Probabilistic data structures

Bloom — m bits, k hash functions, design capacity n. Shows bits per key, the best k = (m/n)·ln 2, the false-positive rate (FPR) at n and with the best k, and the memory. Live inserts k0, k1, k2…: the bit array lights up (orange rings are bits just set), with the fill, the theoretical FPR, the FPR from the fill (fillᵏ) and the FPR measured on 2,000 keys never added. Type a key to Add, Check (probed bits outlined green when set, red when 0; a "maybe" for a key never added is called out as a false positive) or Delete. Tick Counting Bloom filter for counters of 1–8 bits that allow deletes; counters that saturate are drawn red and can never be decremented again. Charts: FPR as the filter fills (theory and measured), and FPR against bits per key from 2 to 20.

Cuckoo — buckets, entries per bucket b, fingerprint bits f and the kick limit. Live inserts keys until an insert fails; every bucket is drawn with its fingerprints in hex, the new key’s two candidate buckets dashed, and the moves of the last insert numbered and listed ("kick out 0x3a → its other bucket 17"). Load α, bits per key f/α, the FPR bound and the measured FPR. Chart: bits per key against FPR for cuckoo filters filled to failure with 4- to 20-bit fingerprints, against the Bloom filter’s 1.44·log₂(1/ε) and the log₂(1/ε) minimum.

Count-Min — width w, depth d, heavy hitters to keep, and whether to draw the conservative-update sketch (both run side by side). The stream is Zipf(s), uniform or all-distinct over a number of keys, with a seed. The counter grid is drawn as a heat map; Estimate a key to see its d counters outlined and the minimum taken. Shows ε = e/w, δ = e^−d, the εN bound, the mean overestimate for both update rules and the share of keys over εN (it should be at most δ), and a top-k table of true counts against both estimates. Chart: overestimate against width (log–log) with the bound.

HyperLogLog — precision p (16 to 65,536 registers), the estimator shown big, and HLL sparse mode. The registers are drawn as bars (or as a histogram of their values when there are too many); the live panel compares the estimate with the exact distinct count, the standard error 1.04/√m and the memory against an exact set, and a table shows the raw harmonic-mean estimate, linear counting, Flajolet et al.'s switch, HLL's thresholds and Ertl’s estimator. Charts: this run’s error as the count grows (with the ±1.04/√m band), RMSE against the number of registers, and the bias of each estimator against cardinality — the bump where linear counting hands over to the raw estimate.

t-digest — compression δ and a value distribution (log-normal latency, exponential, normal, Pareto, bimodal "cache hit / miss", uniform). Centroids are drawn along the quantile axis: width is a centroid’s share of the data, height its count — tiny at the tails. A table compares p0.1, p1, p25, p50, p90, p99 and p99.9 with the exact values (value and rank error). Chart: rank error at seven quantiles for δ = 20 to 500.

Reservoir — sample size k, stream length N and the algorithm drawn. The slots flash as items replace their occupants; Algorithm R and Algorithm L run side by side so you can compare how many random numbers each draws. Chart: how often each stream position ends up in the sample over 20,000 seeded runs, against k/N, with a χ² statistic.

Hashing: MurmurHash3 x86_32 (checked against the SMHasher reference outputs); two values make a 64-bit hash. Bloom and Count-Min positions use Kirsch–Mitzenmacher double hashing, gᵢ = h₁ + i·h₂ mod m — A. Kirsch and M. Mitzenmacher, "Less Hashing, Same Performance: Building a Better Bloom Filter" (ESA 2006).

Bloom filter: B. H. Bloom, "Space/Time Trade-offs in Hash Coding with Allowable Errors" (CACM 1970). The classic FPR formula is slightly optimistic for small m — P. Bose et al., "On the false-positive rate of Bloom filters" (IPL 2008). Counting Bloom filters and the overflow bound m·(e·ln 2/i)^i: L. Fan, P. Cao, J. Almeida and A. Broder, "Summary Cache" (IEEE/ACM ToN 2000).

Cuckoo filter: B. Fan, D. G. Andersen, M. Kaminsky and M. Mitzenmacher, "Cuckoo Filter: Practically Better Than Bloom" (CoNEXT 2014) — partial-key cuckoo hashing, 500 kicks, a victim slot, ε ≤ 2b/2^f, and maximum loads of about 50%, 84%, 95% and 98% for b = 1, 2, 4, 8.

Count-Min sketch: G. Cormode and S. Muthukrishnan, "An Improved Data Stream Summary: The Count-Min Sketch and its Applications" (J. Algorithms 2005). Conservative update: C. Estan and

HyperLogLog: P. Flajolet, É. Fusy, O. Gandouet and F. Meunier, "HyperLogLog: the analysis of a near-optimal cardinality estimation algorithm" (AofA 2007). HLL++: S. Heule, M. Nunkesser and

t-digest: T. Dunning and O. Ertl, "Computing Extremely Accurate Quantiles Using t-Digests" (arXiv:1902.04023, 2019) — the merging variant with the k₁ scale function.

Reservoir sampling: J. S. Vitter, "Random Sampling with a Reservoir" (ACM TOMS 1985), Algorithm R; K.-H. Li, "Reservoir-Sampling Algorithms of Time Complexity O(n(1 + log(N/n)))" (ACM TOMS 1994), Algorithm L.

Streams are synthetic (Zipf, uniform or distinct ids as strings k0, k1…); nothing reads your data. Sizes are capped so the page stays responsive: Bloom filters to 2 million bits in the page, HyperLogLog to p = 16, Zipf universes to a million keys.

HLL here has no bias-correction tables, and sparse entries are counted at 4 bytes each rather than HLL's varint-delta encoding; the memory shown is the ideal 6 bits per register.

The t-digest is the merging variant with k₁ only (no k₂/k₃ scale functions, no AVL-tree variant); quantiles interpolate between centroid centres as in the paper.

Measured false-positive rates come from a few thousand probes, so small rates are noisy in the live view; the sweep charts use 20,000–40,000 probes.