A tabular pruning rule in tree-based fast nearest neighbor search algorithms
Empreu sempre aquest identificador per citar o enllaçar aquest ítem
http://hdl.handle.net/10045/8771
Títol: | A tabular pruning rule in tree-based fast nearest neighbor search algorithms |
---|---|
Autors: | Oncina, Jose | Thollard, Franck | Gómez Ballester, Eva | Micó, Luisa | Moreno Seco, Francisco |
Grups d'investigació o GITE: | Reconocimiento de Formas e Inteligencia Artificial |
Centre, Departament o Servei: | Universidad de Alicante. Departamento de Lenguajes y Sistemas Informáticos | Laboratoire Hubert Curien |
Paraules clau: | Pruning Rules | Metric spaces | Branch and Bound scheme | Nearest neighbour search |
Àrees de coneixement: | Lenguajes y Sistemas Informáticos | Ciencia de la Computación e Inteligencia Artificial |
Data de publicació: | 2007 |
Editor: | Springer Berlin / Heidelberg |
Citació bibliogràfica: | ONCINA CARRATALÁ, Jose, et al. "A tabular pruning rule in tree-based fast nearest neighbor search algorithms". En: Pattern Recognition and Image Analysis : Third Iberian Conference, IbPRIA 2007, Girona, Spain, June 6-8, 2007, Proceedings, Part II. Berlin : Springer, 2007. (Lecture Notes in Computer Science; 4478/2007). ISBN 978-3-540-72848-1, pp. 306-313 |
Resum: | Some fast nearest neighbor search (NNS) algorithms using metric properties have appeared in the last years for reducing computational cost. Depending on the structure used to store the training set, different strategies to speed up the search have been defined. For instance, pruning rules avoid the search of some branches of a tree in a tree-based search algorithm. In this paper, we propose a new and simple pruning rule that can be used in most of the tree-based search algorithms. All the information needed by the rule can be stored in a table (at preprocessing time). Moreover, the rule can be computed in constant time. This approach is evaluated through real and artificial data experiments. In order to test its performance, the rule is compared to and combined with other previously defined rules. |
Patrocinadors: | Spanish CICIyT for partial support of this work through projects DPI2006-15542-C04-1, TIN2006-14932-C02, GV06/166, the IST Programme of the European Community, under the PASCAL Network of Excellence, IST 2002-506778. |
URI: | http://hdl.handle.net/10045/8771 |
ISBN: | 978-3-540-72848-1 |
ISSN: | 0302-9743 (Print) | 1611-3349 (Online) |
DOI: | 10.1007/978-3-540-72849-8_39 |
Idioma: | eng |
Tipus: | info:eu-repo/semantics/article |
Drets: | The original publication is available at www.springerlink.com |
Revisió científica: | si |
Versió de l'editor: | http://dx.doi.org/10.1007/978-3-540-72849-8_39 |
Apareix a la col·lecció: | INV - GRFIA - Artículos de Revistas |
Arxius per aquest ítem:
Arxiu | Descripció | Tamany | Format | |
---|---|---|---|---|
ibpria07.pdf | Versión revisada (acceso libre) | 187,42 kB | Adobe PDF | Obrir Vista prèvia |
Tots els documents dipositats a RUA estan protegits per drets d'autors. Alguns drets reservats.