Publication Type

Journal Article

Version

publishedVersion

Publication Date

6-2022

Abstract

Similarity search fnds similar objects for a given query object based on a certain similarity metric. Similarity search in metric spaces has attracted increasing attention, as the metric space can accommodate any type of data and support fexible distance metrics. However, a metric space only models a single data type with a specifc similarity metric. In contrast, a multi-metric space combines multiple metric spaces to simultaneously model a variety of data types and a collection of associated similarity metrics. Thus, a multi-metric space is capable of performing similarity search over any combination of metric spaces. Many studies focus on indexing a single metric space, while only a few aims at indexing multi-metric space to accelerate similarity search. In this paper, we propose DESIRE, an efcient dynamic cluster-based forest index for similarity search in multi-metric spaces. DESIRE frst selects high-quality centers to cluster objects into compact regions, and then employs B+ -trees to efectively index distances between centers and corresponding objects. To support dynamic scenarios, efcient update strategies are developed. Further, we provide fltering techniques to accelerate similarity queries in multi-metric spaces. Extensive experiments on four real datasets demonstrate the superior efciency and scalability of our proposed DESIRE compared with the state-of-the-art multi-metric space indexes.

Discipline

Databases and Information Systems

Research Areas

Data Science and Engineering

Publication

Proceedings of the VLDB Endowment

Volume

15

Issue

10

First Page

2121

Last Page

2133

ISSN

2150-8097

Identifier

10.14778/3547305.3547317

Publisher

VLDB Endowment

Additional URL

https://www.vldb.org/pvldb/vol15/p2121-gao.pdf

Download

Share

COinS