TY - GEN
T1 - Finding frequent items in data streams
AU - Charikar, Moses
AU - Farach-Colton, Martin
N1 - Funding Information: ∗Corresponding author. E-mail addresses: [email protected], (M. Charikar), [email protected] (K. Chen), [email protected] (M. Farach-Colton). 1Most of this work was done while the authors were at Google Inc. Moses Charikar gratefully acknowledges support from NSF ITR Grant CCR-0205594 and DOE Early Career Principal Investigator award DE-FG02-02ER25540.
PY - 2002
Y1 - 2002
N2 - We present a 1-pass algorithm for estimating the most frequent items in a data stream using very limited storage space. Our method relies on a novel data structure called a count sketch, which allows us to estimate the frequencies of all the items in the stream. Our algorithm achieves better space bounds than the previous best known algorithms for this problem for many natural distributions on the item frequencies. In addition, our algorithm leads directly to a 2-pass algorithm for the problem of estimating the items with the largest (absolute) change in frequency between two data streams. To our knowledge, this problem has not been previously studied in the literature.
AB - We present a 1-pass algorithm for estimating the most frequent items in a data stream using very limited storage space. Our method relies on a novel data structure called a count sketch, which allows us to estimate the frequencies of all the items in the stream. Our algorithm achieves better space bounds than the previous best known algorithms for this problem for many natural distributions on the item frequencies. In addition, our algorithm leads directly to a 2-pass algorithm for the problem of estimating the items with the largest (absolute) change in frequency between two data streams. To our knowledge, this problem has not been previously studied in the literature.
UR - http://www.scopus.com/inward/record.url?scp=84869158135&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84869158135&partnerID=8YFLogxK
U2 - 10.1007/3-540-45465-9_59
DO - 10.1007/3-540-45465-9_59
M3 - Conference contribution
SN - 3540438645
SN - 9783540438649
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 693
EP - 703
BT - Automata, Languages and Programming - 29th International Colloquium, ICALP 2002, Proceedings
A2 - Widmayer, Peter
A2 - Eidenbenz, Stephan
A2 - Triguero, Francisco
A2 - Morales, Rafael
A2 - Conejo, Ricardo
A2 - Hennessy, Matthew
PB - Springer Verlag
T2 - 29th International Colloquium on Automata, Languages, and Programming, ICALP 2002
Y2 - 8 July 2002 through 13 July 2002
ER -