To find a needle in a haystack
summary
Compares concrete fuzzy‑search designs and tradeoffs using a real film dataset (700k records, ~3M titles) on a MacBook, measuring index size and latency. Tests linear, hash, template hashing, radix/patricia tries, BK‑style graph traversal, Levenshtein and Jaro‑Winkler, and n‑grams; shows 3-gram index ~500MB and that combining n‑grams + Jaro‑Winkler yields best quality while staying fast, about ~100 ms average search. Recommends n‑grams for scale, Jaro‑Winkler for ranking, and hybrid indexing for production.
AI-written summary · about
chapters (8)
- 0:00Fuzzy search introduction
- 10:41Exact search problems
- 12:26Levenshtein metric
- 14:10Jaro-Winkler metric
- 21:37Graph search
- 25:51Using n-grams
- 33:14Combining methods
- 37:51Q&A
