{"ID":2876416,"CreatedAt":"2026-06-01T04:54:23.091178241Z","UpdatedAt":"2026-06-01T04:54:23.091178241Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2509.00365","arxiv_id":"2509.00365","title":"CRouting: Reducing Expensive Distance Calls in Graph-Based Approximate Nearest Neighbor Search","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.","short_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 t...","url_abs":"https://arxiv.org/abs/2509.00365","url_pdf":"https://arxiv.org/pdf/2509.00365v1","authors":"[\"Zhenxin Li\",\"Shuibing He\",\"Jiahao Guo\",\"Xuechen Zhang\",\"Xian-He Sun\",\"Gang Chen\"]","published":"2025-08-30T05:27:09Z","proceeding":"cs.DB","tasks":"[\"cs.DB\",\"cs.IR\"]","methods":"[]","has_code":false,"code_links":[{"ID":610293,"CreatedAt":"2026-06-01T04:54:23.091178241Z","UpdatedAt":"2026-06-01T04:54:23.091178241Z","DeletedAt":null,"paper_id":2876416,"paper_url":"https://arxiv.org/abs/2509.00365","paper_title":"CRouting: Reducing Expensive Distance Calls in Graph-Based Approximate Nearest Neighbor Search","repo_url":"https://github.com/ISCS-ZJU/CRouting","is_official":false,"mentioned_in_paper":false,"mentioned_in_github":true,"github_stars":0}]}