用图搜索统一处理稀疏稠密向量,提升检索效率与准确率。
Efficient and Effective Retrieval of Dense-Sparse Hybrid Vectors using Graph-based Approximate Nearest Neighbor Search
- 通过分布对齐优化稀疏稠密向量距离统计,提升准确率1%~9%
- 采用自适应两阶段计算+稀疏向量剪枝,加速2.1倍
- 在同等精度下吞吐量达现有方法8.9~11.7倍,适合大规模检索
文本嵌入向量的近似最近邻搜索(ANNS)广泛应用于信息检索,其中稀疏向量和稠密向量是两种重要表征方式。尽管融合二者可提升准确性,但目前分别搜索的方法存在可扩展性差、系统复杂度高的问题。而构建统一索引又面临准确率与效率的挑战。为此,我们提出一种基于图的稠密-稀疏混合向量近似最近邻搜索算法。首先,设计分布对齐方法,通过预采样分析稠密与稀疏向量的距离分布统计,使准确率提升1%~9%;其次,设计自适应两阶段计算策略,先仅计算稠密距离,再补充混合距离,并对稀疏向量进行剪枝,实现约2.1倍加速。大量实验表明,在相同准确率下,该算法吞吐量达到现有混合向量搜索算法的8.9~11.7倍。
原文摘要 · Abstract (English)
ANNS for embedded vector representations of texts is commonly used in information retrieval, with two important information representations being sparse and dense vectors. While it has been shown that combining these representations improves accuracy, the current method of conducting sparse and dense vector searches separately suffers from low scalability and high system complexity. Alternatively, building a unified index faces challenges with accuracy and efficiency. To address these issues, we propose a graph-based ANNS algorithm for dense-sparse hybrid vectors. Firstly, we propose a distribution alignment method to improve accuracy, which pre-samples dense and sparse vectors to analyze their distance distribution statistic, resulting in a 1%$\sim$9% increase in accuracy. Secondly, to improve efficiency, we design an adaptive two-stage computation strategy that initially computes dense distances only and later computes hybrid distances. Further, we prune the sparse vectors to speed up the calculation. Compared to naive implementation, we achieve $\sim2.1\times$ acceleration. Thorough experiments show that our algorithm achieves 8.9x$\sim$11.7x throughput at equal accuracy compared to existing hybrid vector search algorithms.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。