Apache DataSketches: A Guide to Sketch Types

In the previous article, we discussed about how to use Apache DataSketch in Scala and looked at the sketchprobe tool to view the contents of a sketch in readable format.

This article gives a summary and overview of different sketch types. Consider this as a datasketch cheatsheet to get an overview.

There are over 20 types of sketches across 5 families. The sketches in the same family solves more of less the same problems. In other words, the sketches in a family answers one type of question.

1. Cardinality: How many distinct things?

This family gives the estimates about the cardinality or distinct counts of values/keys.

Sketch	Idea	Special ability	Trade-off
HLL	Keeps small registers that record how rare the hashes it has seen are.	Smallest and fastest. Can be merged (union).	Counts only. No direct intersection or difference, and it cannot list items.
Theta	Keeps the k smallest hash values it has seen.	Set operations: union, intersection, and difference (A − B).	Uses more memory than HLL for the same accuracy.
CPC	Does the same job as HLL, but uses a compressed representation.	Better accuracy per byte than HLL (about 40% smaller in some configurations).	Slower, and the internal representation is more complex.
Tuple	Theta-like sketch with an associated summary value attached to each retained key.	Tracks distinct items along with associated data, such as total spend per user.	The value type is not stored in the serialized sketch; the application must know how to interpret it.

How to choose? If you only need a count, use HLL (or CPC for more compactness). If you need to ask "how many users are in both A and B", use Theta. If each user also carries a number, use Tuple.

Example use cases:

• Website analytics - Estimate the number of unique visitors per day.
• Infrastructure monitoring: Estimate the number of unique IP addresses seen across billions of log records.

2. Percentiles: What's the median or p99?

This family estimates percentiles of a stream of numbers, helping you understand the distribution of your data.

Sketch	Error guarantee	Item types	Notes
Quantiles (classic)	Uniform rank error across the distribution	double	Older design. The parameter k must be a power of two.
KLL	Uniform rank error across the distribution	float, double, long, strings (depending on implementation)	More space-efficient than the classic quantiles sketch for comparable accuracy. k does not need to be a power of two.
REQ	Relative rank accuracy focused on either the high or low tail	float	Useful for tail-focused queries, such as p99.9. You choose which end to prioritize.
t-Digest	No strict, general-purpose rank-error guarantee	double	A separate sketch design. Often compact and effective at estimating extreme quantiles, but its accuracy is empirical rather than guaranteed.

In short: KLL replaces Quantiles for new code, REQ is for extreme tails, and TDigest is a pragmatic alternative with no formal bound.

Example use case:

• API latency analysis: Understand response-time distributions, such as p50 (median), p95, and p99 latency.
• E-commerce analytics: Calculate the median purchase value during a campaign to understand typical customer spending.

3. Frequency: What are the most frequent items?

This family identifies items that occur frequently in a data stream and estimates their frequencies without storing every occurrence.

Sketch	Keeps the keys?	Answers
Frequency (Frequent Items)	Yes: it stores the heavy hitters themselves.	"What are the top 20 platforms?" with an error bound.
Count-Min	No: it stores only a grid of counters.	"How many times did key X appear?" for any queried key. It never underestimates the frequency.

Frequency tells you what is popular(heavy hitters). CountMin can only tell you how often a key you already know appeared.

Example use case:

• Browser analytics: Estimate how many requests came from a each browsers
• Log analysis: Estimate the frequency of a specific error code across millions of log entries.

4. Sampling: Give me a sample of the data

This family maintains a representative sample of a large data stream without storing every record.

Sketch	What it does
Reservoir	Maintains a fixed-size, uniformly random sample of items.
VarOpt	Maintains a sample of weighted items, optimized so that sums over subsets (e.g., "revenue for customers in Germany") can be estimated accurately.
EBPPS	Maintains a weighted sample with exact inclusion probabilities for each item.

Unlike the other groups, these hold real items, so the original data is visible.

Example use case:

• E-commerce: Study a sample of purchase transactions to understand customer buying behavior
• Customer analytics: Analyze a sample of customers to understand demographics, spending patterns, or purchasing habits.

5. Existence: Have I seen this value before?

This family checks whether a value has been seen before or belongs to a set, helping detect duplicates efficiently without storing every item.

Sketch	Idea	Special ability	Trade-off
Bloom Filter	Uses a bit array and multiple hash functions to represent a set.	Checks whether an item may have been seen before, with a configurable false-positive rate.	Can report false positives, but standard Bloom filters have no false negatives for inserted items. Cannot list stored items.
Xor Filter	Stores a compact fingerprint for each item using an XOR-based structure.	Efficient membership checks with a low false-positive rate and compact storage.	Typically built for a fixed set of items; adding new items generally requires rebuilding the filter.

Bloom and Xor filters answer yes or no for one value. They don't count or estimate anything.

Example use case:

• Database optimization: Check whether a value might exist before performing an expensive database lookup.
• Network security: Quickly check whether an IP address belongs to a known blocklist using a compact filter.

What kind of data is stored in the blob?

Group	What the blob stores
HLL, CPC	Compact summaries used to estimate distinct counts. Some small HLL sketches may store hashed values in list or set mode. Original values cannot be recovered.
Theta	Hashes of retained distinct values, not the original values themselves.
Tuple	Hashes of retained keys, plus associated summary values for each retained key.
KLL, Quantiles, REQ	A sample of the original numerical values, plus compact summary information used to estimate quantiles. Not the entire dataset.
Frequency (Frequent Items)	Candidate item keys and frequency-related counters or estimates. Items are encoded using a serializer (serde).
Reservoir	The actual sampled items, encoded using a serializer (serde).
VarOpt	The actual sampled items, their weights, and sampling-related information, encoded using a serializer (serde).
Bloom Filter	A bit array representing set membership. Original values cannot be recovered.
XOR Filter	A compact fingerprint-based structure for set membership. Original values cannot be recovered.
Count-Min Sketch	A grid of counters used to estimate item frequencies. Original item identities cannot be recovered from the sketch alone.