Navigable Graphs For High-dimensional Nearest Neighbor Search: Constructions And Limits

Abstract

There has been significant recent interest in graph-based nearest neighbor search methods, many of which are centered on the construction of navigable graphs over high-dimensional point sets. A graph is navigable if we can successfully move from any starting node to any target node using a greedy routing strategy where we always move to the neighbor that is closest to the destination according to a given distance function. The complete graph is navigable for any point set, but the important question for applications is if sparser graphs can be constructed. While this question is fairly well understood in low-dimensions, we establish some of the first upper and lower bounds for high-dimensional point sets. First, we give a simple and efficient way to construct a navigable graph with average degree \(O(\sqrt\{n log n \})\) for any set of \(n\) points, in any dimension, for any distance function. We compliment this result with a nearly matching lower bound: even under the Euclidean metric

Stats

• citations3
• S2 citations—
• github stars0
• HF likes0
• heat score4.52
• arxiv keydiwan2024navigable

Related papers

• Graph-based Nearest Neighbor Search: From Practice To Theory (2019)0.00
• A Theoretical Analysis Of Nearest Neighbor Search On Approximate Near Neighbor Graph (2023)0.00
• Efficient And Robust Approximate Nearest Neighbor Search Using Hierarchical Navigable Small World Graphs (2016)22.99
• High Dimensional Similarity Search With Satellite System Graph: Efficiency, Scalability, And Unindexed Query Compatibility (2019)17.30
• Fast Approximate Nearest Neighbor Search With The Navigating Spreading-out Graph (2017)18.20
• Revisiting The Index Construction Of Proximity Graph-based Approximate Nearest Neighbor Search (2024)7.16
• Revisiting \(k\)-nearest Neighbor Graph Construction On High-dimensional Data : Experiments And Analyses (2021)0.00
• A Scalable Solution To The Nearest Neighbor Search Problem Through Local-search Methods On Neighbor Graphs (2017)3.58