Graph-Based Nearest-Neighbor Search without the Spread
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , , , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2026
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866908822275096576 |
|---|---|
| author | Giliberti, Jeff Har-Peled, Sariel Sauer, Jonas Vakilian, Ali |
| author_facet | Giliberti, Jeff Har-Peled, Sariel Sauer, Jonas Vakilian, Ali |
| contents | $\renewcommand{\Re}{\mathbb{R}}$Recent work showed how to construct nearest-neighbor graphs of linear size, on a given set $P$ of $n$ points in $\Re^d$, such that one can answer approximate nearest-neighbor queries in logarithmic time in the spread. Unfortunately, the spread might be unbounded in $n$, and an interesting theoretical question is how to remove the dependency on the spread. Here, we show how to construct an external linear-size data structure that, combined with the linear-size graph, allows us to answer ANN queries in logarithmic time in $n$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2602_06633 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Graph-Based Nearest-Neighbor Search without the Spread Giliberti, Jeff Har-Peled, Sariel Sauer, Jonas Vakilian, Ali Computational Geometry Data Structures and Algorithms Machine Learning $\renewcommand{\Re}{\mathbb{R}}$Recent work showed how to construct nearest-neighbor graphs of linear size, on a given set $P$ of $n$ points in $\Re^d$, such that one can answer approximate nearest-neighbor queries in logarithmic time in the spread. Unfortunately, the spread might be unbounded in $n$, and an interesting theoretical question is how to remove the dependency on the spread. Here, we show how to construct an external linear-size data structure that, combined with the linear-size graph, allows us to answer ANN queries in logarithmic time in $n$. |
| title | Graph-Based Nearest-Neighbor Search without the Spread |
| topic | Computational Geometry Data Structures and Algorithms Machine Learning |
| url | https://arxiv.org/abs/2602.06633 |