Finding frequent items in data streams

2003/08/12 by Moses Charikar, Kevin Chen, Martin Farach-Colton +1 · 53 citations
Computer Science · #Data Mining Algorithms and Applications #Advanced Database Systems and Queries #Data Stream Mining Techniques

paper · doi:10.1016/s0304-3975(03)00400-6

Cited by

• DRIVE: One-bit Distributed Mean Estimation
• Clustering High Dimensional Dynamic Data Streams
• Data Synopses Management based on a Deep Learning Model
• Compressed Sensing with Very Sparse Gaussian Random Projections
• Sparse sketches with small inversion bias
• Fast and Guaranteed Tensor Decomposition via Sketching
• FetchSGD: Communication-Efficient Federated Learning with Sketching
• Sketching for Kronecker Product Regression and P-splines
• Online Machine Learning in Big Data Streams
• Composite Hashing for Data Stream Sketches
• Pseudo-deterministic Streaming
• Faster Kernel Ridge Regression Using Sketching and Preconditioning
• Matrix Sketching for Secure Collaborative Machine Learning
• Stochastic Dual Ascent for Solving Linear Systems
• Faster Randomized Methods for Orthogonality Constrained Problems
• Enhancing the Privacy of Federated Learning with Sketching
• Streaming Symmetric Norms via Measure Concentration
• Distributed Hierarchical GPU Parameter Server for Massive Scale Deep Learning Ads Systems
• Estimating the Size of Union of Sets in Streaming Models
• Faster and More Accurate Measurement through Additive-Error Counters
• Sublinear Time Low-Rank Approximation of Distance Matrices
• Optimal approximate matrix product in terms of stable rank
• A Sparse Johnson--Lindenstrauss Transform
• Compressed Matrix Multiplication
• Sparse Fourier Transform in Any Constant Dimension with Nearly-Optimal Sample Complexity in Sublinear Time
• Frequent Directions : Simple and Deterministic Matrix Sketching
• RAMBO: Repeated And Merged BloOm Filter for Ultra-fast Multiple Set Membership Testing (MSMT) on Large-Scale Data
• Compressive Sensing with Local Geometric Features
• Multimodal Compact Bilinear Pooling for Visual Question Answering and Visual Grounding
• Communication-Efficient Distributed Deep Learning: A Comprehensive Survey
• Sublinear-Time Algorithms for Compressive Phase Retrieval
• Deterministic algorithms for skewed matrix products
• Low-rank Approximation of a Matrix: Novel Insights, New Progress, and Extensions
• ISLET: Fast and Optimal Low-rank Tensor Regression via Importance Sketching
• Notes on Randomized Algorithms
• Near-Linear Time Local Polynomial Nonparametric Estimation with Box Kernels
• DALock: Distribution Aware Password Throttling
• KONG: Kernels for ordered-neighborhood graphs
• 2FA Sketch: Two-Factor Armor Sketch for Accurate and Efficient Heavy Hitter Detection in Data Streams
• A Robust Sparse Fourier Transform in the Continuous Setting
• On the Power of Multiple Anonymous Messages
• Faster Update Time for Turnstile Streaming Algorithms
• Graph Sample and Hold: A Framework for Big-Graph Analytics
• BPTree: an ℓ₂ heavy hitters algorithm using constant memory
• Better and Faster: Knowledge Transfer from Multiple Self-supervised Learning Tasks via Graph Distillation for Video Classification
• The Online Event-Detection Problem
• Recursive Sketching For Frequency Moments
• Lifelong Learning with Sketched Structural Regularization
• Hokusai - Sketching Streams in Real Time
• CountSketches, Feature Hashing and the Median of Three
• Low Rank Approximation and Regression in Input Sparsity Time
• Communication-efficient distributed SGD with Sketching
• SF-sketch: A Two-stage Sketch for Data Streams