Theta sketches: set algebra over massive streams

Most engineers encounter cardinality estimation the same way: they get paged because a COUNT(DISTINCT user_id) query is killing the database, and someone suggests HyperLogLog. HLL solves the “how many unique things” problem elegantly, and for a large class of systems that is enough. But then the analytics team asks something different: “How many users saw campaign A but not campaign B?” or “What is the overlap between users who clicked this ad and users who made a purchase?” Suddenly HLL stops being enough. You need set algebra over streams, and that is where Theta sketches earn their place.

This article goes deep on how Theta sketches work, where they came from, and how to use them correctly in production. The math is not skipped, but the focus is on the intuitions that actually matter when you are building systems.

The problem that cardinality sketches solve

At small scale, counting distinct elements is a solved problem. Load the data into memory, use a hash set, and read off the size. At large scale this falls apart fast. A hash set of 100 million 64-bit user IDs costs roughly 800 MB, and that is before you account for load factors and memory fragmentation in real hash table implementations. If you are running this across a distributed system with many such queries in flight simultaneously, the memory cost becomes a serious constraint.

The deeper problem is that hash sets are not mergeable in any useful way. If you have two partitions of data and you want the combined distinct count, you have to take the union of the two hash sets, which is O(n) in space and requires moving potentially huge sets around the network. For a distributed system processing terabytes per day, this is not a viable path.

Streaming algorithms — or sketches — solve this by making a different trade: accept a small, bounded error in exchange for fixed memory consumption and full mergeability. A sketch occupies a few kilobytes regardless of whether it has seen a thousand or a billion distinct elements. Multiple sketches can be merged in constant time with no accuracy penalty. And crucially, the error is mathematically bounded, not just “probably fine.”

Where Theta sketches came from

The intellectual lineage of Theta sketches goes back to the k Minimum Values (KMV) algorithm, which itself draws on work by Broder in 1997 on estimating set similarities via min-wise hashing. KMV is a beautiful, simple idea: hash every element to a uniform value in [0, 1), keep the k smallest hash values you have seen, and estimate the cardinality as (k-1) / V(kth), where V(kth) is the k-th smallest hash value in the retained set.

The intuition behind KMV is direct. If you sample uniformly from a population and keep the k smallest values, those values will concentrate near the bottom of the [0, 1) range. The (k+1)-th smallest value represents roughly the point where you have sampled enough of the space to estimate the total population. If that value is 0.01, it means about 1% of the hash space is covered by k samples, so the total population is approximately k / 0.01 = 100k.

This works, but KMV in its raw form conflates several distinct roles for the parameter k: it controls both the precision of the estimate and the size of the retained set, and V(kth) serves both as the boundary for what to retain and as the raw material for the cardinality estimate. These roles being entangled makes it hard to build set operations cleanly.

The Theta Sketch Framework, introduced in a 2016 ICDT paper by Dasgupta, Lang, Rhodes, and Thaler, separates these concerns by introducing a dedicated variable: theta ($\theta$). This is the key insight that makes the whole framework possible.

The theta variable and what it buys you

A Theta sketch is a pair (theta, S), where theta is a sampling threshold between 0 and 1, and S is the set of all hashed values less than theta that the sketch has retained. The cardinality estimate is |S| / theta. That is it. The entire construction rests on this.

When a sketch is initialized, theta = 1.0. Every element hashed to a value in [0, 1) is less than theta, so everything is retained. The sketch is in exact mode: it holds every distinct element it has seen, and the estimate is just |S|, which is exact with no error.

As the sketch accumulates elements and |S| exceeds the configured nominal entries k, theta is reduced to the (k+1)-th smallest hash value observed so far. Elements with hash values >= theta are dropped. The sketch transitions into estimation mode. From this point forward, only elements with hash values < theta are retained, keeping |S| at approximately k entries. The estimate |S| / theta remains unbiased.

