note that, and this is the tricky part, the merge does not keep all items.
it truncates to keep the map size the same (otherwise a merge could result
in thing getting out of hand in terms of size). what this means -i believe-
is that after the  merge the bottom element in the structure might have a
count higher than 30 + 29, and the result would be that for an unknow item
it would report count x with error x for some x > (30 + 29). so there is a
loss in precision, but it is still correct.



On Mon, Feb 10, 2014 at 7:44 PM, Koert Kuipers <koert@tresata.com> wrote:

> 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>
>> .
>>
>
>