agreed. let me go over the merge again and make sure its right


On Mon, Feb 10, 2014 at 6:31 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] = {
>
> I'm worried that this merge operation is not associative. I'm not sure how
> much that will come up in practice, but as a pathological case: say you had
> a summary for each day, and each day's top m items were unique to it, but
> the (m+1)th most frequent item was the same for each one. That item should
> be the most frequent overall, but you'll never find that out by merging
> daily summaries.
>
> --
> Reply to this email directly or view it on GitHub<https://github.com/twitter/algebird/pull/259/files#r9607649>
> .
>