Accurate And Fast Retrieval For Complex Non-metric Data Via Neighborhood Graphs

Abstract

We demonstrate that a graph-based search algorithm-relying on the construction of an approximate neighborhood graph-can directly work with challenging non-metric and/or non-symmetric distances without resorting to metric-space mapping and/or distance symmetrization, which, in turn, lead to substantial performance degradation. Although the straightforward metrization and symmetrization is usually ineffective, we find that constructing an index using a modified, e.g., symmetrized, distance can improve performance. This observation paves a way to a new line of research of designing index-specific graph-construction distance functions.

Stats

• citations0
• S2 citations—
• github stars0
• HF likes0
• heat score0.00
• arxiv keyboytsov2019accurate

Related papers

• A Scalable Solution To The Nearest Neighbor Search Problem Through Local-search Methods On Neighbor Graphs (2017)3.58
• Fast Approximate Nearest Neighbor Search With A Dynamic Exploration Graph Using Continuous Refinement (2023)0.00
• Optimization Of Indexing Based On K-nearest Neighbor Graph For Proximity Search In High-dimensional Data (2018)0.00
• Fast-convergent Proximity Graphs For Approximate Nearest Neighbor Search (2025)0.00
• Navigable Graphs For High-dimensional Nearest Neighbor Search: Constructions And Limits (2024)4.52
• Indexing Metric Spaces For Exact Similarity Search (2020)10.85
• Fast Approximate Nearest Neighbor Search With The Navigating Spreading-out Graph (2017)18.20
• Exact Computation Of A Manifold Metric, Via Lipschitz Embeddings And Shortest Paths On A Graph (2017)5.24