Research article

Resumen

La búsqueda por similitud consiste en recuperar todos aquellos objetos dentro de una base de datos que sean parecidos o relevantes a una determinada consulta. Actualmente es un tema de gran interés para la comunidad científica debido a sus múltiples campos de aplicación, como la búsqueda de palabras e imágenes en la World Wide Web, reconocimiento de patrones, detección de plagio, bases de datos multimedia, entre otros. La búsqueda por similitud o en proximidad se modela matemáticamente a través de un espacio métrico, en el cual los objetos son representados como una caja negra donde la única información disponible es la distancia de este objeto a los otros. En general, el cálculo de la función de distancia es costoso y los sistemas de búsqueda operan a una gran tasa de consultas por unidad de tiempo. A fin de optimizar este procesamiento se han desarrollado numerosas estructuras métricas, que funcionan como índices y realizan un preprocesamiento de los datos a fin de disminuir las evaluaciones de distancia al momento de la búsqueda. Por otro lado, la necesidad de procesar grandes volúmenes de datos hace poco factible la utilización de una estructura en aplicaciones reales si ésta no considera la utilización de entornos de procesamiento paralelo. Existen una serie de tecnologías para realizar implementaciones de procesamiento paralelo. Se incluyen entre las más vigentes las tecnologías basadas en arquitecturas multi-CPU (multi-core) y GPU / multi-GPU, que son interesantes debido a las altas prestaciones y los bajos costes involucrados. En el presente artículo se aborda la búsqueda por similitud y la implementación de estructuras métricas sobre entornos paralelos. En la sección 2 se presenta el estado del arte en los temas relacionados a búsqueda por similitud con estructuras métricas y tecnologías de paralelización. Se proponen análisis comparativos sobre experimentos que buscan identificar el comportamiento de un conjunto de espacios métricos y estructuras métricas seleccionados sobre plataformas de procesamiento basadas en multicore y GPU en la sección 3. Finalmente, se recopilan las conclusiones obtenidas y sugerencias de trabajos futuros en la sección 4.

Abstract

Similarity search consists on retrieving objects within a database that are similar or relevant to a particular query. It is a topic of great interest to scientific community because of its many fields of application, such as searching for words and images on the World Wide Web, pattern recognition, detection of plagiarism, multimedia databases, among others. Search by similarity or proximity mathematically modeled through a metric space in which objects are represented as a black box where the only information available is the distance from the object to the other. In general, the calculation of the distance function is costly and search systems operate at a high query rate per unit time. To optimize this process have been developed numerous metric structures that function as indexes and perform preprocessing of data to decrease the distance evaluations when the search. Furthermore, the need to process large volumes of data makes unfeasible the use of a structure in real applications if it does not consider the use of parallel processing environments. There are a number of technologies for parallel processing implementations. Technologies based on multi-CPU (multi-core) and GPU / multi-GPU architectures that are interesting due to the high performance and low costs involved. In this article the similarity search and implementation of metric structures on parallel environments is addressed. In section 2 the state of the art is presented on issues related to search by similarity metric structures and parallelization technologies. Comparative analysis of experiments seeking to identify the behavior of a set of metric spaces and metric structures on selected processing platforms based on multicore and GPU in the proposed section 3. Finally, the conclusions and suggestions for future work are summarized in section 4.

Curation

La curación es realizada aplicando una demarcación epistemológica, la cual permite valorar un trabajo científico para la web semántica - ⓘ

Curator

ⓘ