This is why the variable is called theta — it functions as a dynamic sampling rate. When theta = 0.1, the sketch retains roughly 10% of elements, and dividing the count by 0.1 recovers the estimated total. The error of the estimate is determined entirely by how many entries are retained: the relative standard error (RSE) is approximately 1 / sqrt(k - 1). For k = 4096, that is about 1.6%. For k = 16384, it drops to about 0.8%.

The separation of theta from k also means sketches can be configured once and operate correctly across all cardinality ranges without any mode-switching logic in user code.

How KMV relates to Theta and why it matters

KMV sketches are a special case of Theta sketches. In a KMV sketch, the role of theta is implicitly played by V(kth). The Theta Sketch Framework generalizes this by making theta explicit and independent. This might seem like a cosmetic change, but it has deep practical consequences.

The key consequence is that set operations become straightforward to define and implement correctly. In the KMV formulation, merging two sketches requires reconciling two different interpretations of k. In the Theta formulation, merging is defined purely in terms of the theta variable and the set of retained entries.

The framework also enables a range of sketch variants — the Alpha sketch for improved accuracy during updates, the QuickSelect sketch for production use — all sharing the same set operation logic because they conform to the same abstract (theta, S) definition.

Set operations: the thing that makes Theta sketches irreplaceable

This is the core value proposition, and it is worth understanding in detail.

Union is the simplest operation. Given two sketches A = (theta_A, S_A) and B = (theta_B, S_B), the union sketch is:

theta_result = min(theta_A, theta_B)
S_result = { x : x in S_A or x in S_B, and x < theta_result }

You take the smaller theta (the more aggressive sampling rate) and retain entries from both sketches that fall below that threshold. The estimate is |S_result| / theta_result. This is correct because both sketches sampled from the same hash space: any element with a hash value below both thresholds was retained by both sketches, and by taking the union of retained entries below the minimum theta, you account for all elements that would have been sampled by the combined sketch.

Intersection is more subtle. Given sketches A and B, the intersection sketch is:

theta_result = min(theta_A, theta_B)
S_result = { x : x in S_A and x in S_B, and x < theta_result }

The same theta rule applies. You keep only entries present in both retained sets, below the minimum theta. The estimate is |S_result| / theta_result. This is unbiased because elements that appear in both original streams were independently hashed to the same value (same hash function, same seed) and retained or discarded based on the same threshold.

Difference (A not B) follows analogously: keep entries present in S_A but not in S_B, below the minimum theta.

The critical property that makes this all work is that the hash function is deterministic and universal. If a user appears in both stream A and stream B, their ID hashes to the same value in both sketches. Whether they appear in S_A depends on whether hash(user_id) < theta_A. Whether they appear in S_B depends on whether hash(user_id) < theta_B. By filtering both sets to the minimum theta, you ensure that elements below the threshold were subject to the same sampling decision in both sketches, making the set operations meaningful.

The result of any set operation is itself a valid Theta sketch. This means you can compose operations arbitrarily. A query like ((A union B) intersect (C union D)) minus (E union F) is expressed as a sequence of sketch operations, each producing a sketch that feeds the next. This is not possible with HLL.

Here is what this looks like in Java using Apache DataSketches:

import org.apache.datasketches.theta.*;

int k = 4096;

UpdateSketch sketchA = Sketches.updateSketchBuilder().setNominalEntries(k).build();
UpdateSketch sketchB = Sketches.updateSketchBuilder().setNominalEntries(k).build();

// Feed elements into sketches
for (long userId : campaignAUsers) { sketchA.update(userId); }
for (long userId : campaignBUsers) { sketchB.update(userId); }

// Union
Union union = Sketches.setOperationBuilder().setNominalEntries(k).buildUnion();
union.union(sketchA);
union.union(sketchB);
CompactSketch unionResult = union.getResult();

// Intersection
Intersection intersection = Sketches.setOperationBuilder().buildIntersection();
intersection.intersect(sketchA);
intersection.intersect(sketchB);
CompactSketch intersectResult = intersection.getResult();

