Solving Multiple Queries through a Permutation Index in GPU

Abstract

Query-by-content by means of similarity
search is a fundamental operation for applications that
deal with multimedia data. For this kind of query
it is meaningless to look for elements exactly equal
to the one given as query. Instead, we need to
measure dissimilarity between the query object and each
database object. The metric space model is a paradigm
that allows modeling all similarity search problems.
Metric databases permit to store objects from a metric
space and efficiently perform similarity queries over
them, in general, by reducing the number of distance
evaluations needed. Therefore, the goal is to preprocess
a particular dataset in such a way that queries can be
answered with as few distance computations as possible.
Moreover, for a very large metric database it is not
enough to preprocess the dataset by building an index,
it is also necessary to speed up the queries via high
performance computing using GPU. In this work we
show an implementation of a pure GPU architecture to
build a Permutation Index used for approximate similarity
search on databases of different data nature and to
solve many queries at the same time. Besides, we
evaluate the tradeoff between the answer quality and
time performance of our implementation.