Efficient search supporting several similarity queries by reordering pivots
Please use this identifier to cite or link to this item:
http://hdl.handle.net/10045/16956
Title: | Efficient search supporting several similarity queries by reordering pivots |
---|---|
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: | K-nearest neighbour | Approximation | Elimination | Metric spaces | Pivot | Range search |
Knowledge Area: | Lenguajes y Sistemas Informáticos |
Issue Date: | Feb-2011 |
Publisher: | Acta Press |
Citation: | SOCORRO, Raisa; MICÓ ANDRÉS, Luisa; ONCINA CARRATALÁ, Jose. "Efficient search supporting several similarity queries by reordering pivots". En: Proceedings of the Eighth IASTED International Conference on Signal Processing, Pattern Recognition, and Applications (SPPRA 2011). Anaheim, Calif. : Acta Press, 2011. ISBN 978-0-88986-865-6, pp. 114-120 |
Abstract: | Effective similarity search indexing in general metric spaces has traditionally received special attention in several areas of interest like pattern recognition, computer vision or information retrieval. A typical method is based on the use of a distance as a dissimilarity function (not restricting to Euclidean distance) where the main objective is to speed up the search of the most similar object in a database by minimising the number of distance computations. Several types of search can be defined, being the k-nearest neigh-bour or the range search the most common. AESA is one of the most well known of such algorithms due to its performance (measured in distance computations). PiAESA is an AESA variant where the main objective has changed. Instead of trying to find the best nearest neighbour candidate at each step, it tries to find the object that contributes the most to have a bigger lower bound function, that is, a better estimation of the distance. In this paper we extend and test PiAESA to support several similarity queries. Our empirical results show that this approach obtains a significant improvement in performance when comparing with competing algorithms. |
Sponsor: | The authors thank the Spanish CICyT for partial support of this work 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/16956 |
ISBN: | 978-0-88986-865-6 |
Language: | eng |
Type: | info:eu-repo/semantics/conferenceObject |
Peer Review: | si |
Appears in Collections: | INV - GRFIA - Comunicaciones a Congresos, Conferencias, etc. Research funded by the EU |
Files in This Item:
File | Description | Size | Format | |
---|---|---|---|---|
efficient_search.pdf | Versión revisada (acceso libre) | 109,08 kB | Adobe PDF | Open Preview |
Items in RUA are protected by copyright, with all rights reserved, unless otherwise indicated.