Fast, small-space algorithms for approximate histogram maintenance

By Anna C. Gilbert, Sudipto Guha, Piotr Indyk, Yannis Kotidis, S. Muthu Muthukrishnan, Martin J. Strauss. Symposium on the Theory of Computing, 2002

305 citations recorded by the source corpus.

Subfields: Computational Mechanics, Computer Vision and Pattern Recognition

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

How researchers see this paper

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

In Computational Mechanics

In Computer Vision and Pattern Recognition

Citations in the corpus

Communication-Efficient Distributed Learning of Discrete Probability Distributions (2017, methodology): “tool for the succinct approximation of data [9, 38, 25, 26, 1].”
Combining geometry and combinatorics: A unified approach to sparse signal recovery (2008, background): “Similarly, we also easily obtain a sketch of a sum of two signals given the sketches for individual signals x and y, since �(x + y) = �x + �y. Both properties are very useful in several computational areas, notably computing over data streams [AMS99, Mut03, Ind07], network measurement [ EV03 ], quer”
What's hot and what's not: tracking most frequent items dynamically (2003, methodology): “A recent theoretical work presented provable algorithms for maintaining histograms with guaranteed accuracy and small space [16].”
Clustering Data Streams: Theory and Practice (2003, background): “…in small space when the data is a stream include: frequency estimation [36], [12], norm estimation [4], [22], [44], order statistics [64], [57], [56], [30], [28], synopsis structures [26], time indexed data [25], [32], [17], [8], signal reconstructions [24], [18], [1], [33], [27], [29], [72].”
An improved data stream summary: the count-min sketch and its applications (2004, methodology): “We have recently applied these ideas to the problem of change detection on data streams [9], and we also believe that it can be applied to improve the time and space bounds for constructing approximate wavelet and histogram representations of data streams [19].”
Fast Monte Carlo Algorithms for Matrices I: Approximating Matrix Multiplication (2006, background): “, [17] for applications to the problem of dynamic histogram maintenance.”
Compressed sensing and best k-term approximation (2008, methodology): “9): for instance the decoders proposed in [7] and [11], respectively, use n ∼ k log(N) and n ∼ k 3 log(N) samples in order to achieve (1.”
Near-optimal sparse fourier representations via sampling (2002, methodology): “The main obstacle in this paper is that we cannot even reliably estimate norms by sampling; by contrast, in [7] norm estimation is easy.”
Federated Learning on Non-IID Data Silos: An Experimental Study (2021, background): “This made a decade of database research relevant, such as data sampling [5] and sketching [17].”