Choose a sketch
You need an answer over a large stream or table, say distinct users per day, the most frequent items, or p99 latency, and keeping every value is too expensive. A sketch keeps a small summary instead and trades exactness for space. Each kind of question has one right family and several wrong ones. Which one do you need, and do you need one at all?
You will end with the sketch family for your question, or the decision to stay exact, and the properties it must have in your pipeline.
Decide
Can you afford the exact answer?
Compute the cost. Below a few million items, an exact hash set is usually cheaper than understanding a sketch.
YesStay exact
NoGo to 2
Why
A sketch's error falls only as 1 ÷ √(memory): four times the memory buys half the error. Accuracy is expensive, so make sure you need to spend it.
What exactly is the question?
Is it there?Filter (Bloom, cuckoo, XOR)
How many distinct?Go to 3
Most frequent?Heavy-hitter sketch (Count-Min, Space-Saving)
What percentile?Go to 4
How similar?MinHash
A sampleReservoir sample
Will anyone ever need to intersect these counts?
Users active on both day 1 and day 2; customers in segment A and B.
PlausiblyTheta sketch
NeverHyperLogLog
Why
HyperLogLog counts distinct items compactly but cannot intersect; estimates by subtraction degrade badly. Paying for Theta now is cheaper than discovering that in a quarterly report.
Where you can land
Stay exact
Use it when the exact answer fits your budget.
What it costs: the space you would have saved, usually still the right trade.
Filter (Bloom, cuckoo, XOR)
Use it when the question is whether an item is in a set.
It may say "maybe present" for an absent item, never "absent" for a present one, so a "no" is safe to act on: use it as a guard that skips work. What it costs: a false-positive budget, and it cannot list what it contains.
HyperLogLog
Use it when you count distinct items and will never intersect them.
What it costs: no intersections; two-sided error.
Theta sketch
Use it when you count distinct items and someone may intersect them.
What it costs: more space per unit of accuracy than HyperLogLog.
Heavy-hitter sketch (Count-Min, Space-Saving)
Use it when the question is which items are most frequent.
Accurate for the head of the distribution. What it costs: blind to the tail; Count-Min only ever overestimates.
t-digest
Use it when you need percentiles, especially high ones.
What it costs: two-sided error, best at the extremes and weaker in the middle.
KLL
Use it when you need percentiles across the whole distribution with a guarantee.
What it costs: less detail in the far tail than t-digest at the same size.
MinHash
Use it when the question is how similar two sets are.
What it costs: an estimate, not an exact similarity; exact all-pairs comparison is quadratic and is what it avoids.
Reservoir sample
Use it when you need a uniform sample of a stream of unknown length.
What it costs: a sample cannot count distinct values, and rare items are mostly missed.
Whichever you land on
Will it be merged?
If sketches from different partitions, days or machines will be combined: the sketch must merge exactly (merging two sketches equals sketching the combined data). That rules out most homemade alternatives.
Can delivery duplicate records?
Bloom filters, HyperLogLog, Theta and MinHash ignore a second copy of an item. Count-Min, Space-Saving, t-digest and reservoir samples count it twice. If your pipeline delivers at least once and the sketch counts: you need deduplication upstream.
Does the error direction suit the use?
One-sided error (filters, Count-Min) suits a guard, where a wrong answer costs only extra work. Two-sided, unbiased error (HyperLogLog, quantile sketches) suits a reported metric. Never put a two-sided sketch where a false negative would silently drop data.
Keep the raw data if you can
A sketch answers only the questions it was built for. A daily rollup of sketches by three dimensions can never answer a question about a fourth. Keeping the raw data alongside costs the space you saved, and keeps the unasked questions answerable.