HyperLogLog
Estimates distinct items, such as unique visitors or IP addresses.
Memory ∝ log log n
Case studies
Student research case study
Louis published original computer science research while still in high school.
He turned a graduate-level question about streaming algorithms into six working implementations, two comparative experiments, and a public paper with a permanent DOI.
- Field
- Streaming algorithms
- Published
- August 26, 2026
- DOI
- 10.5281/zenodo.22103851
- License
- CC BY 4.0
6
streaming algorithms compared
2
student-designed experiments
10³⁹
largest stream scale modeled
64 KB
fixed budget in experiment two
1 DOI
permanent public research record
The student
Meet Louis
Louis came to Pristone wanting to do real computer science—not another tutorial project, but a question without a tidy answer waiting at the back of a book.
He chose a problem from the world of massive data: when a computer must process billions of items but can retain only a few kilobytes at a time, which algorithm should it trust? The topic normally appears at the graduate level and matters in systems such as search, fraud detection, and network security.
Louis did more than summarize six well-known methods. He implemented them, designed two comparisons, ran the experiments, and interpreted what the results did—and did not—show.
The line-up
Six algorithms, six different jobs
The algorithms are not interchangeable. Each answers a different question about a stream, which is why memory use alone cannot determine which method is best.
Flajolet–Martin
The foundational count-distinct sketch that later approaches build upon.
Memory ∝ log n
Misra–Gries
Finds heavy hitters—the most frequent items in a stream.
Memory ∝ (1/ε) log n
Count–Min Sketch
Estimates the frequency of a specified item without undercounting it.
Memory ∝ (1/ε) log(1/ε) log n
Reservoir Sampling
Maintains a fair random sample when the final stream length is unknown.
Memory ∝ (1/ε²) log n
Bloom Filter
Answers whether an item may have appeared before, without false negatives.
Memory ∝ n (linear)
Experiment one
Hold error at 2%. How much memory is needed?
The clearest divide was linear versus sublinear growth. Across streams modeled from 10⁹ through 10³⁹ items, the five sublinear methods stayed within roughly 25 KB. The Bloom Filter, whose memory grows linearly, required about 970 MB at even the smallest tested scale and quickly moved beyond practical storage.
≈ 25 KB
Upper range for the five sublinear methods across the tested sweep.
≈ 970 MB
Bloom Filter memory at the smallest tested stream scale.
Experiment two
Give every algorithm 64 KB. How much error remains?
Louis reversed the first experiment: fix memory, then measure error. The table reproduces the values reported in his summary. Lower is better.
| Algorithm | n = 10⁹ | n = 10¹⁹ | n = 10²⁹ | n = 10³⁹ |
|---|---|---|---|---|
| Misra–GriesBest | 0.011% | 0.024% | 0.037% | 0.050% |
| Count–Min Sketch | 0.078% | 0.166% | 0.252% | 0.337% |
| HyperLogLog | 0.352% | 0.380% | 0.406% | 0.431% |
| Reservoir Sampling | 0.378% | 0.552% | 0.680% | 0.787% |
| Flajolet–Martin | 0.590% | 0.862% | 1.061% | 1.228% |
| Bloom FilterWrong tool | 100% | 100% | 100% | 100% |
The mature interpretation
A 100% Bloom Filter result does not make it a bad algorithm. Bloom Filters are sized for a known, finite set of keys; the setup deliberately gave a linear method a sublinear budget. Louis treated that mismatch as a limitation of the experiment, not a reason for a simplistic winner-and-loser claim.
Beyond the benchmark
He proposed a next question
Louis asked whether error tolerance could adapt as a stream arrives instead of being fixed in advance. He framed the idea as a direction for future work—not a completed result—and connected it to areas where streaming sketches meet machine learning.
Why it matters
A permanent record before college
Zenodo published the paper as an open record with a permanent DOI and CC BY 4.0 license, and Louis published the accompanying Python implementation on GitHub. The paper and code can both be inspected—not a certificate or simulated classroom exercise, but student-owned work on the public record.
Pristone's role
Mentorship without taking authorship
Pristone helped Louis find a question worth pursuing, held the work to academic standards, and coached him through implementation, analysis, and publication. Louis remained the researcher and author; the paper and its conclusions are his work.
What this case does—and does not—show
- It documents one student's sustained technical work and a verified public publication.
- It does not promise publication, admissions, awards, or the same timeline for another student.
- The Zenodo record verifies the author, paper, date, DOI, and license.
- The linked GitHub repository provides the accompanying Python implementation and paper files.
Verified public record
A Comparative Analysis of Streaming Algorithms: Memory Efficiency and Accuracy Under Fixed Budgets
- Author
- Yoonsang (Louis) Lee
- Publisher
- Zenodo · Version 1
- DOI
- 10.5281/zenodo.22103851
- License
- Creative Commons Attribution 4.0
Does your student have a question worth chasing?
A research-readiness diagnostic tests the question, technical prerequisites, experimental judgment, ownership, and the smallest honest next step.
Student-owned work · no guaranteed publication, awards, or admissions outcomes