Finding frequent items in data streams

By Moses Charikar, Kevin C. Chen, Martín Farach-Colton. 2002

2,037 citations recorded by the source corpus.

Subfields: Artificial Intelligence, Computer Networks and Communications, Information Systems, Natural Language Processing, Algorithms & Complexity

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 Information Systems

In Natural Language Processing

In Algorithms & Complexity

Citations in the corpus

Memory-Efficient Adaptive Optimization for Large-Scale Learning (2019, methodology): “Spring et al. [25] provide an alternative way to reduce memory costs, making use of the Count-Sketch data structure [7] to maintain a compressed approximation to the auxiliary variables.”
MUTAN: Multimodal Tucker Fusion for Visual Question Answering (2017, methodology): “The count-sketch projection [3] Ψ is used to project q⊗v on a lower dimensional space.”
Federated Learning Of Out-Of-Vocabulary Words (2019, background): “Approaches based on hash maps, count sketches (Charikar et al., 2002), or tries (Gu-nasinghe and Alahakoon, 2012) require signiﬁcant adaptation to be able to run on FL settings (Zhu et al., 2019).”
Federated Heavy Hitters Discovery with Differential Privacy (2019, neutral): “Naively, a service provider can learn the popular elements by ﬁrst col-Proceedings lecting user data and then applying state-of-the-art centralized heavy hitters discovery algorithms (Cor-mode et al., 2003; Cormode and Hadjieleftheriou, 2008; Charikar et al., 2002).”
Deep Fried Convnets (2014, methodology): “For example, the count-sketch algorithm [5] uses pairwise independent hash functions to carry this job very effectively in many applications [9].”
Compact Bilinear Pooling (2015, methodology): “Similar to the RM approach, Count Sketch[4], defined by Ψ(x, h, s) in Algorithm 2, has the favorable property that: E[〈Ψ(x, h, s),Ψ(y, h, s)〉] = 〈x, y〉 [4].”
Efficient Private Statistics with Succinct Sketches (2015, methodology): “Count Sketch [16] is a data structure which provides an estimate for an item’s frequency in a stream.”
Hellinger Strikes Back: A Note on the Multi-party Information Complexity of AND (2009, background): “A major influence on the foundations of massive data sets as well as a pioneer of novel techniques has been the frequency moments problem and its variants [FM85, AMS99, Ind06, BJK+02, CCFC04 , IW05].”
An End-to-End Multimodal Voice Activity Detection Using WaveNet Encoder and Residual Networks (2019, methodology): “This is accomplished via the count sketch projection function suggested in [51], denoted as Ψ, which is a method of projecting a vector c ∈ R to a lower dimensional representation ĉ ∈ R for d < m.”
Graph sketches: sparsification, spanners, and subgraphs (2012, background): “, finding heavy hitters and quantiles [10, 13]; estimating norms and support sizes [32, 33]; and constructing histograms and low-dimensional approximations [11, 26].”
Differentially-Private Multi-Party Sketching for Large-Scale Statistics (2020, methodology): “Count-Sketch [15] and Count-Min Sketch [16] are sketches that are used to approximate the frequencies of elements in a datastream.”
Numerical linear algebra in the streaming model (2009, methodology): “We note that it is also seems possible to obtain a one-pass O(c −2 log(nc) log(c/δ))-space algorithm via techniques in [2, 6, 10], but the space is suboptimal.”
Online Machine Learning in Big Data Streams (2018, background): “Note that a special subtask, ﬁnding frequent items in data streams, is already challenging and requires approximate data structures [50].”
SketchVisor: Robust Network Measurement for Software Packet Processing (2017, background): “However, it needs to update various components (including CountSketch [8] and top-k flow keys), and remains computationally expensive (see analysis below).”
RAPTT: An Exact Two-Sample Test in High Dimensions Using Random Projections (2014, positive): “Our second choice of R is based on the idea of one permutation + one random projection , which is closely related to very sparse random projection (Li et al., 2006) and count-sketch (Charikar et al., 2004).”
Regularizing Neural Networks via Minimizing Hyperspherical Energy (2019, methodology): “For example, we have subsampled randomized Hadamard transform [57] and count sketch-based projections [58].”
Distributed top-k monitoring (2003, background): “This work ([9, 18, 27]) only considers single data streams rather than distributed data streams and concentrates on reducing memory requirements rather than communication costs.”
Elastic sketch: adaptive and fast network-wide measurements (2018, methodology): “Thus Elastic has a much tighter error bound than Count-Min when the parameters (d andw) are the same.”