# Optimization of Indexing Based on k-Nearest Neighbor Graph for Proximity Search in High-dimensional Data

arXiv: https://arxiv.org/abs/1810.07355 · HTML: https://mlsanity.com/paper/1810.07355/

## Key facts

- Cited by 20 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 17 Oct 2018.

## Built on by (most cited first, 20 of 20)

- [Results of the NeurIPS'21 Challenge on Billion-Scale Approximate Nearest Neighbor Search](https://mlsanity.com/paper/2205.03763/) (2022)
- [SPANN: Highly-efficient Billion-scale Approximate Nearest Neighbor Search](https://mlsanity.com/paper/2111.08566/) (2021)
- [CAGRA: Highly Parallel Graph Construction and Approximate Nearest Neighbor Search for GPUs](https://mlsanity.com/paper/2308.15136/) (2023)
- [Similarity search in the blink of an eye with compressed indices](https://mlsanity.com/paper/2304.04759/) (2023)
- [Worst-case Performance of Popular Approximate Nearest Neighbor Search Implementations: Guarantees and Limitations](https://mlsanity.com/paper/2310.19126/) (2023)
- [DEANN: Speeding up Kernel-Density Estimation using Approximate Nearest Neighbor Search](https://mlsanity.com/paper/2107.02736/) (2021)
- [PDX: A Data Layout for Vector Similarity Search](https://mlsanity.com/paper/2503.04422/) (2025)
- [Automating Nearest Neighbor Search Configuration with Constrained Optimization](https://mlsanity.com/paper/2301.01702/) (2023)
- [Orientation-Guided Contrastive Learning for UAV-View Geo-Localisation](https://mlsanity.com/paper/2308.00982/) (2023)
- [VIBE: Vector Index Benchmark for Embeddings](https://mlsanity.com/paper/2505.17810/) (2025)
- [LoRANN: Low-Rank Matrix Factorization for Approximate Nearest Neighbor Search](https://mlsanity.com/paper/2410.18926/) (2024)
- [LSM-VEC: A Large-Scale Disk-Based System for Dynamic Vector Search](https://mlsanity.com/paper/2505.17152/) (2025)
- [General and Practical Tuning Method for Off-the-Shelf Graph-Based Index: SISAP Indexing Challenge Report by Team UTokyo](https://mlsanity.com/paper/2309.00472/) (2023)
- [Exploring Large Action Sets with Hyperspherical Embeddings using von Mises-Fisher Sampling](https://mlsanity.com/paper/2507.00518/) (2025)
- [Similarity search on neighbor's graphs with automatic Pareto optimal performance and minimum expected quality setups based on hyperparameter optimization](https://mlsanity.com/paper/2201.07917/) (2022)
- [Theoretical and Empirical Analysis of Adaptive Entry Point Selection for Graph-based Approximate Nearest Neighbor Search](https://mlsanity.com/paper/2402.04713/) (2024)
- [Optimizing Domain-Specific Image Retrieval: A Benchmark of FAISS and Annoy with Fine-Tuned Features](https://mlsanity.com/paper/2412.01555/) (2024)
- [Infinity Search: Approximate Vector Search with Projections on q-Metric Spaces](https://mlsanity.com/paper/2506.06557/) (2025)
- [All-in-one Graph-based Indexing for Hybrid Search on GPUs](https://mlsanity.com/paper/2511.00855/) (2025)
- [Mycelium-Index: A Streaming Approximate Nearest Neighbor Index with Myelial Edge Decay, Traffic-Driven Reinforcement, and Adaptive Living Hierarchy](https://mlsanity.com/paper/2604.11274/) (2026)

## Abstract (arXiv)

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.