Búsquedas por rango sobre plataformas GPU en espacios métricos

Abstract

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 reconocimiento de patrones, recuperación de la información, 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 un objeto es representado como una caja negra, donde la única información disponible es la función de distancia de este objeto a los otros. En general, el cálculo de la distancia es costoso, por ello el objetivo es reducir la cantidad de evaluaciones de distancia necesarias para resolver la consulta. Para esto se han desarrollado numerosas estructuras métricas, que realizan un preprocesamiento de los datos a fin de disminuir las evaluaciones de distancia al momento de la búsqueda. En la actualidad, 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 sistemas de altas prestaciones en entornos de procesamiento paralelo. Existen una serie de tecnologías para realizar implementaciones paralelas, siendo una de las más nuevas, las plataformas basadas en GPU / Multi- GPU, que son interesantes debido a la cantidad de procesadores y los bajos costes involucrados.