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

DOI10.1016/j.jalgor.2003.12.001zbMath1068.68048WikidataQ61920316 ScholiaQ61920316MaRDI QIDQ4675489

No author found.

Publication date: 4 May 2005

Published in: Journal of Algorithms (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.jalgor.2003.12.001

Mathematics Subject Classification ID

68P05: Data structures

Related Items

Unnamed Item, Unnamed Item, Unnamed Item, A framework for clustering massive graph streams, Space‐efficient tracking of persistent items in a massive data stream, Multiscale Matrix Sampling and Sublinear-Time PageRank Computation, An Implicit Representation and Iterative Solution of Randomly Sketched Linear Systems, Compressive Learning for Patch-Based Image Denoising, RidgeSketch: A Fast Sketching Based Solver for Large Scale Ridge Regression, Stochastic Reformulations of Linear Systems: Algorithms and Convergence Theory, Sublinear Algorithms for MAXCUT and Correlation Clustering, Buffered Count-Min Sketch on SSD: Theory and Experiments, Deterministic Heavy Hitters with Sublinear Query Time, Nearly Optimal Distinct Elements and Heavy Hitters on Sliding Windows., On Low-Risk Heavy Hitters and Sparse Recovery Schemes, On Approximating Matrix Norms in Data Streams, Summary Data Structures for Massive Data, Tracking the l_2 Norm with Constant Update Time, Unnamed Item, Phase transition in count approximation by count-min sketch with conservative updates, Joint tracking of multiple quantiles through conditional quantiles, Randomized counter-based algorithms for frequency estimation over data streams in \(O(\log \log N)\) space, Sublinear-space streaming algorithms for estimating graph parameters on sparse graphs, Arithmetic sketching, Forty years of frequent items, Space-efficient estimation of statistics over sub-sampled streams, Loda: lightweight on-line detector of anomalies, Mining frequent itemsets over distributed data streams by continuously maintaining a global synopsis, Estimating hybrid frequency moments of data streams, Streaming techniques and data aggregation in networks of tiny artefacts, Voting almost maximizes social welfare despite limited communication, Optimizing the confidence bound of count-min sketches to estimate the streaming big data query results more precisely, Sketched learning for image denoising, Deterministic \(k\)-set structure, The frequent items problem, under polynomial decay, in the streaming model, Finding frequent items over sliding windows with constant update time, Chirp sensing codes: Deterministic compressed sensing measurements for fast recovery, Sketching information divergences, Hierarchical sampling from sketches: Estimating functions over data streams, The range 1 query (R1Q) problem, Expander \(\ell_0\)-decoding, Identifying correlated heavy-hitters in a two-dimensional data stream, Fast and accurate mining of correlated heavy hitters, A parallel space saving algorithm for frequent items and the Hurwitz zeta distribution, Distributed mining of time-faded heavy hitters, On the power of multiple anonymous messages: frequency estimation and selection in the shuffle model of differential privacy, Top-\(k\) frequent items and item frequency tracking over sliding windows of any size, Labeled graph sketches: keeping up with real-time graph streams, Compressed sensing with sparse binary matrices: instance optimal error guarantees in near-optimal time, Computer science and decision theory, Improved algorithms for distributed entropy monitoring, On deterministic sketching and streaming for sparse recovery and norm estimation, Accuracy vs. Lifetime: Linear sketches for aggregate queries in sensor networks, Compressive statistical learning with random feature moments, Frugal Streaming for Estimating Quantiles, A Statistical Analysis of Probabilistic Counting Algorithms, Indexing for summary queries, Range Majority in Constant Time and Linear Space, Compressed sensing and best 𝑘-term approximation, Periodicity and Cyclic Shifts via Linear Sketches, Streaming Algorithms with One-Sided Estimation, Evaluating Bayesian Networks via Data Streams, Simplified Planar Coresets for Data Streams, A Note on Estimating Hybrid Frequency Moment of Data Streams