Spectral Approaches to Nearest Neighbor Search

on YouTube ↗49m

" summary

Proposes reducing approximate nearest neighbor to a spectral graph problem, building a sparsified neighborhood graph and embedding via Laplacian eigenmaps so most k‑nearest relations remain (≈95%) after compression by about 10×. Implements a data structure that combines spectral sparsifiers, Laplacian eigenmaps and LSH, and evaluates on image and text collections, reporting roughly 5–10× query speedup with about 50% memory reduction compared to baseline ANN.

AI-written summary · about

" chapters (16)

1. 0:00Intro
2. 0:45Nearest Neighbor Search (NNS)
3. 1:08Motivation
4. 3:18Curse of dimensionality
5. 4:14Approximate NNS
6. 16:37Practice vs Theory Data-aware projections often outperform (vanilla) random-projection methods
7. 19:43Model properties
8. 24:32Tool: PCA Principal Component Analysis like SVD Top PCA direction direction maximizing variance of the data
9. 25:01Naive attempt via PCA Use PCA to find the signal subspace U?
10. 27:291st Algorithm: intuition
11. 30:51Analysis of PCA
12. 32:51Closeness of subspaces ?
13. 38:19Additional issue: Conditioning After an iteration, the noise is not random anymore!
14. 40:06Performance of Iterative PCA
15. 42:342 algorithmic modifications
16. 44:35Post-perspective

" related talks

• 43mSpectral Approaches to Nearest Neighbor SearchRobert Krauthgamer · Learning, Algorithm Design and Beyond Worst-Case Analysis
• 01h 05mNearest Neighbor Methods IIlya Razenshteyn · Foundations of Data Science Boot Camp 2018
• 34mParallel Efficient Clustering with Graph-Based Approximate Nearest Neighbor SearchJulian Shun · Managing Parallelism 2025
• 42mDistribution-Specific Analysis of Nearest Neighbor Search and ClassificationSanjoy Dasgupta · Learning, Algorithm Design and Beyond Worst-Case Analysis
• 48mHolder Homeomorphisms and Approximate Nearest NeighborsIlya Razenshteyn · Sublinear Algorithms and Nearest-Neighbor Search
• 46mSpectral Partitioning for Metrics (And NNs Too)Alex Andoni · Sublinear Algorithms and Nearest-Neighbor Search
• 10man introduction to approximate nearest neighborsKacper Łukawski · PyData Global 2022
• 40mEfficient Reductions for k-Nearest Neighbor SearchRasmus Pagh · Sublinear Algorithms and Nearest-Neighbor Search