What's hot and what's not: tracking most frequent items dynamically

By Graham Cormode, S. Muthu Muthukrishnan. ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, 2003

396 citations recorded by the source corpus.

Subfields: Information Systems, Signal Processing

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

How researchers see this paper

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

In Information Systems

In Signal Processing

Citations in the corpus

Approximate counts and quantiles over sliding windows (2004, methodology): “Cormode and Muthukrishnan [7] recently presented randomized algorithms for identifying frequency counts in the presence of both additions and deletions.”
Data streams: algorithms and applications (2005, methodology): “• Using variants ofL1 sketches and other algorithmic techniques, we can dynamica lly tr ck most frequent items [92], wavelets and histograms [93], etc.”
Fast and approximate stream mining of quantiles and frequencies using graphics processors (2005, methodology): “Entire past history: Apply the query over all the elements in the past history of the stream [12, 22, 23, 27, 28, 34].”
Efficient Computation of Frequent and Top-k Elements in Data Streams (2005, methodology): “Furthermore, Space-Saving has a better bound than GroupTest [5], whose bound is O( 1 φ log( 1 δφ ) log(|A|)), which is less scalable than ours.”
Finding Hierarchical Heavy Hitters in Data Streams (2003, methodology): “For the naive algorithm, we make use of the data structure proposed in [4] to (cid:12)nd the Heavy Hitters at each level, and we use the same sketch structure to compute estimated counts. d ) log(1 =(cid:14) )) .”
Heavy-Hitter Detection Entirely in the Data Plane (2016, neutral): “Techniques like group testing [15], reversible sketches [37], and FlowRadar [24] can decode keys from hash-based sketches.”
An improved data stream summary: the count-min sketch and its applications (2004, methodology): “We adopt the solution given in [8], which describes a divide and conquer procedure to find the heavy hitters.”