CRouting: Reducing Expensive Distance Calls in Graph-Based Approximate Nearest Neighbor Search

• URL: http://arxiv.org/abs/2509.00365v1
• Date: Sat, 30 Aug 2025 05:27:09 GMT
• Title: CRouting: Reducing Expensive Distance Calls in Graph-Based Approximate Nearest Neighbor Search
• Authors: Zhenxin Li, Shuibing He, Jiahao Guo, Xuechen Zhang, Xian-He Sun, Gang Chen,
• Abstract summary: Approximate nearest neighbor search (ANNS) is a crucial problem in information retrieval and AI applications.<n>We propose a novel routing strategy named CRouting, which bypasses unnecessary distance computations.<n>Our experiments show that CRouting reduces the number of distance computations by up to 41.5% and boosts queries per second by up to 1.48$times$ on two predominant graph indexes.
• Score: 9.557937699715124
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Approximate nearest neighbor search (ANNS) is a crucial problem in information retrieval and AI applications. Recently, there has been a surge of interest in graph-based ANNS algorithms due to their superior efficiency and accuracy. However, the repeated computation of distances in high-dimensional spaces constitutes the primary time cost of graph-based methods. To accelerate the search, we propose a novel routing strategy named CRouting, which bypasses unnecessary distance computations by exploiting the angle distributions of high-dimensional vectors. CRouting is designed as a plugin to optimize existing graph-based search with minimal code modifications. Our experiments show that CRouting reduces the number of distance computations by up to 41.5% and boosts queries per second by up to 1.48$\times$ on two predominant graph indexes, HNSW and NSG. Code is publicly available at https://github.com/ISCS-ZJU/CRouting.

Related papers

• GPU-Accelerated Algorithms for Graph Vector Search: Taxonomy, Empirical Study, and Research Directions [54.570944939061555]
  We present a comprehensive study of GPU-accelerated graph-based vector search algorithms.<n>We establish a detailed taxonomy of GPU optimization strategies and clarify the mapping between algorithmic tasks and hardware execution units.<n>Our findings offer clear guidelines for designing scalable and robust GPU-powered approximate nearest neighbor search systems.
  arXiv  Detail & Related papers  (2026-02-10T16:18:04Z)
• Efficient Sketching and Nearest Neighbor Search Algorithms for Sparse Vector Sets [16.768212375976546]
  We introduce a set of novel data structures and algorithmic methods for sparse ANNS.<n>Our contributions range from a theoretically-grounded sketching algorithm for sparse vectors to reduce their effective dimensionality.<n>Our final algorithm, dubbed Seismic, reaches sub-millisecond latency with high accuracy on a large-scale benchmark dataset.
  arXiv  Detail & Related papers  (2025-09-29T14:02:45Z)
• SymphonyQG: Towards Symphonious Integration of Quantization and Graph for Approximate Nearest Neighbor Search [13.349178274732862]
  We present SymphonyQG, which achieves more symphonious integration of quantization and graph. Based on extensive experiments on real-world datasets, SymphonyQG establishes the new state-of-the-art in terms of the time-accuracy trade-off.
  arXiv  Detail & Related papers  (2024-11-19T04:51:08Z)
• Probabilistic Routing for Graph-Based Approximate Nearest Neighbor Search [3.934351369702082]
  Approximate nearest neighbor search (ANNS) in high-dimensional spaces is a pivotal challenge in the field of machine learning. This paper introduces a method that offers a probabilistic guarantee when exploring a node's neighbors in the graph. We then introduce PEOs, a novel approach that efficiently identifies which neighbors in the graph should be considered for exact distance calculation.
  arXiv  Detail & Related papers  (2024-02-17T18:08:37Z)
• SpirDet: Towards Efficient, Accurate and Lightweight Infrared Small Target Detector [60.42293239557962]
  We propose SpirDet, a novel approach for efficient detection of infrared small targets. We employ a new dual-branch sparse decoder to restore the feature map. Extensive experiments show that the proposed SpirDet significantly outperforms state-of-the-art models.
  arXiv  Detail & Related papers  (2024-02-08T05:06:14Z)
• Efficient k-NN Search with Cross-Encoders using Adaptive Multi-Round CUR Decomposition [77.4863142882136]
  Cross-encoder models are prohibitively expensive for direct k-nearest neighbor (k-NN) search. We propose ADACUR, a method that adaptively, iteratively, and efficiently minimizes the approximation error for the practically important top-k neighbors.
  arXiv  Detail & Related papers  (2023-05-04T17:01:17Z)
• A Theoretical Analysis Of Nearest Neighbor Search On Approximate Near Neighbor Graph [51.880164098926166]
  Graph-based algorithms have demonstrated state-of-the-art performance in the nearest neighbor search (NN-Search) problem. There exists a practice-to-theory gap in the graph-based NN-Search algorithms. We present theoretical guarantees of solving NN-Search via greedy search on ANN-Graph for low dimensional and dense vectors.
  arXiv  Detail & Related papers  (2023-03-10T21:18:34Z)
• Rapid Person Re-Identification via Sub-space Consistency Regularization [51.76876061721556]
  Person Re-Identification (ReID) matches pedestrians across disjoint cameras. Existing ReID methods adopting real-value feature descriptors have achieved high accuracy, but they are low in efficiency due to the slow Euclidean distance computation. We propose a novel Sub-space Consistency Regularization (SCR) algorithm that can speed up the ReID procedure by 0.25$ times.
  arXiv  Detail & Related papers  (2022-07-13T02:44:05Z)
• FINGER: Fast Inference for Graph-based Approximate Nearest Neighbor Search [20.928821121591493]
  We propose FINGER, a fast inference method to achieve efficient graph search. FINGER approximates the distance function by estimating angles between neighboring residual vectors with low-rank bases and distribution matching. Empirically, accelerating a popular graph-based method named HNSW by FINGER is shown to outperform existing graph-based methods by 20%-60% across different benchmark datasets.
  arXiv  Detail & Related papers  (2022-06-22T22:30:46Z)
• Towards Efficient Graph Convolutional Networks for Point Cloud Handling [181.59146413326056]
  We aim at improving the computational efficiency of graph convolutional networks (GCNs) for learning on point clouds. A series of experiments show that optimized networks have reduced computational complexity, decreased memory consumption, and accelerated inference speed.
  arXiv  Detail & Related papers  (2021-04-12T17:59:16Z)
• Scaling Graph Neural Networks with Approximate PageRank [64.92311737049054]
  We present the PPRGo model which utilizes an efficient approximation of information diffusion in GNNs. In addition to being faster, PPRGo is inherently scalable, and can be trivially parallelized for large datasets like those found in industry settings. We show that training PPRGo and predicting labels for all nodes in this graph takes under 2 minutes on a single machine, far outpacing other baselines on the same graph.
  arXiv  Detail & Related papers  (2020-07-03T09:30:07Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.