Holder Homeomorphisms and Approximate Nearest Neighbors
summary
New algorithms give time‑efficient ANN for arbitrary norms in R^D with subpolynomial approximation (exp((log D)^{2/3})) using polynomial space and preprocessing and polylog N query time, and a second variant that trades exponential preprocessing for approximation exp(sqrt(log D)) and near‑linear space. Key ingredients are the complex interpolation construction that yields Hölder homeomorphisms between perturbed norm and Euclidean spaces, a bounded ANN reduction (Bartal–Gottlieb), discretized convex programs to compute interpolated norms, and spectral partitioning; the constructions are algorithmic and provably work.
AI-written summary · about
chapters (9)
- 0:00Start
- 2:23Distances beyond l1/?
- 7:30Approach at a high level
- 9:31Reducing ANN to the bounded case
- 13:08Embedding the unit ball
- 16:00Uniform convexity
- 33:49Construction
- 36:14Making interpolation algorithmic
- 40:55Sparse cuts in embedded graph
related talks
01h 01mNearest Neighbor Methods II
49mSpectral Approaches to Nearest Neighbor Search
01h 05mNearest Neighbor Methods I
54mA Near-Linear Time Algorithm for the Chamfer Distance
01h 30mAnalytic Methods for Supervised Learning IV
01h 34mAlgorithmic High-Dimensional Geometry II
01h 05mNearest Neighbors II
42mDistribution-Specific Analysis of Nearest Neighbor Search and Classification