// A not B
AnotB anotb = Sketches.setOperationBuilder().buildANotB();
CompactSketch diffResult = anotb.aNotB(sketchA, sketchB);

System.out.println("Union estimate: " + unionResult.getEstimate());
System.out.println("Intersection estimate: " + intersectResult.getEstimate());
System.out.println("A not B estimate: " + diffResult.getEstimate());
System.out.println("Upper bound (2 sigma): " + intersectResult.getUpperBound(2));
System.out.println("Lower bound (2 sigma): " + intersectResult.getLowerBound(2));

And in Python:

import datasketches

k = 4096

sketch_a = datasketches.update_theta_sketch(k)
sketch_b = datasketches.update_theta_sketch(k)

for user_id in campaign_a_users:
    sketch_a.update(user_id)

for user_id in campaign_b_users:
    sketch_b.update(user_id)

# Union
u = datasketches.theta_union(k)
u.update(sketch_a)
u.update(sketch_b)
union_result = u.get_result()

# Intersection
i = datasketches.theta_intersection()
i.update(sketch_a)
i.update(sketch_b)
intersection_result = i.get_result()

# A not B
anotb = datasketches.theta_a_not_b()
diff_result = anotb.compute(sketch_a, sketch_b)

print(f"Union: {union_result.get_estimate():.0f}")
print(f"Intersection: {intersection_result.get_estimate():.0f}")
print(f"A not B: {diff_result.get_estimate():.0f}")

Exact mode and estimation mode

One property worth internalizing is the transition between exact and estimation mode. When a sketch has seen fewer distinct elements than its configured k, theta remains at 1.0 and |S| equals the exact count. There is zero error. The RSE guarantee only kicks in once the sketch transitions to estimation mode.

In the DataSketches library, you can check which mode the sketch is in:

boolean isEstimating = sketch.isEstimationMode(); // theta < 1.0 and not empty

This matters for systems that pre-compute and store sketches. If a sketch is in exact mode, you know the estimate is precise. If it is in estimation mode, you apply the RSE guarantee. Systems that need to report confidence intervals should always call getUpperBound() and getLowerBound() rather than just getEstimate(), because the estimate is a point in a distribution, not a hard value.

Accuracy degradation with intersections

The most important non-obvious property of Theta sketches is that intersection accuracy degrades as the intersection becomes small relative to the union.

The RSE of an intersection estimate is approximately:

RSE_intersection = sqrt(F) * RSE_base

where F is the ratio of the union cardinality to the intersection cardinality: F = |A union B| / |A intersect B|.

To put numbers on this: if k = 4096 giving RSE_base = 1.6%, and you are intersecting two sets of 1 million elements with an overlap of only 1000, then F = (2M - 1000) / 1000 which is approximately 2000. The intersection RSE would be sqrt(2000) * 0.016 which is roughly 71%. That is a meaningless estimate.

The intuition is clear: intersection works by finding common hash values below the minimum theta. If theta is 0.001 (because one set has a million elements), only 0.1% of elements are retained. If the intersection has only 1000 elements, you expect to retain roughly 1 element in the intersection sketch. Estimating a population from a single sample has enormous variance.

LinkedIn ran into this directly when building audience reach estimation for advertisers in Pinot. They confirmed that intersections with cardinality far smaller than either input set had unacceptably high error. Their workaround was to shard the larger dataset to reduce the disparity between shard sizes and the target set.

The actionable rules:

• Always call getUpperBound() and getLowerBound() to understand the error range before trusting an intersection estimate.
• If the intersection is expected to be much smaller than the inputs, increase k substantially, or pre-filter data to reduce the union cardinality before sketching.
• Successive intersections compound the problem. Each intersection reduces the retained entries further. After a few chained intersections on small overlaps, the retained set can reach zero, making estimation impossible.
• Do not use intersection on low-overlap sets where precision matters. If you need an exact count for a niche audience segment, exact methods are the right tool.

