Finding frequent items in data streams

2003/08/12 by Moses Charikar, Kevin Chen, Martin Farach-Colton +1 · 131 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
• On Finding Similar Items in a Stream of Transactions
• 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
• Universal Streaming of Subset Norms
• An algebraic approach to complexity of data stream computations
• Extreme Classification in Log Memory using Count-Min Sketch: A Case Study of Amazon Search with 50M Products
• Almost Optimal Explicit Johnson-Lindenstrauss Transformations
• Sketch and Scale: Geo-distributed tSNE and UMAP
• Exponentially Improved Dimensionality Reduction for ℓ₁: Subspace Embeddings and Independence Testing
• A Distributed SGD Algorithm with Global Sketching for Deep Learning Training Acceleration
• Catching the head, tail, and everything in between: a streaming algorithm for the degree distribution
• A Survey of Coded Distributed Computing
• Differentially Private Fractional Frequency Moments Estimation with Polylogarithmic Space
• Coding for Random Projections
• An Improved Frequent Directions Algorithm for Low-Rank Approximation via Block Krylov Iteration
• Faster PAC Learning and Smaller Coresets via Smoothed Analysis
• BEAR: Sketching BFGS Algorithm for Ultra-High Dimensional Feature Selection in Sublinear Memory
• Consistent Subset Sampling
• Memory-Efficient Performance Monitoring on Programmable Switches with Lean Algorithms
• Effective sketching methods for value function approximation
• Approximating Large Frequency Moments with Pick-and-Drop Sampling
• Sketch and Project: Randomized Iterative Methods for Linear Systems and Inverting Matrices
• Sketchy With a Chance of Adoption: Can Sketch-Based Telemetry Be Ready for Prime Time?
• Adapting The Secretary Hiring Problem for Optimal Hot-Cold Tier Placement under Top-K Workloads
• Weakly Supervised Attention Learning for Textual Phrases Grounding
• Regularizing Neural Networks via Minimizing Hyperspherical Energy
• L2/L2-foreach sparse recovery with low risk
• Streaming Algorithms from Precision Sampling
• Locality-Sensitive Sketching for Resilient Network Flow Monitoring
• Polynomial Tensor Sketch for Element-wise Function of Low-Rank Matrix
• Trying Bilinear Pooling in Video-QA
• Pyramid: Enhancing Selectivity in Big Data Protection with Count Featurization
• High-Order Attention Models for Visual Question Answering
• Lower Memory Oblivious (Tensor) Subspace Embeddings with Fewer Random Bits: Modewise Methods for Least Squares
• WOR and p's: Sketches for ℓ_p-Sampling Without Replacement
• Tight Bounds for the Subspace Sketch Problem with Applications
• The Power of Hashing with Mersenne Primes
• Non-Adaptive Adaptive Sampling on Turnstile Streams
• Time lower bounds for nonadaptive turnstile streaming algorithms
• AMS Without 4-Wise Independence on Product Domains
• On Parallelizing Matrix Multiplication by the Column-Row Method
• Privacy for Free: Communication-Efficient Learning with Differential Privacy Using Sketches
• (Learned) Frequency Estimation Algorithms under Zipfian Distribution
• Fast Splitting Algorithms for Sparsity-Constrained and Noisy Group Testing
• Combining geometry and combinatorics: A unified approach to sparse signal recovery
• Compact Bilinear Pooling
• A Derandomized Sparse Johnson-Lindenstrauss Transform
• COLOGNE: Coordinated Local Graph Neighborhood Sampling
• On Estimating the First Frequency Moment of Data Streams
• Tensorized Random Projections
• Question Type Guided Attention in Visual Question Answering
• CR-precis: A deterministic summary structure for update data streams
• Model Counting meets F0 Estimation
• Learning to Evaluate Image Captioning
• DreamNLP: Novel NLP System for Clinical Report Metadata Extraction using Count Sketch Data Streaming Algorithm: Preliminary Results
• Implementing Randomized Matrix Algorithms in Parallel and Distributed Environments
• Schatten Norms in Matrix Streams: Hello Sparsity, Goodbye Dimension
• Count-Min: Optimal Estimation and Tight Error Bounds using Empirical Error Distributions
• Optimal Las Vegas Approximate Near Neighbors in ℓ_p
• Distributed Low Rank Approximation of Implicit Functions of a Matrix
• A Practical Guide to Randomized Matrix Computations with MATLAB Implementations
• Bias-Aware Sketches
• Block Compressed Sensing Based Distributed Device Detection for M2M Communications
• Structure-Aware Sampling: Flexible and Accurate Summarization
• Heavy Hitters over Interval Queries
• Stronger L2/L2 Compressed Sensing; Without Iterating
• Modularized Textual Grounding for Counterfactual Resilience
• (Nearly) Sample-Optimal Sparse Fourier Transform in Any Dimension; RIPless and Filterless
• Ranking and benchmarking framework for sampling algorithms on synthetic data streams
• Fast and scalable polynomial kernels via explicit feature maps
• How to find a good image-text embedding for remote sensing visual question answering?
• How to reduce dimension with PCA and random projections?
• RidgeSketch: A Fast sketching based solver for large scale ridge regression
• Tabulation-Based 5-Independent Hashing with Applications to Linear Probing and Second Moment Estimation
• Optimal approximations of the frequency moments of data streams
• Coresets for Vector Summarization with Applications to Network Graphs
• Federated Heavy Hitters Discovery with Differential Privacy
• Dimensionality Reduction for Categorical Data
• An improved data stream summary: the count-min sketch and its applications
• Estimating leverage scores via rank revealing methods and randomization