A tabular pruning rule in tree-based fast nearest neighbor search algorithms
Por favor, use este identificador para citar o enlazar este ítem:
http://hdl.handle.net/10045/8771
Título: | A tabular pruning rule in tree-based fast nearest neighbor search algorithms |
---|---|
Autor/es: | Oncina, Jose | Thollard, Franck | Gómez Ballester, Eva | Micó, Luisa | Moreno Seco, Francisco |
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 | Laboratoire Hubert Curien |
Palabras clave: | Pruning Rules | Metric spaces | Branch and Bound scheme | Nearest neighbour search |
Área/s de conocimiento: | Lenguajes y Sistemas Informáticos | Ciencia de la Computación e Inteligencia Artificial |
Fecha de publicación: | 2007 |
Editor: | Springer Berlin / Heidelberg |
Cita 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 |
Resumen: | 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. |
Patrocinador/es: | 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 |
Tipo: | info:eu-repo/semantics/article |
Derechos: | The original publication is available at www.springerlink.com |
Revisión científica: | si |
Versión del editor: | http://dx.doi.org/10.1007/978-3-540-72849-8_39 |
Aparece en las colecciones: | INV - GRFIA - Artículos de Revistas |
Archivos en este ítem:
Archivo | Descripción | Tamaño | Formato | |
---|---|---|---|---|
ibpria07.pdf | Versión revisada (acceso libre) | 187,42 kB | Adobe PDF | Abrir Vista previa |
Todos los documentos en RUA están protegidos por derechos de autor. Algunos derechos reservados.