HJG: An effective hierarchical joint graph for ANNS in multi-metric spaces
Publication Type
Conference Proceeding Article
Publication Date
5-2024
Abstract
Owing to the widespread deployment of smartphones and networked devices, massive amount of data in different types are generated every day, including numeric data, locations, text data, images, etc. Nearest neighbour search in multi-metric spaces has attracted much attention, as it can accommodate any type of data and support search on flexible combinations of multiple metrics. However, most existing methods focus on single metric queries, failing to answer multi-metric queries efficiently due to the complex metric combinations. In this paper, for the first time, we study the approximate nearest neighbour search (ANNS) in multi-metric spaces, and propose HJG, a hierarchical joint graph, to solve the multi-metric query efficiently and effectively. HJG constructs hierarchical graphs for modeling objects of various types, and applies our presented balancing techniques to improve the graph distribution. To support efficient and accurate nearest neighbour search, we join individual graphs dynamically with high efficiency, and develop filtering techniques with efficient search strategy for HJG. Extensive experiments on four datasets demonstrate the superior effectiveness and scalability of our proposed HJG.
Keywords
Accuracy, Costs, Filtering, Scalability, Graphics processing units, Extraterrestrial measurements, Search problems
Discipline
Databases and Information Systems
Research Areas
Data Science and Engineering
Publication
Proceedings of the 2024 IEEE 40th International Conference on Data Engineering (ICDE), Utrecht, Netherlands, May 13-16
First Page
4275
Last Page
4287
ISBN
9798350317169
Identifier
10.1109/ICDE60146.2024.00326
Publisher
IEEE
City or Country
Los Alamitos, CA
Citation
ZHU, Yifan; CHEN, Lu; GAO, Yunjun; MA, Ruiyao; ZHENG, Baihua; and ZHAO, Jingwen.
HJG: An effective hierarchical joint graph for ANNS in multi-metric spaces. (2024). Proceedings of the 2024 IEEE 40th International Conference on Data Engineering (ICDE), Utrecht, Netherlands, May 13-16. 4275-4287.
Available at: https://ink.library.smu.edu.sg/sis_research/9285
Additional URL
https://doi.org/10.1109/ICDE60146.2024.00326