DEG: Efficient Hybrid Vector Search Using the Dynamic Edge Navigation Graph
Open Access
- 10 February 2025
- journal article
- Published by Association for Computing Machinery (ACM) in Proceedings of the ACM on Management of Data
- Vol. 3 (1) , 1-28
Abstract
Bimodal data, such as image-text pairs, has become increasingly prevalent in the digital era. The Hybrid Vector Query (HVQ) is an effective approach for querying such data and has recently garnered considerable attention from researchers. It calculates similarity scores for objects represented by two vectors using a weighted sum of each individual vector's similarity, with a query-specific parameter α to determine the weight. Existing methods for HVQ typically construct Approximate Nearest Neighbors Search (ANNS) indexes with a fixed α value. This leads to significant performance degradation when the query's α dynamically changes based on the different scenarios and needs. In this study, we introduce the Dynamic Edge Navigation Graph ( DEG ), a graph-based ANNS index that maintains efficiency and accuracy with changing α values. It includes three novel components: (1) a greedy Pareto frontier search algorithm to compute a candidate neighbor set for each node, which comprises the node's approximate nearest neighbors for all possible α values; (2) a dynamic edge pruning strategy to determine the final edges from the candidate set and assign each edge an active range. This active range enables the dynamic use of the Relative Neighborhood Graph's pruning strategy based on the query's α values, skipping redundant edges at query time and achieving a better accuracy-efficiency trade-off; and (3) an edge seed method that accelerates the querying process. Extensive experiments on real-world datasets show that DEG demonstrates superior performance compared to existing methods under varying α values.Keywords
All Related Versions
This publication has 50 references indexed in Scilit:
- PM-LSH: a fast and accurate in-memory framework for high-dimensional approximate NN and closest pair searchThe VLDB Journal, 2021
- Location- and keyword-based querying of geo-textual data: a surveyThe VLDB Journal, 2021
- Connecting Vision and Language with Localized Narratives2020
- Accelerating Large-Scale Molecular Similarity Search through Exploiting High Performance Computing2019
- S2R-tree: a pivot-based indexing structure for semantic-aware spatial keyword searchGeoInformatica, 2019
- Semantic-aware top-k spatial keyword queriesWorld Wide Web, 2017
- Approximate nearest neighbor algorithm based on navigable small world graphsInformation Systems, 2014
- Constructing the relative neighborhood graph in 3-dimensional Euclidean spaceDiscrete Applied Mathematics, 1991
- The relative neighbourhood graph of a finite planar setPattern Recognition, 1980
- On the shortest spanning subtree of a graph and the traveling salesman problemProceedings of the American Mathematical Society, 1956