FA-73212 / Probabilistic sketches / Member archive

MinHash LSH banding: band key omits the band index · case 02

Two signatures that agree on different bands are paired although no band matches.

Member previewVariant 2 · 3 implementations · 8 checks per implementation

Case contract

Input {b, r, sigs} with sigs a list of [id, signature]. Every signature must have exactly b*r components, otherwise "invalid". Band i covers components i*r .. i*r+r-1 and hashes to the key (i, band tuple). Ids sharing any band key form a candidate pair [smaller, larger], reported once, sorted. Also return the similarity threshold (1/b)^(1/r) rounded to 3 decimals.

Why this case matters

Locality-sensitive hashing prunes all-pairs similarity search; banding mistakes either flood the verifier with false candidates or silently miss near-duplicates.

One recorded failure

Sample boundary fixture

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

Boundary fixture	Actual	Expected	Outcome
bands 2 b=4 r=2	`[[[1, 2], [1, 5], [2, 3], [2, 4], [2, 5], [3, 4], [3, 5], [4, 5]], 0.5]`	`[[[1, 2], [2, 3], [2, 4], [2, 5], [3, 4], [3, 5], [4, 5]], 0.5]`	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.