Finding frequent items in data streams
โ
Moses Charikar; Kevin Chen; Martin Farach-Colton
๐
Article
๐
2004
๐
Elsevier Science
๐
English
โ 232 KB
We present a 1-pass algorithm for estimating the most frequent items in a data stream using limited storage space. Our method relies on a data structure called a COUNT SKETCH, which allows us to reliably estimate the frequencies of frequent items in the stream. Our algorithm achieves better space bo