The seed problem and why you cannot ignore it

Hash seeds are a detail that bites engineers who skip the documentation.

Theta sketches must use the same hash seed across all sketches that will participate in a set operation. The correctness of intersection and difference depends on the fact that a given element hashes to the same value in both sketches. If two sketches were created with different seeds, the hash values are different for the same input, and the set operations produce nonsense.

The DataSketches library uses a default seed of 9001. If you use the default everywhere, this is not a problem. The moment you introduce a custom seed — perhaps for security reasons, to prevent hash flooding — you must be disciplined about propagating that seed to all sketches and set operation builders.

The library validates this at operation time: it will throw if the seeds do not match. This is a good safeguard, but it means you cannot mix sketches from different systems unless they were created with the same seed. If you are reading sketches serialized by one service and combining them with sketches from another, coordinate on the seed before deployment.

Also: do not change the seed after you have stored sketches. There is no migration path. Old sketches hashed with the old seed cannot participate in set operations with new sketches using a new seed.

Serialization and the updatable vs. compact distinction

Theta sketches exist in two forms: updatable and compact.

An updatable sketch has an internal hash table with extra capacity to handle collisions and growth. It accepts new updates but uses more memory. The overhead is typically 2 to 4x the size of the retained entries.

A compact sketch is the serialized, read-only form. It strips out the hash table overhead and stores only the retained entries and the theta value. A compact sketch is what you serialize to disk or send over the network. It cannot accept new updates but is significantly smaller.

The typical pattern in a batch system:

// Build the updatable sketch while ingesting
UpdateSketch updateSketch = Sketches.updateSketchBuilder().setNominalEntries(k).build();
for (long id : stream) { updateSketch.update(id); }

// Convert to compact for storage
CompactSketch compact = updateSketch.compact(true, null); // ordered=true, dst=heap

// Serialize to bytes
byte[] bytes = compact.toByteArray();

// Later: deserialize and merge
CompactSketch loaded = Sketches.heapifyCompactSketch(Memory.wrap(bytes));
Union union = Sketches.setOperationBuilder().buildUnion();
union.union(loaded);

Binary format compatibility is not guaranteed across different sketch libraries. A sketch serialized by Apache DataSketches Java will not deserialize correctly if you try to interpret it using a different library with its own binary format. The DataSketches library itself maintains cross-language compatibility (Java, C++, Python, Rust, Go), so if you standardize on DataSketches across your stack, you can safely share serialized sketches. But do not assume you can exchange sketches with Druid’s native HLL implementation or any other tool that has its own sketch format.

Memory trade-offs vs. HLL and CPC

The honest comparison among cardinality sketch families:

• HLL sketches are the most compact for pure cardinality estimation. For a given accuracy target, HLL uses 2 to 16 times less memory than a Theta sketch of equivalent k. If all you need is COUNT(DISTINCT) and merging, HLL is the right choice.
• CPC sketches (Compressed Probabilistic Counting) beat HLL by another 30-40% in space efficiency at the same accuracy. CPC is what you use when you have millions of pre-computed cardinality sketches and storage is a hard constraint.
• Theta sketches use more memory than HLL but provide the full set algebra (union, intersection, difference). At equivalent accuracy parameters, a Theta sketch at the default size of 16384 entries uses roughly 30 times more memory than an HLL sketch with lgK = 12. This is not a small gap.

The decision rule is not subtle: if you need intersection or difference, use Theta. If you only need union and distinct count, use HLL or CPC and save the memory.

In Druid and Pinot, which have native DataSketches integration, this means you may want different sketch types for different columns depending on the query patterns. A user-id column queried only for COUNT(DISTINCT) should use HLL. A campaign-id column queried for audience overlap should use Theta.

Tuple sketches: beyond cardinality

