theta-sketch · shipping

Theta sketch

A Theta sketch retains hashed distinct values below a sampling threshold to estimate set sizes and combinations of sets.

The state includes a threshold theta and the retained hashes. The estimate is retained count divided by theta; theta=1 gives an exact count in the hashed domain. Compatible sketches can estimate unions, intersections and set differences. The framework's unbiasedness result assumes a suitable threshold rule and ideal random hashing. [1]

An intersection uses the smaller input threshold and retains common hashes below it. A small overlap can leave no retained hash. In that state estimate=0 does not certify disjoint inputs: empty=false and theta<1 preserve uncertainty. Query the result's bounds instead of borrowing the input sketch's relative error. [2] [3]

In a native 5.2.0 example, two sets of 10000 integer identities share one value. With lg_k=5 and seed=9001, the intersection estimates zero, but its 2-standard-deviation upper bound is 1092. With lg_k=12 it still estimates zero, with upper bound 5. These are approximate library bounds, not hard maxima. [5]

Preserve theta, the empty flag and hash/encoding compatibility through serialization. Replacing a zero-retained sampled result with a fresh empty sketch discards its uncertainty; the native compact serialization preserves it. A cardinality sketch cannot authorize deletion of individual blocks or establish ingestion completeness. [4] [5]

Relations

related
HyperLogLog, Data deduplication, Sampling design, MinHash, Jaccard similarity

Citations

  1. Dasgupta, Lang, Rhodes and Thaler. A Framework for Estimating Stream Expression Cardinalities. ICDT 2016, sections 2 and 3.7. (accessed 2026-11-20)
  2. Apache DataSketches. Theta Sketch and Tuple Sketch Set Operation Corner Cases: empty and degenerate states. (accessed 2026-11-20)
  3. Apache DataSketches. Theta accuracy plots: error after intersection and difference. (accessed 2026-11-20)
  4. Apache DataSketches C++ 5.2.0: pinned intersection implementation, empty-state and threshold handling. (accessed 2026-11-20)
  5. Hesela. Theta intersections: preserving uncertainty when the sample is empty. Native controls, results and replay. (accessed 2026-11-20)
Sources & caveats
  • Executed Apache DataSketches Python 5.2.0 with synthetic integer ranges; the release source references C++ 5.2.0. Wheel and source hashes are recorded in the replay packet.
  • The 768-run sweep varies a fixed list of seeds over three known overlaps. It is not a random fleet sample, a confidence-bound coverage study or a reproduction of the paper's performance results.
  • Exact mode concerns offered identities and finite hashes. Source completeness, intended identity encoding and cryptographic authenticity need separate checks.

JSON: /data/terms/theta-sketch.json

Published by Hesela team · Updated

Report a correction · Editorial standards · Reuse guidance

Cite this page
Hesela team. Theta sketch. Hesela. 2026-11-20. https://hesela.dev/terms/theta-sketch/