A fast pivot-based indexing algorithm for metric spaces
Por favor, use este identificador para citar o enlazar este ítem:
http://hdl.handle.net/10045/18324
Título: | A fast pivot-based indexing algorithm for metric spaces |
---|---|
Autor/es: | Socorro Llanes, Raisa | Micó, Luisa | Oncina, Jose |
Grupo/s de investigación o GITE: | Reconocimiento de Formas e Inteligencia Artificial |
Centro, Departamento o Servicio: | Universidad de Alicante. Departamento de Lenguajes y Sistemas Informáticos | Instituto Superior Politécnico Jose Antonio Echevarría (La Habana) |
Palabras clave: | Fast nearest neighbor | Similarity search | Metric space |
Área/s de conocimiento: | Lenguajes y Sistemas Informáticos |
Fecha de publicación: | 28-abr-2011 |
Editor: | Elsevier |
Cita bibliográfica: | SOCORRO, Raisa; MICÓ, Luisa; ONCINA, Jose. "A fast pivot-based indexing algorithm for metric spaces". Pattern Recognition Letters. Vol. 32, Issue 11 (1 Aug. 2011). ISSN 0167-8655, pp. 1511-1516 |
Resumen: | This work focus on fast nearest neighbor (NN) search algorithms that can work in any metric space (not just the Euclidean distance) and where the distance computation is very time consuming. One of the most well known methods in this field is the AESA algorithm, used as baseline for performance measurement for over twenty years. The AESA works in two steps that repeats: first it searches a promising candidate to NN and computes its distance (approximation step), next it eliminates all the unsuitable NN candidates in view of the new information acquired in the previous calculation (elimination step). This work introduces the PiAESA algorithm. This algorithm improves the performance of the AESA algorithm by splitting the approximation criterion: on the first iterations, when there is not enough information to find good NN candidates, it uses a list of pivots (objects in the database) to obtain a cheap approximation of the distance function. Once a good approximation is obtained it switches to the AESA usual behavior. As the pivot list is built in preprocessing time, the run time of PiAESA is almost the same than the AESA one. In this work, we report experiments comparing with some competing methods. Our empirical results show that this new approach obtains a significant reduction of distance computations with no execution time penalty. |
Patrocinador/es: | Spanish CICyT partial support through projects TIN2009-14205-C04-01, the IST Programme of the European Community, under the PASCAL Network of Excellence, IST-2002-506778, and the program CONSOLIDER INGENIO 2010 (CSD2007–00018). |
URI: | http://hdl.handle.net/10045/18324 |
ISSN: | 0167-8655 (Print) | 1872-7344 (Online) |
DOI: | 10.1016/j.patrec.2011.04.016 |
Idioma: | eng |
Tipo: | info:eu-repo/semantics/article |
Revisión científica: | si |
Versión del editor: | http://dx.doi.org/10.1016/j.patrec.2011.04.016 |
Aparece en las colecciones: | INV - GRFIA - Artículos de Revistas Investigaciones financiadas por la UE |
Archivos en este ítem:
Archivo | Descripción | Tamaño | Formato | |
---|---|---|---|---|
Fast_pivot-based_indexing_algorithm_final.pdf | Versión final (acceso restringido) | 758,47 kB | Adobe PDF | Abrir Solicitar una copia |
piaesa-prl.pdf | Versión revisada (acceso abierto) | 212,89 kB | Adobe PDF | Abrir Vista previa |
Todos los documentos en RUA están protegidos por derechos de autor. Algunos derechos reservados.