文章基本信息

标题：Solving Multiple Queries through a Permutation Index in GPU
本地全文：下载
作者：Mariela Lopresti ; Natalia Miranda ; Fabiana Piccoli 等
期刊名称：Computación y Sistemas
印刷版ISSN：1405-5546
出版年度：2013
卷号：17
期号：3
页码：341-356
语种：English
出版社：Instituto Politécnico Nacional
摘要：Realizar consultas por contenido, a través de búsquedas de similitud, es una operación fundamental para aplicaciones relacionadas con datos multimedia. En este tipo de consultas no tiene sentido buscar elementos exactamente iguales a uno dado como consulta. En su lugar, es necesario medirla disimilitud entre el objeto de consulta y cada objeto de la base de datos. El modelo de espacio métrico es un paradigma que permite modelar todos los problemas de búsqueda por similitud. Las bases de datos métricas permiten el almacenamiento de objetos de un espacio métrico y responder consultas por similitud de manera eficiente, generalmente, mediante la reducción del número de evaluaciones de distancia. En consecuencia, el objetivo es pre-procesar el conjunto de datos de manera que las consultas pueden ser respondidas con el menor numero posible de c alculos de distancia. M as aun, para grandes bases de datos m etricas no basta con procesar previamente el conjunto de datos mediante la creación de un índice, también es necesario acelerar las consultas mediante el uso de computación de alto desempeño, una alternativa es utilizar GPU. En este trabajo se muestra una implementación de una arquitectura de GPU pura para construir el Pemutation Index, el cual nos permite resolver en paralelo múltiples consultas por similitud aproximadas en bases de datos de diferente naturaleza. Adem as se evalúa el compromiso entre la calidad de respuesta y el desempeño de nuestra aplicaci on. Finalmente se presentan resultados experimentales
其他摘要：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.
关键词：Metric space; approximate similarity search; permutation index; high performance computing; GPU;Espacios métricos; búsquedas; aproximadas por similitud; índice de permutación; computación de alto desempeño; GPU