6 / 6 Counters, Top-K & Sketches

Overlap On A Budget

You keep one HyperLogLog per feature flag holding the unique users who touched it. Product asks how many users touched both flag A and flag B, where A has roughly 8 million users, B roughly 7 million, and the true overlap is a few thousand. What should you expect?

A

A bitwise AND of the two register arrays gives the intersection as long as both sketches share parameters

B

HyperLogLog has no intersection operator, and inclusion-exclusion buries an overlap that small

C

Taking the per-register minimum of the two sketches yields an intersection with the accuracy unions get

D

Intersection is exact here because identical user IDs always land in identical registers in both sketches