Probably 🎲

An interactive lab for probabilistic data structures.

Count distinct visitors, test membership, estimate frequencies, and measure similarity over huge streams — without storing everything. Probably teaches the sketches that power Redis, Cassandra, Presto, and modern monitoring, and lets you play with them: feed data, watch the internal state fill, and see the estimate track (or drift from) the exact answer in real time.

Why this exists

Bloom filters have a hundred explainers. But the moment you need to count distinct things (HyperLogLog), estimate frequencies (Count-Min Sketch), delete from a filter (Cuckoo filter), or measure set similarity (MinHash), the material thins out to dense papers and one-off blog posts. There was no single place to play with the whole family, size them for a real workload, and copy correct code. That's what this is.

Every visualization runs on an actual, tested implementation from src/core — nothing is mocked for the demo. If a chart shows an estimate converging on the truth, that convergence really happened, live.

What's inside

Structure	Answers	Error	Delete?	Lab
Bloom filter	Is x in the set?	false positives	no	live bit grid · sizing calculator · empirical FPR
Cuckoo filter	Is x in the set?	false positives	yes	bucket/slot grid · Bloom-vs-Cuckoo memory
HyperLogLog	How many distinct?	±% of the count	—	register heatmap · estimate-vs-truth convergence
Count-Min Sketch	How often is x?	overcount ≤ ε·N	—	counter grid · estimated-vs-actual scatter
Top-K (Space-Saving)	Which items are hot?	count in [c−ε, c]	—	live ranked heavy-hitter bars
DDSketch	What's the p99?	±α relative	—	bucket histogram · quantile curve · percentile table
MinHash + LSH	How similar are A, B?	±√(J(1−J)/k)	—	signature strip · convergence · LSH S-curve
Reservoir sampling	A fair sample?	none (exact sample)	—	live reservoir · uniformity histogram

Each lab combines a plain-language explainer, a live visualization you can feed data into, a sizing calculator or experiment, and copy-pasteable reference code.

Two things in one repo

1. src/core/ — a zero-dependency, thoroughly tested TypeScript library of the structures. Usable on its own as a correct reference.
2. The lab (the web app) — a "which structure do I need?" decision guide, per-structure explainers with live visualizations, playgrounds that plot estimate-vs-truth as you feed data, and sizing calculators.

Using the core library on its own

Framework-agnostic, no dependencies:

import { BloomFilter, HyperLogLog, CountMinSketch, MinHash } from "./src/core";

// Membership in a few bits per item, never a false negative.
const seen = BloomFilter.optimal(1_000_000, 0.01);
seen.add("user@example.com");
seen.has("user@example.com"); // → true (probably)

// Distinct count in ~12 KB, whatever the scale.
const distinct = new HyperLogLog({ precision: 14 });
for (const ip of stream) distinct.add(ip);
distinct.count(); // ≈ unique IPs, ±0.8%

// Frequency estimate that never undercounts.
const freq = CountMinSketch.create(0.001, 0.01);
freq.add("/api/login");
freq.estimate("/api/login"); // ≥ true count, over by at most ε·N

// Set similarity from short signatures.
const a = new MinHash({ numHashes: 128 });
a.add("shingle-1"); /* … */
a.jaccard(b); // ≈ Jaccard similarity

Develop

npm install
npm run dev        # start the lab locally (Vite)
npm test           # run the full test suite (Vitest)
npm run typecheck  # strict TypeScript check
npm run build      # type-check + build the static site into dist/

How it's tested

Correctness is pinned by ~90 tests that check each structure against exact ground truth, not just that the code runs:

• MurmurHash3 verified against its published test vectors.
• Filters: the no-false-negative invariant; measured false-positive rates track the theoretical formulas.
• HyperLogLog: cardinality within 3% from 100 to 1,000,000 distinct items; merge behaves as a set union.
• Count-Min: the never-undercount guarantee and the ε·N error bound on skewed streams; conservative update is strictly tighter.
• Top-K (Space-Saving): recovers the true heavy hitters in order; every counter brackets the true count in [c−ε, c]; items above N/K are always kept.
• DDSketch: every quantile within the relative-accuracy guarantee on a fat-tailed stream; exact min/max; merge behaves as a stream union.
• MinHash: Jaccard estimates within tolerance; LSH surfaces near-duplicates.
• Reservoir: uniform sampling confirmed via a chi-square goodness-of-fit test.
• The reactive UI core, chart/grid helpers, every page, and full app boot are covered by jsdom tests.

Architecture

• Zero runtime dependencies. The core structures and the entire UI layer (reactive signals, a hyperscript DOM helper, a hash router, SVG plotting, and a canvas heat-grid) are hand-written and live in this repo.
• Offline-friendly. A static site; the built bundle is ~23 KB gzipped.
• Deployable to GitHub Pages as-is (the build uses a relative base path).

Deploy

npm run build emits a static site into dist/. Push to GitHub with Pages enabled and the included workflow at .github/workflows/ci.yml builds, tests, and deploys it automatically.

Support

Probably is free and MIT-licensed. If it helped you learn something or ship something, you can chip in:

• ☕ Ko-fi
• 💜 GitHub Sponsors

Or star the repo and share it with someone wrestling with a big-data counting problem.

License

MIT — see LICENSE. Built to be read and forked.