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

SimHash bands: find near-duplicate incident fingerprints

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

A SimHash fingerprint maps weighted tokens into a fixed-width bit vector. Each token's digest adds or subtracts its positive weight at every bit; the sign of each accumulated position chooses the output bit. Similar feature bags often produce nearby fingerprints, though similarity of source incidents is not guaranteed by a particular Hamming threshold. This index cuts each 64-bit fingerprint into equal contiguous bands and posts incident IDs under their band values. A query unions all IDs sharing at least one band, then computes the full XOR bit count to verify Hamming distance. With eight bands, accepting a distance of at most seven guarantees candidate recall for indexed fingerprints inside that distance: fewer than eight differing bits cannot disturb all eight bands. Larger thresholds are rejected because one-band matching would then have false negatives. The model indexes distinct IDs and has no update or delete method.

Operational case

Incident 47 contains weighted dock, scanner, and timeout tokens; incident 83 contains weather and road tokens. Each queried feature bag finds its matching ID at Hamming distance zero. A modified token bag can yield a small or large distance depending on hashed bit interactions; this is a fingerprint index rather than exact text equality. The returned pair includes the incident ID and verified distance. Bands are only a candidate generator. A candidate with a shared band but excessive full distance is removed, and an incident within seven differing bits cannot be missed by the eight-band index. An empty feature bag and nonpositive weights are rejected instead of producing an arbitrary all-zero fingerprint.

Working Python program

python
import hashlib


class IncidentFingerprintIndex:
    def __init__(self, band_count=8):
        if not isinstance(band_count, int) or not 1 <= band_count <= 64 or 64 % band_count:
            raise ValueError("band count must divide 64")
        self.band_count = band_count
        self.band_width = 64 // band_count
        self.fingerprints = {}
        self.buckets = {}

    @staticmethod
    def fingerprint(features):
        if not features or any(not isinstance(token, str) or not isinstance(weight, int) or weight <= 0
                               for token, weight in features.items()):
            raise ValueError("features need positive integer weights")
        balance = [0] * 64
        for token, weight in features.items():
            digest = int.from_bytes(hashlib.blake2b(token.encode(), digest_size=8).digest(), "little")
            for bit in range(64):
                balance[bit] += weight if digest & (1 << bit) else -weight
        return sum(1 << bit for bit, score in enumerate(balance) if score > 0)

    def _bands(self, fingerprint):
        mask = (1 << self.band_width) - 1
        return [(band, (fingerprint >> (band * self.band_width)) & mask)
                for band in range(self.band_count)]

    def add(self, incident_id, features):
        if incident_id in self.fingerprints:
            raise ValueError("incident ID already indexed")
        fingerprint = self.fingerprint(features)
        self.fingerprints[incident_id] = fingerprint
        for bucket in self._bands(fingerprint):
            self.buckets.setdefault(bucket, set()).add(incident_id)

    def neighbors(self, features, max_distance=7):
        if not 0 <= max_distance < self.band_count:
            raise ValueError("distance must be below band count for complete candidate recall")
        fingerprint = self.fingerprint(features)
        candidates = set().union(*(self.buckets.get(bucket, set())
                                   for bucket in self._bands(fingerprint)))
        return sorted((incident_id, (fingerprint ^ self.fingerprints[incident_id]).bit_count())
                      for incident_id in candidates
                      if (fingerprint ^ self.fingerprints[incident_id]).bit_count() <= max_distance)


if __name__ == "__main__":
    index = IncidentFingerprintIndex()
    index.add(47, {"dock": 3, "scanner": 2, "timeout": 1})
    index.add(83, {"weather": 4, "road": 2})
    print(index.neighbors({"dock": 3, "scanner": 2, "timeout": 1}))
    print(index.neighbors({"weather": 4, "road": 2}))

Output

Output
[(47, 0)]
[(83, 0)]

Time, space, and tradeoff

For F tokens and W fixed at 64 bits, fingerprinting performs O(FW) bit-weight updates and keeps O(W) temporary scores. An insertion posts one ID to each of eight band buckets. A query reads eight buckets, deduplicates C candidate IDs, and verifies each by one 64-bit XOR and bit count, costing O(FW + C) under fixed-width word operations and O(C) temporary memory. In the worst case every indexed ID shares a band, so C equals N and the query scans the corpus; the bucket index makes no sublinear worst-case promise. Stored fingerprints and postings use O(N times eight) ID references before Python container overhead. MinHash addresses a different set-similarity signal, while this page verifies Hamming distance of weighted-token fingerprints.

Common Mistakes

  • Do not report a shared band as a verified near duplicate.
  • Do not use a threshold of eight or more with an eight-band recall claim.
  • Do not equate small fingerprint distance with semantic equivalence.
  • Do not insert the same incident ID twice without a removal or replacement policy.

Connected lessons

Compare this operation boundary with Adaptive radix trees: grow byte-edge nodes as incident codes branch, Bit-sliced indexes: filter and sum fixed-width sensor readings, Minimal acyclic dictionaries: merge equivalent word suffix states, then complete the audit project and decision quiz.

data structures
hash-tables
Storage details