Li, Yuliang ;
Wang, Jianguo ;
Pullman, Benjamin ;
Bandeira, Nuno ;
Papakonstantinou, Yannis
IndexBased, HighDimensional, Cosine Threshold Querying with Optimality Guarantees
Abstract
Given a database of vectors, a cosine threshold query returns all vectors in the database having cosine similarity to a query vector above a given threshold. These queries arise naturally in many applications, such as document retrieval, image search, and mass spectrometry. The present paper considers the efficient evaluation of such queries, providing novel optimality guarantees and exhibiting good performance on real datasets. We take as a starting point Fagin's wellknown Threshold Algorithm (TA), which can be used to answer cosine threshold queries as follows: an inverted index is first built from the database vectors during preprocessing; at query time, the algorithm traverses the index partially to gather a set of candidate vectors to be later verified against the similarity threshold. However, directly applying TA in its raw form misses significant optimization opportunities. Indeed, we first show that one can take advantage of the fact that the vectors can be assumed to be normalized, to obtain an improved, tight stopping condition for index traversal and to efficiently compute it incrementally. Then we show that one can take advantage of data skewness to obtain better traversal strategies. In particular, we show a novel traversal strategy that exploits a common data skewness condition which holds in multiple domains including mass spectrometry, documents, and image databases. We show that under the skewness assumption, the new traversal strategy has a strong, nearoptimal performance guarantee. The techniques developed in the paper are quite general since they can be applied to a large class of similarity functions beyond cosine.
BibTeX  Entry
@InProceedings{li_et_al:LIPIcs:2019:10313,
author = {Yuliang Li and Jianguo Wang and Benjamin Pullman and Nuno Bandeira and Yannis Papakonstantinou},
title = {{IndexBased, HighDimensional, Cosine Threshold Querying with Optimality Guarantees}},
booktitle = {22nd International Conference on Database Theory (ICDT 2019)},
pages = {11:111:20},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959771016},
ISSN = {18688969},
year = {2019},
volume = {127},
editor = {Pablo Barcelo and Marco Calautti},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2019/10313},
doi = {10.4230/LIPIcs.ICDT.2019.11},
annote = {Keywords: Vector databases, Similarity search, Cosine, Threshold Algorithm}
}
2019
Keywords: 

Vector databases, Similarity search, Cosine, Threshold Algorithm 
Seminar: 

22nd International Conference on Database Theory (ICDT 2019)

Issue date: 

2019 
Date of publication: 

2019 