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.

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

QUEST: Query-Aware Learned Metric Index for Similarity Search

  • Hongzhao Liu,
  • Yaqi Wang,
  • Bin Wang,
  • Xiaochun Yang,
  • Boce Chu,
  • Jin Zhu

摘要

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.