📊 statistics

StreamSampling.jl: Efficient Sampling from Data Streams in Julia

This paper introduces StreamSampling.jl, a Julia library that enables efficient, single-pass sampling from data streams with unknown sizes while maintaining a constant memory footprint, and validates its performance advantages over traditional methods through empirical benchmarks.

Original authors: Adriano Meligrana

Published 2026-05-15

📖 4 min read☕ Coffee break read

CC BY 4.0

Original authors: Adriano Meligrana

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are standing in front of a giant, endless conveyor belt carrying millions of boxes. You need to pick a few boxes to inspect, but you have a problem: you don't know how many boxes are coming, and you only have a tiny backpack to carry your samples. You can't stop the belt, you can't look at all the boxes at once, and you can't carry them all home.

This is the problem StreamSampling.jl solves for the Julia programming language. It is a toolkit that helps computers pick random samples from massive, flowing streams of data without needing to stop and memorize the whole thing.

Here is how it works, broken down into simple concepts:

1. The Two Main Strategies

The paper explains that there are two main ways to handle this "endless conveyor belt" problem, and the library offers both:

The "Reservoir" Method (The Bucket Strategy):
Imagine you have a bucket that can hold exactly 10 items. As boxes fly by on the conveyor belt, you drop them into the bucket. If the bucket is full, you randomly kick one out to make room for the new one.
- Why it's great: You don't need to know how many boxes are coming. You just keep the bucket full, and at any moment, the 10 items inside are a fair, random representation of everything you've seen so far.
- When to use it: When the data stream is endless or you don't know the total count.
The "Sequential" Method (The Skip-Counting Strategy):
Imagine you know exactly how many boxes are on the belt (say, 100 million). Instead of carrying a bucket, you do some math to figure out: "I need to skip 50 boxes, pick the next one, skip 200, pick the next one."
- Why it's great: You don't need to carry any boxes in your backpack while the belt is moving. You just jump straight to the ones you need.
- When to use it: When you know the total number of items in advance. It's faster and uses almost no memory, but it fails if you don't know the total count.

2. Why This Library is Special

Before this tool, programmers had to use different tools for different jobs, or they had to download the entire stream of data into their computer's memory before picking samples.

The Old Way: Imagine trying to pick 10 apples from a truckload of 1 million. The old way required you to dump the whole truck into your living room, sort through them, and then pick 10. Your living room (computer memory) would explode.
The StreamSampling Way: You walk alongside the truck, pick your 10 apples as they pass, and never bring the whole truck inside.

The paper claims this library is the only one in the Julia language that offers both the "Bucket" and "Skip-Counting" strategies, handling both simple items and items with different "weights" (importance).

3. Real-World Proof (The Benchmarks)

The authors tested their library against the standard methods to prove it works better.

The Test: They tried to pick samples from a stream of 100 million items.
The Result: The old methods tried to load all 100 million items into memory, which took a long time and used a lot of space. The new library used a tiny amount of memory and finished much faster.
The "100 GB" Challenge: They even tested it on a 100 GB file stored on a hard drive (like a massive digital warehouse). The old method crashed because it ran out of memory. The new library successfully picked samples without ever crashing, proving it can handle data too big to fit in a computer's brain.

4. How It Fits Together

The library is designed to be a "plug-and-play" part of the Julia ecosystem.

It talks to other popular Julia tools (like OnlineStats.jl) so it fits right into existing data pipelines.
It offers a simple command (itsample) that automatically decides whether to use the "Bucket" or "Skip-Counting" method based on whether the computer knows the total size of the data or not.

Summary

In short, StreamSampling.jl is a smart, memory-efficient tool that lets computers pick random samples from data streams that are too big to fit in memory. It uses clever math to either keep a small, constantly updating "bucket" of samples or to calculate exactly which items to skip, ensuring that data analysis can happen in real-time without crashing the computer.

Technical Summary of StreamSampling.jl: Efficient Sampling from Data Streams in Julia

Problem Statement
Random sampling from data streams is a critical operation in data analysis, particularly when dealing with massive datasets that exceed available memory or continuous streams of indeterminate length. Traditional sampling procedures often require fully materializing the population in memory, leading to substantial allocation overhead and potential out-of-memory failures. While online sampling techniques (algorithms processing elements sequentially in a single pass) exist in various languages, they are often fragmented, addressing specific use cases (e.g., class imbalance in machine learning) or tied to specific ecosystems (e.g., Hadoop/Pig), lacking a unified, general-purpose suite within the Julia programming language.

