通过向量角度分布优化图搜索，减少41.5%距离计算
CRouting: Reducing Expensive Distance Calls in Graph-Based Approximate Nearest Neighbor Search
- 利用高维向量角度分布设计新路由策略
- 在HNSW和NSG上降低41.5%距离计算量
- 无需修改代码即可加速现有图索引
近似最近邻搜索（ANNS）是信息检索与人工智能应用中的关键问题。近年来，图基方法因高效准确而备受关注，但高维空间中重复计算距离成为主要耗时瓶颈。为此，我们提出一种名为CRouting的新路由策略，通过利用高维向量的角度分布，避免不必要的距离计算。CRouting可作为插件集成到现有图基搜索中，仅需少量代码修改。实验表明，该方法在两个主流图索引HNSW和NSG上，将距离计算次数减少最多达41.5%，查询吞吐量提升最高达1.48倍。代码已公开于https://github.com/ISCS-ZJU/CRouting。
原文摘要 · Abstract (English)
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.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。