Random sampling with a reservoir
1985/03/01 by Jeffrey S. Vitter, Jeffrey Scott Vitter · 1,772 citations
Computer Science · Mathematics · #Algorithm #Algorithms and Data Compression #Computer science #Constant (computer programming) #Current (fluid) #Machine Learning and Algorithms #Margin (machine learning) #Markov Chains and Monte Carlo Methods #Mathematical optimization #Mathematics #Pascal (unit) #Sampling (signal processing)
paper · pdf · doi:10.1145/3147.3165
published in ACM Transactions on Mathematical Software 11(1), 37-57 (Association for Computing Machinery)
openalex publication_date 1985/03/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/04
Abstract
We introduce fast algorithms for selecting a random sample of n records without replacement from a pool of N records, where the value of N is unknown beforehand. The main result of the paper is the design and analysis of Algorithm Z; it does the sampling in one pass using constant space and in O ( n (1 + log( N/n ))) expected time, which is optimum, up to a constant factor. Several optimizations are studied that collectively improve the speed of the naive version of the algorithm by an order of magnitude. We give an efficient Pascal-like implementation that incorporates these modifications and that is suitable for general use. Theoretical and empirical results indicate that Algorithm Z outperforms current methods by a significant margin.
Cited by
- Half-Approximating Maximum Dicut in the Streaming Setting
- The Effectiveness of Approximate Regularized Replay for Efficient Supervised Fine-Tuning of Large Language Models
- Data Quality Profiling at Scale with Progressive Sampling: A Benchmark for Data-Centric AI Pipelines
- A fast algorithm for the Hecke representation of the braid group, and applications to the computation of the HOMFLY-PT polynomial and the search for interesting braids
- FlexiWalker: Extensible GPU Framework for Efficient Dynamic Random Walks with Runtime Adaptation
- Perfect Lp Sampling with Polylogarithmic Update Time
- SuRe: Surprise-Driven Prioritised Replay for Continual LLM Learning
- Mitigating Catastrophic Forgetting in Streaming Generative and Predictive Learning via Stateful Replay
- FuseSampleAgg: Fused Neighbor Sampling and Aggregation for Mini-batch GNNs
- SoK: Systematizing a Decade of Architectural RowHammer Defenses Through the Lens of Streaming Algorithms
- Reducing normalizing flow complexity for MCMC preconditioning
- SAMix: Calibrated and Accurate Continual Learning via Sphere-Adaptive Mixup and Neural Collapse
- BOTANIC-0: a series of foundation models for plant genomic data
- Enhancing Foveated Rendering with Weighted Reservoir Sampling
- Towards Sampling Data Structures for Tensor Products in Turnstile Streams
- Foundation vs. Specialized Models: Evaluating Catastrophic Forgetting in Continual Time Series Forecasting
- Continual Learning to Generalize Forwarding Strategies for Diverse Mobile Wireless Networks
- What Is The Political Content in LLMs' Pre- and Post-Training Data?
- Lifelong Learning with Behavior Consolidation for Vehicle Routing
- Global Pre-fixing, Local Adjusting: A Simple yet Effective Contrastive Strategy for Continual Learning
- The Expiration Streaming Model: Diameter, k-Center, Counting, Sampling, and Friends
- What Were You Thinking? An LLM-Driven Large-Scale Study of Refactoring Motivations in Open-Source Projects
simple-idealized-1d-nlse: Pseudo-Spectral Solver for the 1D Nonlinear Schrödinger Equation- Filtering with Randomised Observations: Sequential Learning of Relevant Subspace Properties and Accuracy Analysis
- Constructing Long Paths in Graph Streams
- Triangle Counting in Hypergraph Streams: A Complete and Practical Approach
- The WASM Cloak: Evaluating Browser Fingerprinting Defenses Under WebAssembly based Obfuscation
- DTC: Real-Time and Accurate Distributed Triangle Counting in Fully Dynamic Graph Streams
- Unbiased Insights: Optimal Streaming Algorithms for ℓp Sampling, the Forget Model, and Beyond
- Efficient Multimodal Streaming Recommendation via Expandable Side Mixture-of-Experts
- Online Continual Graph Learning
- Revisiting Replay and Gradient Alignment for Continual Pre-Training of Large Language Models
- Random-Access Ranked Retrieval and Similarity Search
- From Static to Dynamic: A Streaming RAG Approach to Real-time Knowledge Base
- Towards Tight Bounds for Estimating Degree Distribution in Streaming and Query Models
- Longitudinal Sampling of URLs From the Wayback Machine
- CLA: Latent Alignment for Online Continual Self-Supervised Learning
- Continual Reinforcement Learning by Planning with Online World Models
- Learning Representations on the Unit Sphere: Investigating Angular Gaussian and von Mises-Fisher Distributions for Online Continual Learning
- Monte Carlo Neural Fictitious Self-Play: Approach to Approximate Nash equilibrium of Imperfect-Information Games
- Dual-Alignment Knowledge Retention for Continual Medical Image Segmentation
- Holistic Continual Learning under Concept Drift with Adaptive Memory Realignment
- Streaming Algorithms for News and Scientific Literature Recommendation: Submodular Maximization with a d-Knapsack Constraint
- Optimal Rates for Random Order Online Optimization
- “Select and Resequence” Methods Enable a Genome-Wide Association Study of the Dimorphic Human Fungal Pathogen Coccidioides posadasii
- Distributed Random Walks
- Combining Aggregation and Sampling (Nearly) Optimally for Approximate Query Processing
- Alice and the Caterpillar: A more descriptive null model for assessing data mining results
- Principal Gradient Direction and Confidence Reservoir Sampling for Continual Learning
- Preemptive Online Partitioning of Sequences
- A Framework for Behavioral Biometric Authentication using Deep Metric Learning on Mobile Devices
- Neural Fictitious Self-Play on ELF Mini-RTS
- Memory Efficient Experience Replay for Streaming Learning
- Approximate Borderline Sampling using Granular-Ball for Classification Tasks
- Gradient based sample selection for online continual learning
- Single Deep Counterfactual Regret Minimization
- Towards "Intelligent Compression" in Streams: A Biased Reservoir Sampling based Bloom Filter Approach
- A Survey on Sampling and Profiling over Big Data (Technical Report)
- A space efficient streaming algorithm for triangle counting using the birthday paradox
- Tracking Top-K Influential Vertices in Dynamic Networks
- Elastic Processing of Analytical Query Workloads on IaaS Clouds
- Class Incremental Online Streaming Learning
- Efficient Knowledge Graph Accuracy Evaluation
- Dynamic Dual Buffer with Divide-and-Conquer Strategy for Online Continual Learning
- HENN: A Hierarchical Epsilon Net Navigation Graph for Approximate Nearest Neighbor Search
- Reservoir Designs for Online Paired Experiments
- Schatten Norms in Matrix Streams: Hello Sparsity, Goodbye Dimension
- A Unified Gradient-based Framework for Task-agnostic Continual Learning-Unlearning
- ReservoirTTA: Prolonged Test-time Adaptation for Evolving and Recurring Domains
- DROP: Dimensionality Reduction Optimization for Time Series
- Simultaneous 3D Object Segmentation and 6-DOF Pose Estimation
- Perfect and Maximum Randomness in Stratified Sampling over Joins
- Distributed Tera-Scale Similarity Search with MPI: Provably Efficient Similarity Search over billions without a Single Distance Computation
- Advancing Multiple Instance Learning with Continual Learning for Whole Slide Imaging
- A Conformal Predictive Measure for Assessing Catastrophic Forgetting
- Streaming Word Embeddings with the Space-Saving Algorithm
- On efficient construction of stochastic moment matrices
- DDoS defense by offense
- Optimized stratified sampling for approximate query processing
- A random walk approach to sampling hidden databases
- Event Stream-Based Process Discovery using Abstract Representations
- Pinpointing Performance Inefficiencies in Java
- Tracking Influential Individuals in Dynamic Networks
- Probabilistic Value Selection for Space Efficient Model
- Improvements of Dark Experience Replay and Reservoir Sampling towards Better Balance between Consolidation and Plasticity
- The effect of the dispersal kernel on isolation-by-distance in a continuous population
- Informed Content Delivery Across Adaptive Overlay Networks
- A survey on concept drift adaptation
- Models and issues in data stream systems
- Batched ranged random integer generation
- Storyboard: Optimizing Precomputed Summaries for Aggregation
- MIHash: Online Hashing with Mutual Information
- Computing classic closeness centrality, at scale
- Explainability and Continual Learning meet Federated Learning at the Network Edge
Related