\documentclass[12pt]{article}
\usepackage[utf8]{inputenc}
\usepackage[spanish]{babel}
\usepackage{hyperref}
\usepackage{geometry}
\geometry{margin=2.5cm}
\title{Evaluación de estructuras métricas con Unidades de Procesamiento Gráfico de Propósito General}
\author{\small Sofia, Albert Osiris , Dos Santos, Eder , Uribe Paredes , Roberto , Salvador, Jacobo }


\date{2015-10-15}

\begin{document}
\maketitle

\section*{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.

\section*{Referencias}
\begin{itemize}
  \item [CUDA] NVIDIA CUDA C Programming Guide, V. 4.0.

  \item [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.

  \item [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.

  \item [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.

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

  \item [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.

  \item [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.

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

  \item [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.

  \item [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.

  \item [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.

  \item [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.

  \item [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.

  \item [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.

  \item [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.

  \item [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.

  \item [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.

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

  \item [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.

  \item [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.

  \item [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.

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

  \item [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.

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

  \item [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.

\end{itemize}

\section*{Editorial}
Access the full text of article: \href{https://www.cyta.com.ar/ta/article.php?id=140403}{https://www.cyta.com.ar/ta/article.php?id=140403}\\
Publicado por la \textbf{Editorial Ciencia y T\'ecnica Administrativa - CyTA}.\\
Sitio web: \href{https://www.cyta.ar}{www.cyta.ar}\\
Email: \texttt{cyta@cyta.ar}


\end{document}