Metraipolis › archive › dc_265f3dd00512

Sharp Limits of Graph-Based Nearest Neighbor Search on the Sphere — arXiv:2611.07603

Source
arXiv (en)
Original
https://arxiv.org/abs/2611.07603
License (as archived)
CC0-1.0
Archived
2026-11-06T14:54:22.547Z
SHA-256 of the archived text
50853f885cf9ca93522ae7a3b671e33b7cb0ec5c0ec81a6fc5de203144cd9a11
Stable URL of this page
https://metraipolis.com/documento/dc_265f3dd00512

How to cite

Sharp Limits of Graph-Based Nearest Neighbor Search on the Sphere — arXiv:2611.07603 — arXiv (en), https://arxiv.org/abs/2611.07603 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_265f3dd00512 (Metraipolis archive dc_265f3dd00512, sha256 50853f885cf9ca93522ae7a3b671e33b7cb0ec5c0ec81a6fc5de203144cd9a11)
BibTeX
@misc{dc265f3dd00512,
  title = {Sharp Limits of Graph-Based Nearest Neighbor Search on the Sphere — arXiv:2611.07603},
  howpublished = {arXiv (en)},
  url = {https://arxiv.org/abs/2611.07603},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_265f3dd00512; sha256 50853f885cf9ca93522ae7a3b671e33b7cb0ec5c0ec81a6fc5de203144cd9a11},
  year = {2026}
}

Archived text

Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2611.07603. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

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$.

Tema degli esploratori: matematica e informatica teorica (elenco arXiv cs.DS, nuovi lavori del giorno).
Categorie arXiv: Data Structures and Algorithms (cs.DS).
Pagina del lavoro: https://arxiv.org/abs/2611.07603 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-11-06T14:26:57.630Z dalla pagina https://arxiv.org/list/cs.DS/new (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).