Part 2 of 12 · 2 min read
Comparing every pair doesn't scale, so hash similar items into the same bucket
Checking every pair of rows for near-duplicates is quadratic; hashing similar rows into the same bucket turns it into roughly linear work.
Think of sorting a pile of photos by who is in them. Comparing every photo to every other photo takes forever. But suppose you first sort by rough features, such as hair color and setting. Then you only have to carefully compare photos already in the same small pile.
In plain words: finding exact duplicates after normalising text catches some copies but misses anything with even one word changed, while MinHash signatures plus LSH banding let you skip comparing almost all the pairs that obviously aren't similar, at the cost of occasionally missing one that is.
A worked example. Comparing every one of 3,073,960 possible pairs finds all 501 true near-duplicate pairs with perfect recall — but at that cost. Exact matching after normalising case and markup only finds 62.9 percent of them, because it misses anything with even a single word changed. MinHash with 16 bands of 4 rows finds 99.6 percent of the true pairs while only generating 499 candidate pairs to actually check — roughly 1/6,000th of the brute-force comparison count, at a small recall cost.
The key lines. From code/mini-dataset/dedup.py:
# from code/mini-dataset/dedup.py
def lsh_candidates(sig, bands, rows):
"""Items sharing all `rows` signature values in at least one of `bands` bands become candidate pairs."""
if bands < 1 or rows < 1 or bands * rows > sig.shape[1]:
raise ValueError("need bands, rows >= 1 and bands * rows <= number of hashes")
cand = set()
for b in range(bands):
buckets = {}
for i, row in enumerate(sig[:, b * rows:(b + 1) * rows]): buckets.setdefault(row.tobytes(), []).append(i)
Read it as: items only become a candidate pair if they land in the exact same bucket in at least one band. This is what turns an all-pairs comparison into a bucket lookup. It is also exactly why choosing the band and row counts matters. With too few bands, real duplicates slip through without ever sharing a bucket.
Deduplication, shingle and Jaccard similarity
Exact dedup removes items identical after normalisation; near-duplicate detection finds items that are mostly the same, for example by shingle (a short run of words) overlap. Jaccard similarity is the size of the intersection of two shingle sets divided by the size of their union.
Example: the 0.6-to-1.0 Jaccard range covering all 501 true duplicate pairs in this toy is exactly the similarity measure that LSH is trying to approximate cheaply, without ever computing it directly for most pairs.