FA-73224 / Probabilistic sketches / Member archive

MinHash LSH banding: overlong signatures accepted · case 04

Signatures produced with a different hash count are compared on a prefix instead of being rejected.

Member previewVariant 4 · 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
overlong signature	`[[[1, 2]], 0.707]`	`"invalid"`	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.