Speeding up search with locality sensitive hashing

on YouTube ↗24m

" summary

Claims that locality sensitive hashing via random projection forests gives a practical, deployable approximate nearest‑neighbor index, implemented in Python and paired with Postgres for final filtering and exact distance checks. Tools tested include annoy, lsh_forest, FLANN and an in‑house RP forest; tradeoffs reported are about 100× speedup at roughly 60% precision (6/10 true neighbors), supports incremental adds and avoids keeping all vectors in memory, and ships as a small service that returns candidate IDs for Postgres to validate.

AI-written summary · about

" chapters (18)

1. 0:00Introduction
2. 1:29Image search
3. 4:27Similar images
4. 5:08Collaborative filtering
5. 6:14Data scientists
6. 7:36How to make it work
7. 8:28Marginal space
8. 9:00Random line
9. 10:58Dimensionality
10. 15:16Questions
11. 15:33How to generalize
12. 16:29Python packages
13. 18:28RPForest
14. 18:41Speed
15. 18:58How we use it
16. 19:47Postgres
17. 20:10Results
18. 21:13QA

" related talks

• 26mUsing Random Projections to Make Sense of High-Dimensional ...Stefan Savev · Berlin Buzzwords 2015
• 01h 05mNearest Neighbor Methods IIlya Razenshteyn · Foundations of Data Science Boot Camp 2018
• 32mAdventures with Randomized Algebra for Extreme-Scale Signal ProcessingAnshumali Shrivastava · Randomized Numerical Linear Algebra and Applications 2018
• 40mEfficient Reductions for k-Nearest Neighbor SearchRasmus Pagh · Sublinear Algorithms and Nearest-Neighbor Search
• 23mErik Bernhardsson, CTO, Better Mortgage, NYC 2017Erik Bernhardsson · MLconf NYC 2017
• 30mFuzzy Matching at ScaleThusal · PyData London 2022
• 49mSpectral Approaches to Nearest Neighbor SearchAlexandr Andoni · Spectral Algorithms: From Theory to Practice 2014
• 31mNearest Neighbor Based Greedy Coordinate DescentPradeep Ravikumar · Information Theory, Learning and Big Data (Simons Institute, 2015)