Spectral Approaches to Nearest Neighbor Search
summary
Claims that when data equals a hidden k-dimensional subspace plus independent Gaussian noise of magnitude σ ≈ d^{-1/4}, the exact nearest neighbor remains intact and PCA-based, data-aware partitions recover large subsets of points. One algorithm computes top-PC directions, marks well-captured points, projects those to S, builds NN structures recursively (O(log n) structures) reducing high-dim NNS to several k-dim instances; a PCA‑slab variant yields depth ≈2k and similar provable runtimes and space under the probabilistic-noise model.
AI-written summary · about
chapters (14)
- 0:00Intro
- 0:45Nearest Neighbor Search
- 2:04Space Partitions
- 3:23Data
- 5:59Data Optimization
- 6:55Model
- 15:58The Problem
- 17:23Intuition
- 24:01Data Structure
- 29:06Subspaces
- 31:32Davis Kahn
- 35:57Algorithm
- 37:14Performance
- 38:39Why doesnt work
related talks
49mSpectral Approaches to Nearest Neighbor Search
46mSpectral Partitioning for Metrics (And NNs Too)
34mParallel Efficient Clustering with Graph-Based Approximate Nearest Neighbor Search
01h 05mNearest Neighbors II
01h 05mNearest Neighbor Methods I
01h 31mUnsupervised Learning
01h 08mNearest Neighbors I
01h 02mTheory and Big Data