4 ms·
> 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 ident
by 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 :)