Spectral Partitioning for Metrics (And NNs Too)
summary
Gives a concrete parameter, the cutting modulus, and proves it controls approximate nearest‑neighbor complexity: for any norm on R^d there is a cell‑probe data structure using ~n^{1+ε} space and ~n^{ε} probes that guarantees approximation about Θ(log d) (for spectral norm and general norms) with algorithms built from spectral partitioning / nonlinear spectral gaps and minimax duality. Results work but are cell‑probe only, require exponential preprocessing, and improve for ℓ_p families.
AI-written summary · about
chapters (15)
- 0:00Intro
- 0:47Approximate Near Neighbors (ANN)
- 5:29Which metric to use?
- 13:30General norms?
- 15:04Baseline ANN for norms: via embedding
- 16:46Our results
- 22:07New approach
- 27:07Example: real line, l2
- 31:54Cutting modulus vs embeddings
- 32:44Cutting modulus for norms • "Baseline" bound (John's ellipsoid)
- 34:54Cutting modulus = ANN
- 36:20ANN:core partitioning procedure
- 41:22Cutting modulus = core partitioning
- 42:26Cuts: algorithmic aspect
- 44:16Conclusions and open problems
related talks
01h 01mNearest Neighbor Methods II
43mSpectral Approaches to Nearest Neighbor Search
49mSpectral Approaches to Nearest Neighbor Search
01h 05mNearest Neighbors II
52mConstrained Subset Selection Problems under Diversity Measures
01h 04mAlgorithmic High Dimensional Robust Statistics II
42mDistribution-Specific Analysis of Nearest Neighbor Search and Classification
01h 08mNearest Neighbors I