arXiv preprint ·
Sharp Limits of Graph-Based Nearest Neighbor Search on the Sphere
- Published
- Source
- arXiv preprint, posted before peer review
- Original
- Read it at arXiv
- Topics
Abstract
We study the degree needed for greedy graph search to find the exact nearest neighbor from every starting point on graphs of $n$ independent data points on the unit sphere in $\mathbb R^d$. For uniform data, we determine an explicit sublinear degree threshold when $d$ is proportional to $\log n$, and the threshold $2^{d/2+o(d)}$ in the dense regime $\sqrt{\log n}\ll d\ll\log n$. Above these thresholds by fixed exponent gaps, the nearest-neighbor graph succeeds from every entry for most uniform queries with high probability, with evaluation cost on the same exponential scale as its degree. Matching lower bounds hold for every graph designed after observing the sample. For nonuniform data in the dense regime, local density variation shifts the critical degree. Under explicit local regularity conditions and within a specified range of density variation, we derive a sharp worst-case degree curve and show that the nearest-neighbor graph attains it. We construct sampling densities and query distributions for which, with high probability, every graph whose degree lies below this curve by a fixed exponent gap has failing entries for most queries. Allowing fresh uniform random entries reduces the cost of exact recovery. For uniform data in the dense regime, we determine the exact exponent for the number of distinct distance evaluations over a range of degrees below the critical threshold. Independent restarts on a single graph joining points within a prescribed radius attain this exponent with high probability. Matching lower bounds hold for adaptive local exploration on threshold and nearest-neighbor graphs using entries independent of the data. Optimizing within this degree range lowers the exponent from $\frac12\log2\approx0.347$ for success from every entry to approximately $0.243$.
The authors’ abstract, as arXiv lists it. arXiv’s listings, abstracts included, are free for anyone to reuse.
Read it on ReadSearch
Each opens after you create an account, and brings you back to this paper.
More in Data Structures & Algorithms
Quadratic-Time Barriers from Self-Referential SAT
Exact $\ell_p$-CVP via Euclidean SVP in Polynomial Space
GreedTok is a Constant-Factor Approximation for Partition-Cover Tokenization
Constant-Factor Approximations for the Biased Traveling Salesman Problem and Its Path Variant
Constant-Factor Approximation Algorithms for Weighted Budgeted Multisensor Sweep Coverage
Get the few papers worth your time in Data Structures & Algorithms every morning.
ReadSearch reads the new papers in your field each day and brings you the few worth reading, each with its key finding in a sentence.