i should have simply said:

after merging the 2 maps but before the take operation, the new minimum
count is going to be the sum of the minimum counts on left and right, or
possibly higher (if all the items that had minimum counts on left had
higher counts on right and vice versa).

truncating after a sort descending by count can only raise this minimum
count (a reflection of information loss due to the truncation). so the new
minimum count is guaranteed to be higher than the sum of the minimum counts
on both sides.

since merge.min >= left.min + right.min, for an unknown item we had before
that it's count on left would be in range [0, left.min] and on right in
range [0, right.min], which summed up leads to range [0, left.min +
right.min]. now its [0, merge.min] which is guaranteed to to encompass the
old estimate (and possibly be less precise).


On Tue, Feb 11, 2014 at 12:54 PM, Koert Kuipers <koert@tresata.com> wrote:

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