Theta Sketch Tutorial

Mix.install([
  {:ex_data_sketch, "~> 0.10"}
],
config: [
    ex_data_sketch: [
      backend: ExDataSketch.Backend.Rust,
      integrations: [opentelemetry: false]
    ]
  ])

Introduction

ExDataSketch.Theta keeps the k smallest hash values it has seen below a moving threshold ("theta"). Once more than k items pass the threshold, theta drops and the largest retained hashes are evicted -- so the sketch always holds a uniform random sample of the full hashed item space below theta, and cardinality ~= retained_count / theta. Because that sample is a real subset of the input's hashes, two sketches' samples can be combined directly -- that's what makes set operations possible where HLL/ULL can only merge (union):

flowchart LR
    A[item] --> B["hash(item)"]
    B --> C{"hash < theta\nthreshold?"}
    C -->|no| D[discard]
    C -->|yes| E["add to retained set"]
    E --> F{"retained > k?"}
    F -->|yes| G["lower theta,\nevict largest hashes"]
    F -->|no| H["estimate =\nretained_count / theta"]
    G --> H

Use it for: distinct-count plus set operations between sketches -- "how many users used both feature A and feature B," "how many users are in set A but not set B" -- via merge/2 (union) and the inclusion-exclusion combinations shown below, without ever materializing either full set.

Don't use it for: plain distinct-count with no set-operation need -- ExDataSketch.HLL/ExDataSketch.ULL pack far more accuracy per byte for that alone, since Theta retains a full 8-byte hash per entry rather than a compact one-byte register. Also not for exact set operations -- intersection/difference here are still estimates, with the same error budget as the underlying cardinality estimate.

What it buys you: at the default k: 4096, a sketch retains at most 4096 8-byte hashes (~32 KB fixed) with roughly 1.6% relative error (~1/sqrt(k), the standard bound for this sketch family) -- and unlike two independently-built exact sets, you never need to hold either input in full to compute the overlap:

Approach	Memory (per sketch, k=4096)	Set ops	Error
Exact sets (two `MapSet`s)	Grows with input size	Exact	0
`ExDataSketch.Theta` (k=4096)	~32 KB, fixed	union/intersect/difference	~1.6%

Sample data (cached locally)

Set A: users 1..600,000 (600K users). Set B: users 400,001..1,000,000 (600K users). True intersection: users 400,001..600,000 (200K users). True union: users 1..1,000,000 (1,000,000 users).

{users_a, users_b} = ExDataSketch.SampleData.theta_sets()
IO.puts("Set A: #{length(users_a)} users, Set B: #{length(users_b)} users")
IO.puts("True union: 1,000,000; true intersection: 200,000")

Basic usage

alias ExDataSketch.Theta

sketch_a = Theta.from_enumerable(users_a, k: 16_384)
sketch_b = Theta.from_enumerable(users_b, k: 16_384)

IO.puts("|A| estimate: #{Float.round(Theta.estimate(sketch_a), 0)} (true: 600,000)")
IO.puts("|B| estimate: #{Float.round(Theta.estimate(sketch_b), 0)} (true: 600,000)")

Set operations via inclusion-exclusion

merge/2 gives you the union directly. Intersection and difference come from combining the union estimate with the two individual estimates:

|A ∪ B| = |A| + |B| - |A ∩ B|      =>  |A ∩ B| = |A| + |B| - |A ∪ B|
|A \ B| = |A| - |A ∩ B|

union_sketch = Theta.merge(sketch_a, sketch_b)
union_estimate = Theta.estimate(union_sketch)

a_estimate = Theta.estimate(sketch_a)
b_estimate = Theta.estimate(sketch_b)

intersection_estimate = a_estimate + b_estimate - union_estimate
a_not_b_estimate = a_estimate - intersection_estimate

IO.puts("Union estimate: #{Float.round(union_estimate, 0)} (true: 1,000,000)")
IO.puts("Intersection estimate: #{Float.round(intersection_estimate, 0)} (true: 200,000)")
IO.puts("A \\ B estimate: #{Float.round(a_not_b_estimate, 0)} (true: 400,000)")

This is approximate in both directions -- union_estimate already carries HLL-style estimation error, and the subtraction can amplify it (especially when the intersection is small relative to either set). It's still far cheaper than computing an exact MapSet.intersection/2 on two potentially enormous sets.

Precision (`k`) and accuracy

Like HLL's p, Theta's k trades memory for accuracy -- larger k means more retained entries and a tighter estimate:

for k <- [1024, 4096, 16_384] do
  s = Theta.from_enumerable(users_a, k: k)
  error_pct = abs(Theta.estimate(s) - 600_000) / 600_000 * 100
  IO.puts("k=#{k} (#{Theta.size_bytes(s)} bytes): error=#{Float.round(error_pct, 2)}%")
end

Serialization

binary = Theta.serialize(sketch_a)
{:ok, restored} = Theta.deserialize(binary)
IO.puts("Round-tripped estimate: #{Float.round(Theta.estimate(restored), 0)}")

Theta also has a compact/1 step and Apache DataSketches interop (serialize_datasketches/2) -- see guides/apache_interop.md for reading sketches produced by the Java/C++/Python DataSketches library and vice versa.