# Theta Sketch Tutorial

```elixir
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):

```mermaid
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).

```elixir
{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

```elixir
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|
```

```elixir
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:

```elixir
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

```elixir
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.

## See also

* `ExDataSketch.Theta` module documentation -- full API reference.
* `ExDataSketch.HLL`/`ExDataSketch.ULL` -- cardinality-only estimators
  with no set-operation support; use these instead when you only need a
  single count and want the ~30% better accuracy ULL offers at the same
  memory. See `livebooks/sketches/hll.livemd` and
  `livebooks/sketches/ull.livemd`.
* `guides/distributed_merge_semantics.md`,
  `livebooks/distributed_merges.livemd` -- associativity/commutativity
  properties merge relies on.