Methodology and Implemented Methods
The paper introduces StreamSampling.jl, a native Julia library designed to provide general and efficient methods for sampling from data streams in a single pass, even when the total number of items ( $N$ ) is unknown. The library categorizes its algorithms along three axes: underlying logic (reservoir vs. sequential), sampling scheme (with vs. without replacement), and inclusion probabilities (weighted vs. unweighted).

The implemented methods include:

Reservoir Sampling: Maintains a fixed-size sample ( $K$ $K$ ) dynamically updated as elements arrive. This approach is ideal for unbounded streams where $N$ $N$ is unknown.
- Unweighted: AlgR and AlgL (without replacement); AlgRSWRSKIP (with replacement).
- Weighted: AlgARes and AlgAExpJ (without replacement); AlgWRSWRSKIP (with replacement).
Sequential Sampling: Typically used when $N$ $N$ or the total weight ( $W_N$ $W_{N}$ ) is known in advance. These methods compute skip lengths to select elements without maintaining a reservoir, offering higher efficiency when prior knowledge is available.
- Unweighted: AlgD and AlgHiddenShuffle (without replacement); AlgORDSWR (with replacement).
- Weighted: AlgORDWSWR (with replacement).
- Note: The paper explicitly notes that a weighted sequential method without replacement is mathematically impossible in a single pass if only the total remaining weight is known, as individual weights are required to determine subsequent inclusion probabilities.

Software Design and Architecture
The library is designed to integrate seamlessly with existing Julia streaming workflows:

Reservoir Samplers: Align with the OnlineStats.jl API, exposing fit!, value, and merge! operations. This allows them to be composable with online and distributed workflows. They support both mutable and immutable forms (generated via HybridStructs.jl), with immutable variants offering better performance.
Sequential Samplers: Follow Julia's standard iterator protocol. They wrap an input iterable and the known population size/weight, emitting selected elements on the fly without intermediate collection.
Data Structures: Weighted sampling without replacement utilizes binary heaps to efficiently maintain top- $K$ priorities, while unweighted and replacement-based methods use flat arrays for reduced overhead.
Interface: The itsample function provides a convenience layer that automatically dispatches to reservoir methods for unknown-length iterators or sequential methods when the length is known.

Key Contributions

Unified Suite: StreamSampling.jl is presented as the only package in the Julia ecosystem (to the author's knowledge) offering a comprehensive breadth of reservoir and sequential sampling variations (weighted/unweighted, with/without replacement) in a single, self-contained library.
Memory Efficiency: The library avoids the need to fully materialize streams in memory, maintaining a constant memory footprint ( $O(K)$ ) for reservoir methods and $O(1)$ for sequential methods.
Research Implementation: The package implements recent research results, specifically AlgWRSWRSKIP, tying the software directly to recent academic publications.
Integration: The design adheres to Julia's iterable protocol and OnlineStats.jl standards, facilitating integration into existing data pipelines.

Experimental Results
The paper presents empirical benchmarks comparing StreamSampling.jl against standard approaches (specifically StatsBase.sample which materializes data):

Iterator Benchmarks: On a generator of $10^8$ integers, reservoir and sequential methods drastically reduced memory allocations compared to the population-based baseline. For small sample sizes, they were significantly faster. Sequential methods with known $N$ avoided the need for a second pass, further reducing time.
Out-of-Core Experiment: A test sampling from a 100 GB Arrow dataset on disk demonstrated the library's scalability. The baseline chunked approach using StatsBase.sample failed due to out-of-memory errors at larger sample sizes (1%). In contrast, both reservoir and sequential methods successfully processed the largest sample sizes with substantially lower execution times. The reservoir method was most efficient in single-threaded execution, while the sequential method demonstrated superior parallel scaling.

Significance and Claims
The authors claim that StreamSampling.jl transfers current data-stream sampling research into practical Julia workflows. The significance is threefold:

Performance: It reduces runtime and memory consumption by avoiding full population materialization, making iterator-based sampling practical where traditional methods incur high allocation overhead.
Scalability: It enables sampling on scales (e.g., 100 GB datasets) where standard chunking approaches fail.
Ecosystem Gap: It fills a gap in the Julia ecosystem by providing a unified, general-purpose sampling suite that is compatible with existing data pipelines and supports both reservoir and sequential paradigms.

The paper concludes modestly, noting that while the package is recent, it already shows credible near-term scholarly significance and is positioned for use in statistical computing and large-scale data analysis. Future work is identified as extending support to Bernoulli/Poisson sampling, sliding window techniques, and stratified reservoir algorithms, as well as integrating these methods into StatsBase.sample.