9 ms·
On the topic of counting things, I would like to mention this efficient and easily-implemented algorithm for finding the top-k items in a stream, which I think
by gnfargbl 2y ago
On the topic of counting things, I would like to mention this efficient and easily-implemented algorithm for finding the top-k items in a stream, which I think is perhaps not as well known as it should be:
A Simple Algorithm for Finding Frequent Elements in Streams and Bags
Karp, Shenker & Papadimitriou
https://www.cs.umd.edu/~samir/498/karp.pdf https://www.cs.umd.edu/~samir/498/karp.pdf
- vanderZwan 2y ago> the top-k items in a stream Hmm, this is phrased in a way that sounds different (to my ears) than the abstract, which says: > it is often desirable to identify from a very long sequence of symbols (or tuples, or packets) coming from a large alphabet those symbols whose frequency is above a given threshold Your description suggests a finding fixed nr of k items, with the guarantee that it will be the top ones. The abstract sounds like if determines an a priori unknown number of items that meet the criteria of having a particular value greater than k. So "find the 100 oldest users" vs "find all users older than 30". Am I misunderstanding you or the abstract? (English is not my first language)
- gnfargbl 2y agoIt's been a while since I used this in anger, but my recollection is that it maintains a fixed-size set of items. The same algorithm is in section 3.2 of https://erikdemaine.org/papers/NetworkStats_TR2002/paper.pdf https://erikdemaine.org/papers/NetworkStats_TR2002/paper.pdf and might be clearer there.
- vanderZwan 2y agoThank you, that is much easier to follow indeed! Very elegant, I agree :)