A probabilistic data structure answers queries about a data set approximately, using space far smaller than the data set, and gives the approximation as a statement about a random choice made by the structure itself: with probability at least over the choice of hash functions or samples, the answer is within of the truth. The randomness is internal. No assumption is made about the distribution of the input, which may be chosen by an adversary who does not see the random choices.
In practice these structures appear where exact answers would require memory proportional to the input: counting distinct users per day in a database’s query planner, finding the most frequent flows on a router, testing whether a key might exist before reading a disk block, or estimating latency percentiles across many servers without shipping every measurement. Most are also mergeable: two summaries of disjoint inputs combine into a summary of the union with the same guarantee, which makes them suitable for distributed aggregation.
Notation
The notes in this series use the following conventions unless they state otherwise.
- Stream. The input is a sequence of updates , , with each item in a universe . In the cash-register model every ; in the turnstile model may be negative. A stream of plain items is the special case .
- Frequency vector. with . Its norms are and . In the cash-register model is the total count.
- Frequency moments. , so is the number of distinct items (with ), , and .
- Accuracy. An guarantee for an estimate of states for a stated scale : for a relative guarantee, or for an additive one.
- Hashing. denotes a hash function drawn from a family . A family is -wise independent if for any distinct keys the values are independent and uniform. Analyses that assume a fully random function say so; the first note of the series concerns when that assumption is justified.
- Logarithms. is the natural logarithm, the base-2 logarithm.
The shared benchmark
The experiments in the series use the 24 hourly Wikimedia pageview files dated 4 March 2026, covering the hours ending 00:00 through 23:00 UTC. They hold records domain_code page_title count_views total_response_size, one record per (project, page, hour) with at least one view after Wikimedia’s filtering of identified spiders and automated agents. The files were read from a public mirror that holds the same files under the same names.
| Quantity | Value |
|---|---|
| Records (stream length, one per page and hour) | 160,961,718 |
| Distinct (project, page) keys, | 60,974,808 |
| Total views, | 445,961,446 |
| Largest (English Wikipedia’s Main Page) | 4,354,576 (0.98% of ) |
| Keys with exactly one view | 58.9% of keys, 8.1% of views |
| Views held by the top , , keys | 9.1%, 32.6%, 57.3% |
| 0.0124 |
The stream has two properties that matter for sketches. It is long enough () to reach the regime where asymptotic bounds should apply, and its frequency distribution is heavy-tailed but flatter than the Zipf distributions often assumed in analyses: the log-log slope of frequency against rank is about 0.75 between ranks 10 and 1000 and about 0.9 to 1.1 beyond rank .
Series
The notes are ordered so that each depends only on earlier ones. Notes without links are planned.
- Hashing for sketches. Universal and -wise independent families, multiply-shift and tabulation hashing, and the gap between the independence an analysis assumes and the hash functions implementations use, measured by running the same sketches on real keys through weak and strong hashes. Sources: Carter and Wegman (1979), Dietzfelbinger et al. (1997), Pătraşcu and Thorup (2012).
- Bloom filters and their variants. The false-positive analysis, partitioned, blocked and counting filters, and double hashing (Kirsch and Mitzenmacher 2008), with measured false-positive rates on the pageview keys and the cost in cache misses per query.
- Cuckoo, quotient, xor and ribbon filters. Filters that approach the bits-per-key lower bound, compared in space, false-positive rate and throughput. Sources: Fan et al. (2014), Bender et al. (2012), Graf and Lemire (2020), Dillinger and Walzer (2021).
- HyperLogLog and Count-Min. Distinct counting and frequency estimation: the estimators and their proofs, the corrections added after the original analyses, and the measured error on the pageview stream against the published bounds.
- Heavy hitters. Misra-Gries, Space-Saving and Count Sketch for the top- problem, with deterministic and probabilistic guarantees compared on the same stream. Sources: Misra and Gries (1982), Metwally et al. (2005), Charikar et al. (2002).
- Quantile sketches. GK, KLL, t-digest, DDSketch and REQ: rank error against relative error, mergeability, and accuracy at the tails on real latency data.
- MinHash and locality-sensitive hashing. Jaccard similarity estimation, b-bit MinHash and banding for near-duplicate detection on Wikipedia article text. Sources: Broder (1997), Indyk and Motwani (1998), Li and König (2010).
- Sampling from streams. Reservoir sampling and Algorithm L, weighted sampling without replacement, and priority sampling for subset-sum estimation. Sources: Vitter (1985), Efraimidis and Spirakis (2006), Duffield, Lund and Thorup (2007).
- Randomized search structures. Skip lists and treaps: expected and high-probability bounds on depth, and measured lookup cost against balanced trees. Sources: Pugh (1990), Seidel and Aragon (1996).
Related notes
- Expectation and concentration, for the Markov, Chebyshev and Chernoff bounds used throughout
- Bloom filters in LSM storage engines
- Algorithms