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.