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

Additional URL

https://doi.org/10.1109/ICDE60146.2024.00326

This document is currently not available here.

Share

COinS