Ficha del artículo

Tipo - Type: Research article

Título - Title

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

Evaluating metric structures with General Purpose Graphic Processing Units

Autoría - Creator

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.

Palabras Clave

Búsquedas por similitud, espacios métricos, estructuras métricas ⓘ

Keyword

Similarity search, metric spaces, metric structures parallel processing ⓘ - ⓘ - ⓘ

Bibliografía - acceso a la indexación de cada trabajo en Scholar Google

[CUDA] NVIDIA CUDA C Programming Guide, V. 4.0.

[CPM94] R. BAEZA-YATES, W. CUNTO, U. MANBER, and S. Wu. Proximity matching using fixed queries trees. In 5th Combinatorial Pattern Matching (CPM’94), 1994, LNCS 807, pp. 198–212.

[DEXA12] Roberto Uribe-Paredes, Enrique Arias, José L. Sánchez, and Diego Cazorla. Improving the Performance for the Range Search on Metric Spaces using a Multi-GPU Platform. To appear: 23rd International Conference on Database and Expert Systems Applications (DEXA 2012). Vienna, Austria, Sept. 2012.

[EIPA12] Osiris SOFIA, Jacobo SALVADOR, Eder DOS SANTOS, Roberto URIBE PAREDES. Búsquedas por Similitud en Espacios Métricos sobre Plataformas Basadas en GPUs. II Encuentro de Investigadores de la Patagonia Austral, Universidad Nacional de la Patagonia Austral, Unidad Académica San Julián, Puerto San Julián, Argentina. 7 de septiembre de 2012. Proceeding Publicados en CD por Universidad Nacional de la Patagonia Austral.ISBN13: 978-987-1242-66-5.

[FM07] Wu-Feng and Dinesh Manocha. High-performance computing using accelerators. Parallel Computing, 33:645--647, 2007.

[GBMB10] Veronica Gil-Costa, Ricardo Barrientos, Mauricio Marín, and Carolina Bonacic. Scheduling metric-space queries processing on multi-core processors. Euromicro Conference on Parallel, Distributed, and Network-Based Processing, 0:187--194, 2010.

[GDB08] Vincent Garcia, Eric Debreuve, and Michel Barlaud. Fast k nearest neighbor search using GPU. Computer Vision and Pattern Recognition Workshop, 0:1--6, 2008.

[GKKG03] GRAMA, Ananth and KARYPIS, George and KUMAR, Vipin and GUPTA, Anshul. Introduction to Parallel Computing (2nd Edition). Addison Wesley. 2003.

[HPCS11] Roberto URIBE-PAREDES, Pedro VALERO-LARA, Enrique ARIAS, José L. SÁNCHEZ and Diego CAZORLA. Similarity search implementations for multi-core and many-core processors. In: 2011 International Conference on High Performance Computing and Simulation (HPCS), pp. 656–663 (July 2011). Istanbul, Turkey.

[ICCSDE12] Roberto Uribe-Paredes, Diego Cazorla, José L. Sánchez, and Enrique Arias. A comparative study of different metric structures: Thinking on gpu implementations. In International Conference of Computational Statistics and Data Engineering (ICCSDE’12), London, England, July 2012.

[ISCSCT09] Quansheng Kuang and Lei Zhao. A practical GPU based kNN algorithm. International Symposium on Computer Science and Computational Technology (ISCSCT), pp. 151–155, 2009.

[ISPA12] R.J. Barrientos, J.I. Gómez, C. Tenllado, M. Prieto, and M. Marin. Range query processing in a multi-GPU enviroment. In 10th IEEE International Symposium on Parallel and Distributed Processing with Applications (ISPA 2012), Madrid, Spain, July 2012.

[JISBD12] E. ARIAS, D. CAZORLA, J. L. SÁNCHEZ, R. URIBE-PAREDES. Una estructura Métrica Genérica para Búsquedas por Rango sobre una Plataforma Multi-GPU. XVII Jornadas de Ingeniería del Software y Bases de Datos (JISBD2012). Sept. 2012, Almería, España.

[JP12] Roberto Uribe-Paredes, Diego Cazorla, Enrique Arias and José L. Sánchez. Acelerando la Búsqueda por Rango con un Sistema Híbrido de Memoria Compartida. To appear: Actas XXIII Jornadas de Paralelismo (JP2012). Sept. 2012, Elche, España.

[MOV94] María Luisa MICÓ, José ONCINA, and Enrique VIDAL. A new version of the nearest-neighbour approximating and eliminating search algorithm (AESA) with linear preprocessing time and memory requirements. Pattern Recognition Letters, 15(1):9--17, January 1994.

[MPI94] W. Gropp, E. Lusk, and A. Skelljum. Using MPI: Portable Parallel Programming with the Message Passing Interface. Scientific and Engineering computation Series. MIT Press, Cambridge, MA, 1994.

[NN97] S. Nene and S. Nayar. A simple algorithm for nearest neighbor search in high dimensions. IEEE Transactions on Pattern Analysis and Machine Intelligence, 19(9):989--1003, 1997.

[OMP07] Barbara Chapman, Gabriele Jost, and Ruud van der Pas. Using OpenMP: Portable Shared Memory Parallel Programming. The MIT Press, 2007.

[SOFSEM07] Oscar Pedreira and Nieves R. Brisaboa. Spatial selection of sparse pivots for similarity search in metric spaces. In 33rd Conference on Current Trends in Theory and Practice of Computer Science (SOFSEM 2007), Harrachov, Czech Republic, 2007, vol. 4362 of LNCS, pp. 434–445, Springer.

[SPIRE99] Edgar CHÁVEZ, José L. MARROQUÍN, and Ricardo BAEZA-YATES. Spaghettis: An array based algorithm for similarity queries in metric spaces. In 6th International Symposium on String Processing and Information Retrieval (SPIRE 99), pages 38--46. IEEE CS Press, 1999.

[TTSF00] Caetano Traina, Agma Traina, Bernhard Seeger, and Christos Faloutsos. Slim-trees: High performance metric trees minimizing overlap between nodes. In VII International Conference on Extending Database Technology, pages 51--61, 2000.

[VLDB95] Sergei Brin. Near neighbor search in large metric spaces. In the 21st VLDB Conference, pages 574—584. Morgan Kaufmann Publishers, 1995.

[VLDB97] Paolo Ciaccia, Marco Patella, and Pavel Zezula. M-Tree : An efficient access method for similarity search in metric spaces. In the 23st International Conference on VLDB, pages 426--435, 1997.

[VLDBJ02] Gonzalo Navarro. Searching in metric spaces by spatial approximation. The Very Large Databases Journal (VLDBJ), 11(1):28--46, 2002.

[WICC13] Osiris SOFIA, Jacobo SALVADOR, Eder DOS SANTOS, Roberto URIBE PAREDES. Búsquedas por Rango sobre Plataformas GPU en Espacios Métricos. pp 658 - 662. XV Workshop de Investigadores en Ciencias de la Computación - WICC 2013. 18 al 18 de Abril de 2013. Universidad Autónoma de Entre Ríos, Paraná, Argentina. Proceeding Publicados en CD por Universidad Autónoma de Entre Ríos y RedUNCI. ISBN13: 978-987-28179-6-1.