Data Deduplication using Locality Sensitive Hashing
summary
Explains that minhash + locality sensitive hashing turns Jaccard set similarity into a probabilistic collision test and shows an open source Python implementation (LSH / pyLSH) on GitHub written with Cython and murmur3. Demonstrates on Reuters-like data (≈800k docs) with example similarities like 71% 89% 88%, fingerprints split into bands, and a microbenchmark of 500 docs → 84 µs per fingerprint. Library runs, reduces all‑pairs comparisons, uses in‑memory index today and is being extended to SQLite; practical parameter guidance is given.
AI-written summary · about
chapters (13)
- 0:00Introduction
- 1:14Why deduplication matters
- 3:10Near-duplicate sources
- 6:00Problems from duplicates
- 8:06Scalable comparison needs
- 9:35Shingles and Jaccard similarity
- 11:15All-pairs to LSH
- 14:10MinHash for collisions
- 19:57Fingerprints with hashes
- 22:51How locality-sensitive hashing works in practice
- 24:15LS h library and alternatives
- 26:04Mathematical foundations
- 27:30Q&A
related talks
11mFinding Friends in High Dimensions...
35mBeyond Spark MLlib: Deduplicating Common Crawl at Scale
24mSpeeding up search with locality sensitive hashing
33mFuzzy Search Algorithms How and When to Use Them
32mAdventures with Randomized Algebra for Extreme-Scale Signal Processing
01h 05mNearest Neighbor Methods I
25mAccelerating fuzzy document deduplication to improve LLM training w/ RAPIDS & Dask
42mWhen Hashes Met Wedges - A Distributed Algorithm for Finding High Similarity Vectors