A simple algorithm for finding frequent elements in streams and bags

By Richard M. Karp, Scott Shenker, Christos H. Papadimitriou. TODS, 2003

558 citations recorded by the source corpus.

Subfields: Artificial Intelligence, Computer Networks and Communications

View Paper: https://www.semanticscholar.org/paper/e82c4930ec5f01508313d8ad9b41565d25ea96d5

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computer Networks and Communications

Citations in the corpus

Retrospective: Flipping Bits in Memory Without Accessing Them: An Experimental Study of DRAM Disturbance Errors (2023, unknown): “Folks developing industrial memory testing programs immediately included RowHammer tests, e.g., in memtest86 [37], citing our work.”
Efficient Computation of Frequent and Top-k Elements in Data Streams (2005, methodology): “Problems studied in this context include approximate frequency moments [1], differences [20], distinct values estimation [22, 33, 45], bit counting [16], duplicate detection [42], approximate quantiles [28, 38, 40], histograms [30, 29], wavelet based aggregate queries [25, 41], correlated aggregate ”
What's hot and what's not: tracking most frequent items dynamically (2003, background): “Several authors [9, 21] have rediscovered the algorithm of Misra and Gries, and using more sophisticated data structures they are able to process each item in expected O(1) time while still keeping only O(k) space.”
Approximate counts and quantiles over sliding windows (2004, methodology): “The same algorithm has been rediscovered recently by Demaine et al [10] and Karp et al [16], who reduced the processing time to O(1) in the worst case.”
Frequent pattern mining: current status and future directions (2007, background): “Karp et al., proposed a counting algorithm for ﬁnding frequent elements in data streams (Karp et al. 2003).”
Flipping bits in memory without accessing them: An experimental study of DRAM disturbance errors (2014, methodology): “Some recent reports suggest that new-generation DDR4 DRAM chips are vulnerable to RowHammer [29, 37], so the fundamental security research on RowHammer is likely to continue into the future.”
Fast and approximate stream mining of quantiles and frequencies using graphics processors (2005, background): “[28] re-discovered the same algorithm and reduced its worst case processing time to O(1).”
Differentially Private Continual Monitoring of Heavy Hitters from Distributed Streams (2012, methodology): “The MG algorithm was rediscovered several times [6, 14].”