The Theta sketch family includes an extension called Tuple sketches. A Tuple sketch attaches a summary object to each retained hash entry. That summary can hold arbitrary values: counters, arrays of doubles, sets of strings.

This turns Theta sketches from a pure cardinality tool into a general framework for aggregating data about distinct entities. A canonical example: tracking total revenue and click count per unique user across a distributed system, while still supporting set operations.

In Druid, the arrayOfDoublesSketch aggregator is a Tuple sketch implementation. For each unique user retained in the sketch, it stores an array of doubles (e.g., revenue, clicks, impressions). Set operations over Tuple sketches propagate these summary values, giving you not just “how many users are in the intersection” but also “what is the total revenue of users who appear in both cohorts.”

// Pseudocode for a tuple sketch with revenue and click count per user
ArrayOfDoublesUpdatableSketch tupleSketch = new ArrayOfDoublesUpdatableSketchBuilder()
    .setNominalEntries(k)
    .setNumberOfValues(2)
    .build();

// Associate user ID with [revenue, clicks]
tupleSketch.update(userId, new double[]{revenue, clicks});

// After set operations, extract summaries
ArrayOfDoublesSketch result = intersection.getResult();
double[] sums = result.getSummary(); // aggregated across retained entries

The tradeoff is that Tuple sketches are larger than plain Theta sketches, proportional to the size of the summary data stored per entry.

Real-world usage patterns

The companies using Theta sketches at scale share a common pattern: pre-compute and store sketches at ingestion time, then combine them at query time.

Yahoo built DataSketches internally to handle audience analytics for their advertising business. Queries that previously took hours with exact computation ran in seconds using pre-computed sketches. Their Flurry platform used Theta sketches to provide real-time unique user counts for mobile apps within 15 seconds of events occurring.

LinkedIn integrated Theta sketches into Apache Pinot to power advertiser reach estimation. Their problem was computing audience cardinality for complex targeting criteria: users in specific countries, with specific skills, at specific companies. Exact count-distinct over intersections of large advertiser audiences was too slow. With pre-computed Theta sketches per dimension value, they could evaluate complex boolean expressions over sketch set operations at query time.

Apache Druid and Pinot both support Theta sketches natively through the DataSketches integration. In Druid, you configure a Theta sketch aggregator during ingestion, and the sketches are stored in segments. At query time, Druid’s SQL layer surfaces THETA_SKETCH_ESTIMATE, THETA_SKETCH_UNION, THETA_SKETCH_INTERSECT, and related functions. This means you can push set algebra into SQL queries without any application-level sketch handling:

-- Count users who appeared in both campaign A and campaign B
SELECT
  THETA_SKETCH_ESTIMATE(
    THETA_SKETCH_INTERSECT(
      APPROX_COUNT_DISTINCT_DS_THETA(user_id) FILTER (WHERE campaign = 'A'),
      APPROX_COUNT_DISTINCT_DS_THETA(user_id) FILTER (WHERE campaign = 'B')
    )
  ) AS overlap_estimate
FROM events
WHERE event_date >= '2026-01-01'

In practice, for high-cardinality dimension tables, teams pre-compute sketches per dimension value in a batch job and store them in a key-value store or columnar format. Query time then becomes pure sketch merge operations with no raw data scanning.

When not to use Theta sketches

Theta sketches are not the right tool in several common situations.

If the intersection you care about is tiny relative to the input sets, the error will be unacceptable. This is not a tunable parameter you can work around by increasing k — the fundamental issue is that very few hash values fall in the intersection, giving you almost no samples to estimate from. Exact methods or different query decompositions are better here.

If storage is extremely tight and you only need cardinality plus union, HLL or CPC are the correct choice. Theta sketches use 30x more memory than HLL at equivalent accuracy. That memory cost is the price you pay for set operations. If you are not using set operations, you are paying for something you do not need.

Theta sketches cannot answer membership queries. Given a sketch, you cannot determine whether a specific element was in the original stream. The retained hash values are deterministic but the sketch does not store which original elements produced them (for large inputs with small theta, most elements are dropped entirely). If you need probabilistic membership testing, Bloom filters are the right tool.

