Priority Vantage Points Structures for Similarity Queries in Metric Spaces

Abstract

Similarity search structures for metric spaces have different performance characteristics depending on the properties of the data, construction cost, and space consumption. Nonetheless, recent experiments seem to favor vantage points-based methods such as LAESA, Spaghettis, and FQA if they are allowed to use enough pivots. By using more pre-processing time, these methods can produce superior query performance in terms of distance computations. Unfortunately this also causes them to use more space and CPU time than other structures. In this paper we explore ways to organize the basic structure according to distance relations between database objects, pivots and query objects. We introduce the priority vantage points method, which reduces the CPU overhead without adding extra space requirements. The Kvp structure is also introduced as an improvement, which stores less distance values than other vantage points algorithms. Kvp needs one sequential scan over the index data, making it very suitable to be stored on disk. We show that Kvp is superior to the other methods given same amount of storage.