the merge combines the 2 counters maps. but notice the result is truncated
after sorting:
.sorted(StreamSummary.ordering)
.take(capacity)

to me the hardest part was convincing myself the resulting structure after
the sort and take was correct. it is easy to convince yourself it is
correct for items that are in either map, or in both.

for items that are in neither the newly reported count  (and error, which
will be equal to the count) after the merge of the 2 maps, but before the
take operation, will be the maximum of:

* lowest count on left plus min on right (if item with lowest count of left
was not present on right), so left.min + right.min

* lowest count on left plus actual count on right (if item with lowest
count on left was present on right). if item is present on right it must
have count >= right.min, and therefore result is >= left.min + right.min

* lowest count on right plus min on left (if item with lowest count on
right was not present on left), which is equal to left.min + right.min

* lowest count on right plus actual count on left (if item with lowest
count on right was present on left). if item is present on left it must
have count >= left.min, and therefore result is >= left.min + right.min

so in all cases the resulting lowest_count >= left.min + right.min.

after truncating with the take operation the number can only go up (since
the items are sorted by count desc). since lowest_count becomes min on the
merged object we now have merge.min >= left.min + right.min, which means
for unknown items the domain will be [0, merge.min] for some merge.min >=
left.min + right.min

i believe this is always correct, and the lowest bound possible given the
need to truncate (take operation) to maintain structure sizing...

reading it again its a bit confusing. not sure if this helps...



On Tue, Feb 11, 2014 at 12:18 PM, avibryant <notifications@github.com>wrote:

> In algebird-core/src/main/scala/com/twitter/algebird/StreamSummary.scala:
>
> > +    val buckets1 = buckets + (count -> (buckets.getOrElse(count, Set()) + item))
> > +    new SSMany(m, counters1, buckets1)
> > +  }
> > +
> > +  // add a single element
> > +  private[algebird] def add(x: SSOne[T]): SSMany[T] = {
> > +    require(x.m == m)
> > +    if (counters.contains(x.item))
> > +      bump(x.item)
> > +    else
> > +      (if (exact) this else this.loseOne).introduce(x.item, min + 1L, min)
> > +  }
> > +
> > +  // merge two stream summaries
> > +  // defer the creation of buckets since more pairwise merges might be necessary and buckets are not used for those
> > +  private def merge(x: SSMany[T]): SSMany[T] = {
>
> Your first note made sense, and I can't find a flaw in the argument (and,
> cool! The addition of per-element error is a neat innovation here). I don't
> follow the second part yet, can you elaborate?
>
> --
> Reply to this email directly or view it on GitHub<https://github.com/twitter/algebird/pull/259/files#r9632899>
> .
>