A Tabular Pruning Rule in Tree-Based Fast Nearest Neighbor Search Algorithms

Jose Oncina 1 Franck Thollard 2 Eva Gómez-Ballester 1 Luisa Micó 1 Francisco Moreno-Seco 1
1 DLSI - Departamento de Lenguajes y Sistemas Informáticos
2 LHC - Laboratoire Hubert Curien [Saint Etienne]
Abstract : A common activity in many pattern recognition tasks, image processing or clustering techniques involves searching a labelled data set looking for the nearest point to a given unlabelled sample. To reduce the computational overhead when the naive exhaustive search is applied, some fast nearest neighbor search (NNS) algorithms have appeared in the last years. 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 and analyze a new pruning rule that only uses the information stored in a table at preprocessing time. This rule can be used alone or in combination with other known rules. An exhaustive experimentation evaluating their behavior through real and artificial data has been performed.
Keywords : Nearest neighbor search Pruning
Document type :
Conference papers
Complete list of metadatas
https://hal-ujm.archives-ouvertes.fr/ujm-00165425
Contributor : Franck Thollard <>
Submitted on : Monday, March 9, 2009 - 3:43:00 PM
Last modification on : Wednesday, July 25, 2018 - 2:05:31 PM
Long-term archiving on : Thursday, April 8, 2010 - 6:51:50 PM

File

ibpria07.pdf
Files produced by the author(s)

Identifiers

Collections

LAHC | CNRS | UNIV-ST-ETIENNE | IOGS | PARISTECH

Citation

Jose Oncina, Franck Thollard, Eva Gómez-Ballester, Luisa Micó, Francisco Moreno-Seco. A Tabular Pruning Rule in Tree-Based Fast Nearest Neighbor Search Algorithms. Third Iberian Conference, IbPRIA 2007, Girona, Spain, June 6-8, 2007, Proceedings, Jun 2007, Girona, Spain. pp.306-313, ⟨10.1007/978-3-540-72849-8_39⟩. ⟨ujm-00165425⟩

Export

BibTeX TEI DC DCterms EndNote

Share

Metrics

Record views

153

Files downloads

232

Contact

CCSD