FA-72909 / Probabilistic sketches / Member archive

Bloom filter cardinality estimation: intersection estimated from AND-ed bits · case 04

The shared-item estimate is biased upward because AND-ed bits include coincidental collisions.

Member previewVariant 4 · 3 implementations · 7 checks per implementation

Case contract

Input {m, k, a, b} with a and b lists of set-bit indices (duplicates possible). For a bit set of X distinct indices the item estimate is -(m/k) ln(1 - X/m); a saturated set (X = m) has no estimate (None). The union uses the OR of both bit sets; the intersection is ea + eb - eu clamped at 0, and is None when any input estimate is None. Return the four values rounded to 3 decimals.

Why this case matters

Estimating how many items two Bloom filters hold, and how many they share, drives capacity alarms and set-similarity decisions without access to the items.

One recorded failure

Sample boundary fixture

This sample comes from the broken implementation of a controlled reproducer.

Boundary fixture	Actual	Expected	Outcome
overlapping filters	`[7.895, 8.372, 13.19, 4.0]`	`[7.895, 8.372, 13.19, 3.077]`	Failed

MEMBER ARCHIVE

The complete case is available to members.

This record includes three runnable implementations, regression fixtures, execution results, and source hashes.

Member access is invitation-based. Sign in with your invited account to inspect the sources.