ok here is an attempt at demonstrating it:

to illustrate, say you have 2 streamsummaries (so parallelism is 2).

errors are reported as possible overcounting. so count of 30 and error of
10 means the true count was in range [20, 30]

the most frequent item in on streamsummary 1 is coffee with count 40 and
error 0, and the minimum count is 30.
the most frequent item in on streamsummary 2 is tea with count 38 and error
0, and the minimum count is 29.

assume the true most frequent item is hidden in those minimum counts, and
it is not present in either datastructure. it could have appeared up to 30
+ 29 times.
after a merge it would report coffee with a count of 40 + 29 and an error
of 29, and tea with a count of 38 + 30 and an error of 30.

any unknown item (not kept in either streamsummary) would report count of
30 + 29 with error of 30 + 29

so you get these ranges:
coffee  [40, 69]
tea     [38, 68]
unknown [0, 59]

this shows that coffee can be replaced by any unknow argument as the most
frequent item. the data structure this way admits it doesnt know.



On Mon, Feb 10, 2014 at 7:20 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] = {
>
> Ah, that's interesting, and not intuitively obvious to me. Would love to
> see a demonstration of this.
>
> --
> Reply to this email directly or view it on GitHub<https://github.com/twitter/algebird/pull/259/files#r9609124>
> .
>