FA-72918 / Probabilistic sketches / Member archive

Bloom filter cardinality estimation: saturated filter reports a finite count · case 03

A completely filled filter is reported as containing only m items and yields a finite intersection.

Member previewVariant 3 · 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
saturated filter	`[16, 1.661, 16, 1.661]`	`[null, 1.661, null, null]`	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.