There is a mature kind of system that begins with a confession.
I am not exact.
Then it tells you something more useful.
Here is what I preserve, here is how much memory I use, and here is how wrong I am allowed to be.
That is the philosophy behind probabilistic sketches.
Quick Read
Probabilistic sketches are compact data structures designed to answer narrow questions approximately using much less memory than exact representations. Different sketches preserve different properties. Bloom filters preserve approximate membership. Count-Min Sketch preserves approximate frequencies. HyperLogLog preserves approximate cardinality.
The important common idea is not one algorithm. It is an architecture: deliberately discard most of the source state while preserving a task-specific statistic with an explicit error contract.
One-sentence answer: probabilistic sketches are lossy because they replace exact data with compact summaries whose uncertainty is designed, quantified and matched to the receiver’s question.
Exactness Is Not Free
Exact sets need to remember identities.
Exact frequency tables need a counter for every tracked item.
Exact distinct counts need a way to recognise every unique value already seen.
At small scale, that is fine.
At internet scale, the state itself can become the problem.
Sketches exist because the receiver often does not need exact answers for every object at every stage.
The Three Questions
- Membership: Has this item appeared?
- Frequency: How often has this item appeared?
- Cardinality: How many distinct items appeared?
These questions look related because they all concern a stream or set.
They require different information.
A strong systems design does not build one vague “summary”. It preserves the particular statistic the downstream decision actually needs.
Bloom Filters Preserve Asymmetric Membership
A Bloom filter can say “definitely not” and “probably yes”.
That asymmetry is not a flaw patched after deployment. It is the contract.
Identity disappears into shared bits so a compact structure can reject definite misses quickly.
Count-Min Sketch Preserves One-Sided Frequency Estimates
Count-Min Sketch lets many items share counters.
Collisions create overestimation, and repeated independent rows control that error probabilistically.
The stream’s order and event provenance disappear. Approximate frequency remains.
HyperLogLog Preserves Scale Without Identity
HyperLogLog does not need to remember every distinct user to estimate how many distinct users there were.
It preserves statistical evidence from hashed values and uses that evidence to estimate the unseen set size.
The identities disappear almost completely from the operational representation. Cardinality survives.
This Is Not Ordinary Aggregation
An average compresses known values into a deterministic statistic.
A probabilistic sketch compresses a stream into a state whose answer itself carries controlled estimation uncertainty.
Both are lossy.
The difference is the contract.
Aggregation asks which deterministic summary to preserve. Sketching asks which query can be answered approximately within an explicit resource and error budget.
This Is Not Sampling Either
Sampling keeps a subset of observations or observes the source at discrete points.
Sketching can process every event and still keep only a tiny state.
The loss happens in the retained representation, not necessarily in which events were seen.
A sketch can therefore be a full-stream observer with radically compressed memory.
Memory Becomes an Error Budget
This is the deep engineering move.
Instead of asking “How much memory do I need to be exact?”, the system asks “How much error can the receiver tolerate, and how much memory buys that error?”
Memory, precision and confidence become exchangeable design variables.
This is rate–distortion thinking translated into streaming algorithms.
The Error Must Be Directional When Direction Matters
Bloom filters tolerate false positives but not ordinary false negatives.
Count-Min Sketch tolerates bounded overestimation in its standard setting.
HyperLogLog tolerates small relative estimation error in either direction.
These are not interchangeable forms of approximation.
A system should choose the error geometry before it chooses the algorithm.
Approximation Is Safest When It Routes Toward Exactness
A Bloom filter can reject definite misses and route possible hits to an exact database.
A Count-Min Sketch can identify likely heavy hitters and route them to exact counting.
A HyperLogLog estimate can guide capacity planning while authoritative user records remain elsewhere.
This layered architecture is stronger than demanding exactness everywhere or accepting approximation everywhere.
Sketches Are Often Mergeable
Distributed systems gain enormous value when compact summaries can be combined without replaying the full raw stream.
Compatible Count-Min Sketches can be added.
Compatible HyperLogLog structures can be merged register-wise.
Other sketches offer their own composable operations.
Lossy representation becomes a network primitive: small summaries travel where raw data would be expensive.
Mergeability Preserves Some Algebra
This is worth noticing.
A good sketch does not preserve the original data, but it may preserve operations over the data.
Union, addition or aggregation can sometimes be performed directly on the compressed state.
That means the representation has thrown away objects while preserving part of their algebra.
The Lost Information Is Not Recoverable
A Bloom filter cannot list the set.
A Count-Min Sketch cannot reconstruct the event stream.
A HyperLogLog sketch cannot tell you which unique users existed.
This is not accidental missing functionality.
The memory savings come from refusing to preserve those questions.
The Query Must Be Chosen Before the Compression
If you may later need event order, do not keep only a frequency sketch.
If you may later need identities, do not keep only a cardinality sketch.
If a positive membership decision is legally consequential, do not let a Bloom filter become the final authority.
A sketch is safe when future question-space is intentionally narrowed.
Approximation Can Be More Honest Than Hidden Exactness Theatre
Many ordinary systems output one clean number even though upstream sampling, measurement and modelling already contain uncertainty.
Probabilistic sketches do something healthier.
They acknowledge the approximation explicitly and engineer around it.
The result can be epistemically cleaner than a larger system that looks exact while silently carrying uncontrolled loss.
Dashboards Should Expose Approximation
If a dashboard displays an approximate distinct-user count, it should not present 1,023,741 as though each user were exactly enumerated if the backing query is a sketch.
Round appropriately.
Label approximation where it matters.
Expose uncertainty or method when a decision could change near a threshold.
The interface should preserve the epistemic contract of the data structure.
Sketches and Privacy Are Not the Same Thing
Compact summaries can reduce direct access to raw identities.
That can be operationally useful.
But lossy does not automatically mean private. Formal privacy requires threat models and mechanisms designed for privacy, such as differential privacy in suitable settings.
A sketch should not inherit security claims merely because it stores less information.
Sketches and Anonymisation Solve Different Problems
Anonymisation asks what must be altered to reduce identity or inference risk.
Sketching asks what can be discarded while preserving a query efficiently.
The same representation may incidentally help both, but the design objective and validation criteria differ.
Education: Approximation Should Be Taught as a Contract
Students often encounter approximation as “the answer is not exact”.
That is too weak.
A mature approximation says what is preserved, what is lost, how error behaves, and whether the error can change the decision.
This turns approximation from sloppiness into engineering.
A CivDJ View: Loss Should Be Typed
The useful public lesson is simple: do not label a representation merely “approximate”.
Name the loss.
- Membership uncertainty.
- Frequency overestimation.
- Cardinality relative error.
- Identity loss.
- Sequence loss.
- Provenance loss.
Once the lost dimension is typed, the receiver can decide whether the representation is still fit for purpose.
When Probabilistic Sketches Are Exactly the Right Loss
Use them when streams are enormous, exact state is expensive, the query is narrow, the tolerated error can be stated, and exact evidence remains available where high-stakes verification still matters.
They are especially strong as first-stage routing layers in large systems.
When Probabilistic Sketches Become Dangerous
- The sketch’s output is treated as exact.
- The error guarantee does not match the operational decision.
- The structure is used outside its assumed update model.
- Incompatible sketches are merged.
- The query later changes to something the sketch never preserved.
- The exact source is destroyed without considering future audit needs.
- A smaller representation is mistaken for a formal privacy guarantee.
A Practical Probabilistic-Sketch Audit
- Question: membership, frequency, cardinality or something else?
- Loss type: exactly which dimensions disappear?
- Error: one-sided, two-sided, absolute or relative?
- Confidence: with what probability does the bound hold?
- Memory: what resource budget produced that error?
- Mergeability: can distributed summaries be combined safely?
- Thresholds: could approximation alter a consequential classification?
- Source: what richer evidence remains upstream?
Continue Through eduKateSG
Read the three canonical examples: How Lossy Works | Bloom Filters, How Lossy Works | Count-Min Sketch, and How Lossy Works | HyperLogLog. Then return to How Compression Works for the larger information-reduction frame.
Final Thought: The Best Approximation Knows Exactly What It Is Not
Probabilistic sketches are not powerful despite being lossy.
They are powerful because the loss is deliberate, narrow and quantified.
That is the difference between approximation and carelessness.