Nearest Neighbor Methods I
summary
Nearest-neighbor search is framed as approximate search with radius R and approximation C, and the core claim is that locality-sensitive hashing (LSH) yields sublinear queries: simple coordinate sampling gives space ≈ N^{1+1/C} and query ≈ D·N^{1/C}, while hyperplane LSH gives ρ≈1/C for L2 and Andoni–Indyk style Voronoi/ball-carving drives ρ≈1/C^2. Data-dependent methods shave the exponent further (for C=2 empirical exponents fall to about N^{1/7} for L2 and N^{1/3} for L1). Algorithms are randomized, practical exact search relies on data gaps ~1.1, and tradeoffs between space and query time are explicit.
AI-written summary · about
chapters (13)
- 0:00Introduction
- 2:07Distance measures hierarchy
- 8:10Approximate nearest neighbor problem
- 18:50Voronoi diagrams for NN search
- 23:02Hamming distance sampling
- 30:45Locality-sensitive hashing
- 35:52LSH families for L1 and L2
- 38:45Hyperplane LSH for Euclidean
- 40:51Optimal LSH on unit sphere
- 48:40Data-dependent LSH bounds
- 56:02Time-space tradeoffs
- 58:08NN search guarantees
- 1:01:02Summary and open problems
related talks
40mEfficient Reductions for k-Nearest Neighbor Search
31mNearest Neighbor Based Greedy Coordinate Descent
49mSpectral Approaches to Nearest Neighbor Search
42mDistribution-Specific Analysis of Nearest Neighbor Search and Classification
11mFinding Friends in High Dimensions...
24mSpeeding up search with locality sensitive hashing
26mUsing Random Projections to Make Sense of High-Dimensional ...
48mHolder Homeomorphisms and Approximate Nearest Neighbors