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

DOI10.1016/J.JALGOR.2003.12.001zbMATH Open1068.68048OpenAlexW2080234606WikidataQ61920316 ScholiaQ61920316MaRDI QIDQ4675489FDOQ4675489

Authors:

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

Recommendations

• LATIN 2004: Theoretical Informatics
• On Estimating Frequency Moments of Data Streams
• scientific article; zbMATH DE number 2019620
• CR-precis: A Deterministic Summary Structure for Update Data Streams
• The eternal sunshine of the sketch data structure

Mathematics Subject Classification ID

Data structures (68P05)

Cited In (95)

• Multiscale matrix sampling and sublinear-time PageRank computation
• Sketched learning for image denoising
• Space-efficient estimation of statistics over sub-sampled streams
• Time-decaying sketches for robust aggregation of sensor data
• Mining frequent itemsets over distributed data streams by continuously maintaining a global synopsis
• Labeled graph sketches: keeping up with real-time graph streams
• Compressed sensing with sparse binary matrices: instance optimal error guarantees in near-optimal time
• Learned sketches for frequency estimation
• Adaptive spatial partitioning for multidimensional data streams
• Range counting over multidimensional data streams
• Fast and accurate mining of correlated heavy hitters
• A parallel space saving algorithm for frequent items and the Hurwitz zeta distribution
• Deterministic \(k\)-set structure
• Efficient sketches for the set query problem
• Improved range-summable random variable construction algorithms
• A sketch algorithm for estimating two-way and multi-way associations
• On deterministic sketching and streaming for sparse recovery and norm estimation
• Estimating hybrid frequency moments of data streams
• Stochastic reformulations of linear systems: algorithms and convergence theory
• Loda: lightweight on-line detector of anomalies
• Improved Sketching of Hamming Distance with Error Correcting
• Compressed sensing and best \(k\)-term approximation
• A statistical analysis of probabilistic counting algorithms
• Algorithms and Computation
• On approximating matrix norms in data streams
• Hierarchical sampling from sketches: Estimating functions over data streams
• Compressive statistical learning with random feature moments
• Data streams: algorithms and applications.
• Sketching information divergences
• Chirp sensing codes: Deterministic compressed sensing measurements for fast recovery
• LATIN 2004: Theoretical Informatics
• Accuracy vs. Lifetime: Linear sketches for aggregate queries in sensor networks
• The range 1 query (R1Q) problem
• Time-decaying sketches for sensor data aggregation
• Generalizing the layering method of Indyk and Woodruff: recursive sketches for frequency-based vectors on streams
• The eternal sunshine of the sketch data structure
• Streaming techniques and data aggregation in networks of tiny artefacts
• Finding frequent items over sliding windows with constant update time
• An Implicit Representation and Iterative Solution of Randomly Sketched Linear Systems
• Expander \(\ell_0\)-decoding
• Title not available (Why is that?)
• Adversarially robust property-preserving hash functions
• 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
• Nearly optimal distinct elements and heavy hitters on sliding windows
• Voting almost maximizes social welfare despite limited communication
• Range Majority in Constant Time and Linear Space
• Identifying correlated heavy-hitters in a two-dimensional data stream
• Streaming algorithms via precision sampling
• Optimizing the confidence bound of count-min sketches to estimate the streaming big data query results more precisely
• A framework for clustering massive graph streams
• Frugal Streaming for Estimating Quantiles
• Improved algorithms for distributed entropy monitoring
• Evaluating Bayesian networks via data streams
• Computer science and decision theory
• Data streams and applications in computer science
• RidgeSketch: a fast sketching based solver for large scale ridge regression
• Summary data structures for massive data
• The frequent items problem, under polynomial decay, in the streaming model
• Top-\(k\) frequent items and item frequency tracking over sliding windows of any size
• Summarizing data using bottom-\(k\) sketches
• Indexing for summary queries
• CR-precis: A Deterministic Summary Structure for Update Data Streams
• An Approximate L¹ -Difference Algorithm for Massive Data Streams
• Sparsifying count sketch
• Title not available (Why is that?)
• Buffered Count-Min Sketch on SSD: Theory and Experiments
• Randomized counter-based algorithms for frequency estimation over data streams in \(O(\log \log N)\) space
• A randomized online quantile summary in \(O(\frac 1\varepsilon\log\frac 1\varepsilon)\) words
• Space‐efficient tracking of persistent items in a massive data stream
• A Note on Estimating Hybrid Frequency Moment of Data Streams
• Calculating Max and Min with exemplary sketch algorithm in data stream management system
• Tracking the l_2 Norm with Constant Update Time
• Sublinear-space streaming algorithms for estimating graph parameters on sparse graphs
• Phase transition in count approximation by count-min sketch with conservative updates
• Simplified Planar Coresets for Data Streams
• Beating CountSketch for heavy hitters in insertion streams
• A randomized online quantile summary in \(O((1/\varepsilon) \log(1/\varepsilon))\) words
• Arithmetic sketching
• Joint tracking of multiple quantiles through conditional quantiles
• Title not available (Why is that?)
• Forty years of frequent items
• Compressive learning for patch-based image denoising
• Local differentially private frequency estimation based on learned sketches
• Intermediate value linearizability: a quantitative correctness criterion
• Spiking neural networks through the lens of streaming algorithms
• Deterministic heavy hitters with sublinear query time
• On low-risk heavy hitters and sparse recovery schemes
• Title not available (Why is that?)
• Fast identification of heavy hitters by cached and packed group testing
• Periodicity and cyclic shifts via linear sketches
• Streaming algorithms with one-sided estimation
• Count-min sketch with variable number of hash functions: an experimental study
• Adversarially robust streaming algorithms via differential privacy
• Sublinear algorithms for MAXCUT and correlation clustering

This page was built for publication: An improved data stream summary: the count-min sketch and its applications

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4675489)