i will check, but i believe that
1) you are correct that you would never find out its the most frequent
overall
2) however the error-bars on the most frequent items that it did find would
reflect that uncertainty. basically the data structure would admit it was
not able to say much useful at all.


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