A fast pivot-based indexing algorithm for metric spaces
Please use this identifier to cite or link to this item:
http://hdl.handle.net/10045/18324
Title: | A fast pivot-based indexing algorithm for metric spaces |
---|---|
Authors: | Socorro Llanes, Raisa | Micó, Luisa | Oncina, Jose |
Research Group/s: | Reconocimiento de Formas e Inteligencia Artificial |
Center, Department or Service: | Universidad de Alicante. Departamento de Lenguajes y Sistemas Informáticos | Instituto Superior Politécnico Jose Antonio Echevarría (La Habana) |
Keywords: | Fast nearest neighbor | Similarity search | Metric space |
Knowledge Area: | Lenguajes y Sistemas Informáticos |
Issue Date: | 28-Apr-2011 |
Publisher: | Elsevier |
Citation: | 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 |
Abstract: | 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. |
Sponsor: | 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 |
Language: | eng |
Type: | info:eu-repo/semantics/article |
Peer Review: | si |
Publisher version: | http://dx.doi.org/10.1016/j.patrec.2011.04.016 |
Appears in Collections: | INV - GRFIA - Artículos de Revistas Research funded by the EU |
Files in This Item:
File | Description | Size | Format | |
---|---|---|---|---|
Fast_pivot-based_indexing_algorithm_final.pdf | Versión final (acceso restringido) | 758,47 kB | Adobe PDF | Open Request a copy |
piaesa-prl.pdf | Versión revisada (acceso abierto) | 212,89 kB | Adobe PDF | Open Preview |
Items in RUA are protected by copyright, with all rights reserved, unless otherwise indicated.