Efficient and Effective Retrieval of Dense-Sparse Hybrid Vectors using Graph-based Approximate Nearest Neighbor Search

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Zhang, Haoyu, Liu, Jun, Zhu, Zhenhua, Zeng, Shulin, Sheng, Maojia, Yang, Tao, Dai, Guohao, Wang, Yu
Format:	Preprint
Published:	2024
Subjects:	Information Retrieval
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

_version_	1866912089333825536
author	Zhang, Haoyu Liu, Jun Zhu, Zhenhua Zeng, Shulin Sheng, Maojia Yang, Tao Dai, Guohao Wang, Yu
author_facet	Zhang, Haoyu Liu, Jun Zhu, Zhenhua Zeng, Shulin Sheng, Maojia Yang, Tao Dai, Guohao Wang, Yu
contents	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.
format	Preprint
id	arxiv_https___arxiv_org_abs_2410_20381
institution	arXiv
publishDate	2024
record_format	arxiv
spellingShingle	Efficient and Effective Retrieval of Dense-Sparse Hybrid Vectors using Graph-based Approximate Nearest Neighbor Search Zhang, Haoyu Liu, Jun Zhu, Zhenhua Zeng, Shulin Sheng, Maojia Yang, Tao Dai, Guohao Wang, Yu Information Retrieval 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.
title	Efficient and Effective Retrieval of Dense-Sparse Hybrid Vectors using Graph-based Approximate Nearest Neighbor Search
topic	Information Retrieval
url	https://arxiv.org/abs/2410.20381