Chained intersections kill accuracy fast. If your query plan requires three or four intersections in sequence, each one reduces the retained entries, and the error compounds multiplicatively. Restructure the query to take unions first and intersections last where possible, and validate error bounds at each step.

Theta sketches do not support weighted inputs natively. If each element in your stream has an associated weight and you want weighted distinct counts, you need a different approach — possibly a Tuple sketch with custom summary aggregation, or a different algorithm entirely.

Sizing and tuning in production

The nominal entries parameter k controls the accuracy-memory trade-off. The RSE formula 1 / sqrt(k - 1) lets you compute the required k directly from your accuracy target:

k = (1 / RSE)^2 + 1

For 1% RSE: k = 10001, so use 16384 (nearest power of two). For 2% RSE: k = 2501, so use 4096. For 5% RSE: k = 401, so use 512.

Each retained entry is a 64-bit long (8 bytes). At k = 4096 with the default compact format, a sketch uses roughly 32 KB plus a small fixed header. At k = 16384, that is 128 KB plus header. In a system that pre-computes one sketch per dimension value per day, with 1000 dimension values over a year, at k = 4096: 365 * 1000 * 32 KB = roughly 12 GB of sketch storage. Manageable. At k = 16384 the same scenario is roughly 48 GB. Still manageable. The cost grows linearly with the number of sketches, not with the cardinality of the data they represent.

For intersection-heavy workloads, increase k beyond what the RSE formula suggests for the base cardinality. The intersection error amplification by sqrt(F) means you need more retained entries to achieve the same accuracy on intersection estimates as you would on a direct cardinality estimate.

A note on the Alpha sketch

The DataSketches library ships two flavors of updatable Theta sketch: QuickSelect and Alpha.

QuickSelect is the production default. It uses a QuickSelect algorithm to find the k-th smallest value when the internal buffer needs to be trimmed, and it has tight, predictable performance characteristics.

Alpha is a research variant that achieves lower error during updates (roughly half the RSE of QuickSelect at the same k) by using a more sophisticated estimation technique. The catch is that this benefit vanishes once the sketch is converted to compact form for set operations. The Alpha sketch is useful when you are building a sketch once and reading the cardinality estimate from it directly without any merging. If your workflow involves storing sketches and combining them later, Alpha offers no advantage over QuickSelect.

Summary

Theta sketches solve the problem that HyperLogLog cannot: set algebra (union, intersection, difference) over probabilistic cardinality estimates. They generalize the KMV algorithm by decoupling the sampling threshold theta from the retained-entry count k, which makes set operations well-defined and composable. The price is higher memory than HLL — roughly 30x at equivalent accuracy — but that cost is justified when intersection queries are part of your system’s contract.

The most important operational reality is that intersection accuracy degrades sharply when the intersection cardinality is small relative to the union. Always query error bounds, not just point estimates. Size k based on the expected intersection cardinality, not the input cardinalities. Keep the hash seed stable across all services that will exchange sketches. Pre-compute at ingestion time and merge at query time — that is the architecture that makes Theta sketches genuinely fast in production. Tools like Druid and Pinot make this pattern accessible through native SQL functions, removing the need to handle sketch serialization manually.

---

Theta sketches are probabilistic data structures that estimate set cardinalities (union, intersection, difference) over large streams using a fixed-size sample of hashed values and a dynamic sampling threshold called theta. Derived from the KMV algorithm and formalized in the 2016 Theta Sketch Framework paper, they trade 30x more memory than HyperLogLog for the ability to compose full set expressions. Accuracy is bounded by 1/sqrt(k-1) for direct estimates but degrades as sqrt(F) for intersections where F is the union-to-intersection ratio. Apache DataSketches is the canonical implementation, integrated natively into Druid, Pinot, PostgreSQL, and BigQuery.