Evaluación de estructuras métricas con Unidades de Procesamiento Gráfico de Propósito General

La bAosqueda 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 interA©s para la comunidad cientA­fica debido a sus mAoltiples campos de aplicaciA³n, como la bAosqueda de palabras e imAigenes en la World Wide Web, reconocimiento de patrones, detecciA³n de plagio, bases de datos multimedia, entre otros. La bAosqueda por similitud o en proximidad se modela matemAiticamente a travA©s de un espacio mA©trico, en el cual los objetos son representados como una caja negra donde la Aonica informaciA³n disponible es la distancia de este objeto a los otros. En general, el cAilculo de la funciA³n de distancia es costoso y los sistemas de bAosqueda operan a una gran tasa de consultas por unidad de tiempo. A fin de optimizar este procesamiento se han desarrollado numerosas estructuras mA©tricas, que funcionan como A­ndices y realizan un preprocesamiento de los datos a fin de disminuir las evaluaciones de distancia al momento de la bAosqueda. Por otro lado, la necesidad de procesar grandes volAomenes de datos hace poco factible la utilizaciA³n de una estructura en aplicaciones reales si A©sta no considera la utilizaciA³n de entornos de procesamiento paralelo. Existen una serie de tecnologA­as para realizar implementaciones de procesamiento paralelo. Se incluyen entre las mAis vigentes las tecnologA­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 artA­culo se aborda la bAosqueda por similitud y la implementaciA³n de estructuras mA©tricas sobre entornos paralelos. En la secciA³n 2 se presenta el estado del arte en los temas relacionados a bAosqueda por similitud con estructuras mA©tricas y tecnologA­as de paralelizaciA³n. Se proponen anAilisis comparativos sobre experimentos que buscan identificar el comportamiento de un conjunto de espacios mA©tricos y estructuras mA©tricas seleccionados sobre plataformas de procesamiento basadas en multicore y GPU en la secciA³n 3. Finalmente, se recopilan las conclusiones obtenidas y sugerencias de trabajos futuros en la secciA³n 4.