Optimization Of Indexing Based On K-nearest Neighbor Graph For Proximity Search In High-dimensional Data

Abstract

Searching for high-dimensional vector data with high accuracy is an inevitable search technology for various types of data. Graph-based indexes are known to reduce the query time for high-dimensional data. To further improve the query time by using graphs, we focused on the indegrees and outdegrees of graphs. While a sufficient number of incoming edges (indegrees) are indispensable for increasing search accuracy, an excessive number of outgoing edges (outdegrees) should be suppressed so as to not increase the query time. Therefore, we propose three degree-adjustment methods: static degree adjustment of not only outdegrees but also indegrees, dynamic degree adjustment with which outdegrees are determined by the search accuracy users require, and path adjustment to remove edges that have alternative search paths to reduce outdegrees. We also show how to obtain optimal degree-adjustment parameters and that our methods outperformed previous methods for image and textual data.

Stats

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

Related papers

• Fast Approximate Nearest Neighbor Search With A Dynamic Exploration Graph Using Continuous Refinement (2023)0.00
• A Scalable Solution To The Nearest Neighbor Search Problem Through Local-search Methods On Neighbor Graphs (2017)3.58
• Hd-index: Pushing The Scalability-accuracy Boundary For Approximate Knn Search In High-dimensional Spaces (2018)14.02
• Revisiting The Index Construction Of Proximity Graph-based Approximate Nearest Neighbor Search (2024)7.16
• Accurate And Fast Retrieval For Complex Non-metric Data Via Neighborhood Graphs (2019)0.00
• Revisiting \(k\)-nearest Neighbor Graph Construction On High-dimensional Data : Experiments And Analyses (2021)0.00
• Fast-convergent Proximity Graphs For Approximate Nearest Neighbor Search (2025)0.00
• DEG: Efficient Hybrid Vector Search Using The Dynamic Edge Navigation Graph (2025)6.34