QUEST: Query-Aware Learned Metric Index for Similarity Search
摘要
Similarity search in metric space is one of the fundamental operations in the era of big data. To accelerate similarity searches, a large number of metric access methods (both traditional and learning-based) have been extensively studied. Most existing metric index structures are built based on the data, without considering the distribution of the queries that have been received. And previous research has shown that using the known query distribution can improve the index structure for future query processing. In this paper, we propose QUEST, a learned metric index for metric similarity search, which adapts to optimize querying costs given a query workload. We first partition the data objects into K clusters, where K is determined adaptively based on a given query workload, with the goal of minimizing search overhead by reducing search space. Then, for each cluster, we propose a query-guided pivot-based data transformation technique and a learned index to support similarity search in metric spaces. Extensive experiments on real-world and synthetic datasets show that our proposal can achieve better query performance compared with state-of-the-art methods.