Distribution-Specific Analysis of Nearest Neighbor Search and Classification
summary
Compares algorithmic and statistical behavior of nearest neighbor with concrete bounds: shows KD-style spill forest and random-projection trees have failure probability governed by a concrete potential function — sum over i of dist(q,x1)/dist(q,xi) — and gives instance-size tradeoffs (e.g. 5% overlap → structure size ≈ n^{1.16}; LSH examples n^{1.25} size, query n^{0.25}). Proposes a new probability-mass smoothness for classification that yields matching per-instance upper/lower bounds and proves universal consistency for many metric spaces, leaving explicit open problems about worst-case metric spaces and practical choice of K.
AI-written summary · about
chapters (16)
- 0:00Intro
- 1:20Rate of convergence of NN classification
- 4:53The complexity of nearest neighbor search
- 6:29Approximate nearest neighbor
- 9:45Talk outline
- 10:07The k-d tree: a hierarchical partition of R
- 12:11Heuristic 1: Random split directions
- 13:28Two randomized partition trees
- 16:19Random projection of three points
- 18:26Random projection of a set of points
- 20:42Failure probability of NN search
- 22:57NN search in spaces of bounded doubling dimension
- 26:27Open problems
- 29:21Nearest neighbor classification
- 33:23Smoothness and margin conditions
- 34:41A better smoothness condition for NN
