Skip to content
AITroveRead. Build. Understand.
Reading list
Make this comfortable

MinHash bands: retrieve incident candidates, then check exact overlap

Last updated: 5 Oct 20269 min read
tutorial
IntermediateBy AITrove Editorial

A MinHash sketch records the minimum token hash under each of several independently seeded hash functions. Similar token sets tend to agree in more sketch positions. Banding groups adjacent positions into exact tuples; records sharing a tuple in any band become candidates for later verification. This index stores each incident's complete token set, uses deterministic cryptographic hash digests for stable demonstration output, and calculates exact Jaccard intersection-over-union on retrieved candidates. The bucket search is approximate: two truly similar incidents can miss every band, so a missing result does not prove dissimilarity. Empty token sets are rejected because this interface does not define their Jaccard score, and duplicate incident IDs are refused rather than overwritten without cleaning old buckets.

Operational case

Incident I-19 has dock, scanner, offline, and night. I-47 adds retry to that set, while I-83 contains unrelated payment terms. Querying the first four tokens at threshold 0.75 returns I-19 with score 1.0 and I-47 with score 0.8 in the fixed trace. The index does not compare every record, so another corpus could omit a genuine match that never collides in any band. Exact verification prevents returned false positives relative to the specified threshold, but it cannot recover candidate false negatives. Token normalization and shingling policies must stay the same between indexed incidents and queries.

Working Python program

python
import hashlib
from collections import defaultdict


def token_hash(token, permutation):
    payload = str(permutation).encode() + b"\0" + token.encode("utf-8")
    return int.from_bytes(hashlib.blake2b(payload, digest_size=8).digest(), "big")


def signature(tokens, width=24):
    if not tokens:
        raise ValueError("empty token set has no signature")
    return tuple(min(token_hash(token, number) for token in tokens) for number in range(width))


class IncidentCandidateIndex:
    def __init__(self, bands=6, rows_per_band=4):
        if bands <= 0 or rows_per_band <= 0:
            raise ValueError("positive band dimensions required")
        self.bands = bands
        self.rows_per_band = rows_per_band
        self.records = {}
        self.buckets = defaultdict(set)

    def _keys(self, sketch):
        for band in range(self.bands):
            start = band * self.rows_per_band
            yield band, sketch[start:start + self.rows_per_band]

    def add(self, incident_id, tokens):
        if incident_id in self.records:
            raise ValueError("duplicate incident ID")
        token_set = frozenset(tokens)
        sketch = signature(token_set, self.bands * self.rows_per_band)
        self.records[incident_id] = (token_set, sketch)
        for key in self._keys(sketch):
            self.buckets[key].add(incident_id)

    def query(self, tokens, minimum_similarity):
        if not 0 <= minimum_similarity <= 1:
            raise ValueError("similarity outside [0,1]")
        token_set = frozenset(tokens)
        sketch = signature(token_set, self.bands * self.rows_per_band)
        candidates = set()
        for key in self._keys(sketch):
            candidates.update(self.buckets[key])
        matches = []
        for incident_id in candidates:
            stored_tokens, _ = self.records[incident_id]
            similarity = len(token_set & stored_tokens) / len(token_set | stored_tokens)
            if similarity >= minimum_similarity:
                matches.append((incident_id, round(similarity, 3)))
        return sorted(matches)


incident_index = IncidentCandidateIndex()
incident_index.add("I-19", {"dock", "scanner", "offline", "night"})
incident_index.add("I-47", {"dock", "scanner", "offline", "night", "retry"})
incident_index.add("I-83", {"invoice", "paid", "review"})
print("near matches:", incident_index.query({"dock", "scanner", "offline", "night"}, 0.75))

Output

Output
near matches: [('I-19', 1.0), ('I-47', 0.8)]

Time, space, and tradeoff

With S sketch positions and T distinct tokens in one record, this direct implementation computes O(ST) hashes and stores O(S+T) values per record, plus band-bucket references. A query hashes O(ST) token-position pairs, unions all collided buckets, then verifies each candidate in time proportional to the token-set intersection and union work. In the worst case every record is a candidate, so query work scales with corpus size. Hash agreement only estimates resemblance; this implementation reports exact scores after candidate retrieval. The fixed digest family is practical for reproducibility but does not claim perfect minwise independence or a universal recall guarantee.

Common Mistakes

  • Do not treat a missing band collision as proof of dissimilarity.
  • Do not return an approximate score as if exact verification had run.
  • Do not change token normalization between indexing and querying.
  • Do not overwrite an incident without removing its old band memberships.

Connected lessons

Compare this operation boundary with Alias tables: constant-work draws from fixed dispatch weights, Run-length bitmaps: union, intersect, and subtract alert spans, then complete the structure audit and decision quiz.

Suffix arrays: indexed substring search and adjacent LCP gives a related indexing or summary tradeoff.

SimHash bands: find near-duplicate incident fingerprints examines a related structure with a different operation boundary.

data structures
hash-tables
Storage details