Nearest Neighbor Methods II
summary
Covers concrete algorithms and limits: a deterministic L∞ decision-tree gives O(log log D) approximation with near-linear space and O(d log N) query work; L1/Lp and Orlicz/top-k norms embed into L∞ by dividing coordinates by iid random variables (exponentials or powers) — a randomized exponential embedding yielding constant distortion and thus log log D ANN. New STOC/FOCS work defines a cutting modulus and builds cell-probe ANN with approximation = cutting modulus, space N^{1+ε} and N^{ε} probes; for general d-dimensional norms cutting modulus ≤ O(log d/ε^2), so you get polylog(d) guarantees and some routes to time-efficient structures (coordinate cuts, Mazur-like transforms for Schatten p).
AI-written summary · about
related talks
48mHolder Homeomorphisms and Approximate Nearest Neighbors
42mDistribution-Specific Analysis of Nearest Neighbor Search and Classification
01h 34mAlgorithmic High-Dimensional Geometry II
54mA Near-Linear Time Algorithm for the Chamfer Distance
46mSpectral Partitioning for Metrics (And NNs Too)
01h 30mAnalytic Methods for Supervised Learning II
01h 00mOn Approximating the Covering Radius and Finding Dense Lattice Subspaces
01h 05mNearest Neighbors II