Compare & merge
Two of these structures, built separately, can be combined into one — and the result is exactly the structure you would have got by feeding both streams to a single machine.
Where this is actually used
This is what makes them usable at scale. A hundred servers each keep their own sketch and never talk to each other; at the end of the hour one machine combines all hundred into a single answer covering every request, in one pass, with no re-reading of the original data.
The guarantee
Verified against the structure built from the concatenated stream
How it works
The same stream through every structure, and the merges that make them usable across machines that never talk to each other.
Merge
Two sketches built from different streams, unioned. Bloom filters OR together; HyperLogLogs take the per-register maximum; Count-Min sketches add.
Bloom filter
Stream A
4,643
Stream B
7,374
Merged
10,941
Memory
4.0 KiB
measured from the typed array
Verified
✓
byte-identical to the structure built from A + B
Count-Min sketch
Stream A
4,000
Stream B
4,000
Merged
8,000
Memory
10.0 KiB
measured from the typed array
Verified
✓
byte-identical to the structure built from A + B
HyperLogLog
Stream A
836
Stream B
1,376
Merged
2,208
Memory
4.0 KiB
measured from the typed array
Verified
✓
byte-identical to the structure built from A + B
Union works. Intersection does not.
OR-ing two filters gives bit-for-bit the filter you would have built from both streams — verified above. AND looks like the same trick in the other direction. It is not, and the check that passes for union fails here.
AND equals the filter built from the true intersection
✗
no
Items genuinely in both
778
Bits set by AND
4,352
Bits set by the real thing
4,310
ε of the AND
0
ε if you had built it
0
Why it over-accepts
AND keeps every bit that any item set in one filter and any other item happened to set in the other. Those bits were never put there by a member of the intersection, and nothing distinguishes them from bits that were. So the result carries more set bits than a filter built from the intersection would, and answers “possibly present” more often — you did not get the ε you would have had, and no operation on these two filters can recover the difference.
One thing this is NOT: asking about items from the two streams themselves shows an error rate below a single filter’s ε, and that is correct rather than a defect — an item in exactly one set only needs the other filter to accept it by chance, which is ε by definition. The cost shows on items in neither stream, which is what is measured here.
One item, all four structures
They are not four algorithms. They are one hash pair and one derivation, read four different ways — the same h₁ and h₂ that pick a Bloom slot pick the Count-Min column, the HyperLogLog register and the Cuckoo bucket.
Past the size you planned for
Memory fixed, items climbing. Both structures were sized for 8,000 items; the axis runs to 40,000. Nothing here changes the memory — only how much you put in it.
Cuckoo filter — no lossless merge
The one structure here that cannot do this. Bloom ORs, HyperLogLog takes a maximum, Count-Min adds — each a single pass over the arrays that always succeeds. A Cuckoo filter has no such combine: entries sit in one of two buckets, so merging means re-inserting them one at a time, and that can be refused. Two half-full filters do not fit into one of the same size — measured here at 180 of 600 entries refused.
Union cardinality
Stream A — distinct
836
Stream B — distinct
1,387
Merged — Exact
2,223
The streams overlap on purpose. A merge that double-counted would show here.
Merged — Estimate
2,208
-0.66%
Bloom and HyperLogLog merge as set unions, so merging a structure with itself changes nothing. Count-Min merges as a sum, so it does not — that asymmetry is real, and worth knowing before you merge the same shard twice.