Efficient Reductions for k-Nearest Neighbor Search

on YouTube ↗40m

" summary

Proposes a practical stopping rule called confirmation sampling that queries multiple LSH-style structures until the current best point appears T+1 times, giving a worst-case expected samples ≈ (T+1)/p1 and error probability shrinking as 2^-T. Uses multi-probe hash tables and an SH-forest variant, adapts by searching prefixes and levels, and proves competitiveness up to constant factors with the best LSH-forest strategy for each query. Works with independently drawn hash samples and removes the need to know p1 a priori.

AI-written summary · about

" chapters (16)

1. 0:00Intro
2. 0:35Nearest neighbor search
3. 1:45Some application areas
4. 2:03Hardness of NN search
5. 4:21Approximate nearest neighbor
6. 5:22Approximate NN in practice
7. 9:02NN recall guarantee?
8. 10:14LSH with multi-probing
9. 12:46From FALCONN documentation
10. 14:16Adaptive stopping
11. 16:25Abstract view
12. 21:53Why confirmation sampling works
13. 24:52Abstract confirmation sampling
14. 27:18Application to nearest neighbor
15. 29:12Partial answer for LSH forest
16. 32:08Open question

" related talks

• 42mDistribution-Specific Analysis of Nearest Neighbor Search and ClassificationSanjoy Dasgupta · Learning, Algorithm Design and Beyond Worst-Case Analysis
• 01h 05mNearest Neighbor Methods IIlya Razenshteyn · Foundations of Data Science Boot Camp 2018
• 31mNearest Neighbor Based Greedy Coordinate DescentPradeep Ravikumar · Information Theory, Learning and Big Data (Simons Institute, 2015)
• 49mSpectral Approaches to Nearest Neighbor SearchAlexandr Andoni · Spectral Algorithms: From Theory to Practice 2014
• 01h 01mNearest Neighbor Methods IIIlya Razenshteyn · Foundations of Data Science Boot Camp 2018
• 24mSpeeding up search with locality sensitive hashingMaciej Kula · EuroPython 2015
• 01h 08mNearest Neighbors IKamalika Chaudhuri · Deep Learning Boot Camp 2019
• 01h 05mNearest Neighbors IIKamalika Chaudhuri · Deep Learning Boot Camp 2019