FA-72922 / Probabilistic sketches / Member archive

Bloom filter cardinality estimation: estimate uses a base-2 logarithm · case 02

Every item-count estimate is inflated by a factor of about 1.44.

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
overlapping filters	`[11.458, 12.156, 19.238, 4.376]`	`[7.942, 8.426, 13.335, 3.033]`	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.