Efficient And Effective Retrieval Of Dense-sparse Hybrid Vectors Using Graph-based Approximate Nearest Neighbor Search

Abstract

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

Stats

• citations0
• S2 citations—
• github stars0
• HF likes0
• heat score0.00
• arxiv keyzhang2024efficient

Related papers

• Lucene For Approximate Nearest-neighbors Search On Arbitrary Dense Vectors (2019)0.00
• HQANN: Efficient And Robust Similarity Search For Hybrid Queries With Structured And Unstructured Constraints (2022)9.76
• DGAI: Decoupled On-disk Graph-based ANN Index For Efficient Updates And Queries (2025)0.00
• A Comprehensive Survey And Experimental Comparison Of Graph-based Approximate Nearest Neighbor Search (2021)17.35
• Frequency-aware Graph Construction And Search For Dynamic Vector Databases (2025)0.00
• Scalable Overload-aware Graph-based Index Construction For 10-billion-scale Vector Similarity Search (2025)4.52
• High Dimensional Similarity Search With Satellite System Graph: Efficiency, Scalability, And Unindexed Query Compatibility (2019)17.30
• DEG: Efficient Hybrid Vector Search Using The Dynamic Edge Navigation Graph (2025)6.34