You may be looking for the "majority algorithm." It, and related algorithms are introduced in a helpful article, "The Britney Spears Problem."
erickson
2009-07-20 01:27:47
views:
193answers:
3
+1
A:
I actually remember having read that article when it was published. But there is a difference in the algorithms in step 3. The algorithm in the article would decrement all counters, whereas the one I've described would only decrement a single counter. I vaguely recollect that being an important factor. It makes it more efficient, but I don't know how it affects the accuracy.
2009-07-20 03:18:26
A:
Perhaps look into cache entry replacement algorithms. That seems a lot like LRU (Least Recently Used). There are many variations and, needless to day, they are very very well studied.
Rui Ferreira
2009-07-21 23:45:12
A:
You may be looking for this.
http://www.notjustrandom.com/2009/11/13/finding-frequent-items-in-a-data-stream/
Srinivas
2009-12-15 08:57:18