FA-72912 / Probabilistic sketches / Member archive

Bloom filter cardinality estimation: intersection can become negative · case 02

Disjoint filters report a negative number of shared items.

Member previewVariant 2 · 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
disjoint bits clamp intersection	`[6.501, 6.501, 14.267, -1.265]`	`[6.501, 6.501, 14.267, 0.0]`	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.