Solving Multiple Queries through a Permutation Index in GPU

Authors

  • Mariela Lopresti LIDIC. Universidad Nacional de San Luis.
  • Natalia Miranda LIDIC. Universidad Nacional de San Luis.
  • Fabiana Piccoli LIDIC. Universidad Nacional de San Luis.
  • Nora Reyes LIDIC. Universidad Nacional de San Luis.

DOI:

https://doi.org/10.13053/cys-17-3-1560

Keywords:

Metric space, approximate similarity search, permutation index, high performance computing, GPU.

Abstract

Query-by-content by means of similaritysearch is a fundamental operation for applications thatdeal with multimedia data. For this kind of queryit is meaningless to look for elements exactly equalto the one given as query. Instead, we need tomeasure dissimilarity between the query object and eachdatabase object. The metric space model is a paradigmthat allows modeling all similarity search problems.Metric databases permit to store objects from a metricspace and efficiently perform similarity queries overthem, in general, by reducing the number of distanceevaluations needed. Therefore, the goal is to preprocessa particular dataset in such a way that queries can beanswered with as few distance computations as possible.Moreover, for a very large metric database it is notenough to preprocess the dataset by building an index,it is also necessary to speed up the queries via highperformance computing using GPU. In this work weshow an implementation of a pure GPU architecture tobuild a Permutation Index used for approximate similaritysearch on databases of different data nature and tosolve many queries at the same time. Besides, weevaluate the tradeoff between the answer quality andtime performance of our implementation.

Downloads

Published

2013-10-01

Issue

Vol. 17 No. 3 (2013): 17(3) July-September 2013

Section

Articles

License 

Hereby I transfer exclusively to the Journal "Computación y 
Sistemas", published by the Computing Research Center (CIC-IPN),
the Copyright of the aforementioned paper. I also accept that these 
rights will not be transferred to any other publication, in any other 
format, language or other existing means of developing.
I certify that the paper has not been previously disclosed or simultaneo
usly submitted to any other publication, and that it does not contain 
material whose publication would violate the Copyright or other 
proprietary rights of any person, company or institution. I certify that 
I have the permission from the institution or company where I work or 
study to publish this work.
The representative author accepts the responsibility for the publication
of this paper on behalf of each and every one of the authors. 
This transfer is subject to the following conditions:
  • The authors retain all ownership rights (such as patent rights) of this work, except for the publishing rights transferred to the CIC, through this document.
  • Authors retain the right to publish the work in whole or in part in any book they are the authors or publishers. They can also make use of this work in conferences, courses, personal web pages, and so on.
  • Authors may include working as part of his thesis, for non-profit distribution only.