An improved data stream summary: the count-min sketch and its applications

By Graham Cormode, S. Muthu Muthukrishnan. 2004

2,628 citations recorded by the source corpus.

Subfields: Artificial Intelligence, Computer Networks and Communications, Signal Processing

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

In Signal Processing

Citations in the corpus

Encode, Shuffle, Analyze Privacy Revisited: Formalizations and Empirical Evaluation (2020, methodology): “For large domains, in order to reduce communication/storage one can use a sketching algorithm (e.g., count-mean-sketch [26]) to establish a compact encoding.”
#Exploration: A Study of Count-Based Exploration for Deep Reinforcement Learning (2016, neutral): “However, an alternative technique called Count-Min Sketch (Cormode & Muthukrishnan, 2005), with a data structure identical to counting Bloom ﬁlters (Fan et al., 2000), can count with a ﬁxed integer array and thus reduce computation time.”
Efficient Private Statistics with Succinct Sketches (2015, methodology): “Using Count-Min Sketch [22], we reduce computation and communication overhead incurred by each user from linear to logarithmic in the size of the input.”
Continual Learning in Practice (2019, background): “For estimating the counts of items in data streams, the count-min sketch [14] is a sublinear space data structure which allows fundamental queries in data stream summarisation such as point, range, and inner product queries to be approximately answered very quickly.”
NetCache: Balancing Key-Value Stores with Fast In-Network Caching (2017, background): “The query statistics module contains three major components (Figure 7): (i ) a per-key counter array to keep query frequency of each cached item, (ii ) a Count-Min sketch [12] to detect hot queries for uncached items, and (iii ) a Bloom filter [8] that removes duplicate hot key reports (to reduce co”
Algorithms with predictions (2020, background): “Dell’Amico, Carra, and Michardi empirically study scheduling policies for queueing systems with estimated sizes (Dell’Amico et al., 2015). As mentioned, Purohit et al. (2018) specifically looked at scheduling with predictions in the standard online setting, where they considered variants of shortest”
Hash Kernels (2009, methodology): “Kernel Approximation Our approach is most closely related to the Count-Min sketch [Cormode and Muthukrishnan, 2004] insofar as it uses a hash function to reduce a feature vector to a more compact representation.”
Randomised Language Modelling for Statistical Machine Translation (2007, background): “, (Cormode and Muthukrishn, 2005); while these schemes are more general than ours, they incur greater space overheads for the distributions that we consider here.”
Verifying Computations with Streaming Interactive Proofs (2011, background): “This class includes, for example, many fundamental matrix problems (e.g. determinant, product, inverse), and graph problems (e.g. minimum spanning tree, shortest paths) (see [2, Chapter 6]).”
Sparse Recovery Using Sparse Matrices (2010, methodology): “Count-Median: The count-min algorithm can be extended to work for general signals [ 9 ]; the extension is often referred to as the count-median algorithm.”
Stochastic Reformulations of Linear Systems: Algorithms and Convergence Theory (2017, methodology): “All standard sketching matrices S can be employed within our framework, including the count sketch [6] and the count-min sketch [8].”
Approximate counts and quantiles over sliding windows (2004, methodology): “Algorithms for the problem over data streams have been developed by Charikar et al [6], Cormode and Muthukrishnan [7] and Gibbons and Matias [13].”
One Permutation Hashing (2012, methodology): “The variable-length hashing scheme is to some extent related to the Count-Min (CM) sketch [6] and the Vowpal Wabbit (VW) [21, 25] hashing algorithms.”
Large Scale Distributed Semi-Supervised Learning Using Streaming Approximation (2015, neutral): “Talukdar and Cohen [28] recently proposed a method that seeks to overcome the label scale problem by using a Count-Min Sketch [10] to approximate labels and their scores for each node.”