Publication
Title
PCA-based branch and bound search algorithms for computing K nearest neighbors
Author
Abstract
In this paper, the efficiency of branch and bound search algorithms for the computation of K nearest neighbors is studied. The most important aspects that influence the efficiency of the search algorithm are: (1) the decomposition method, (2) the elimination rule, (3) the traversal order and (4) the level of decomposition. First, a theoretical derivation of an efficient decomposition method based on principal component analysis is given. Then, different elimination rules and traversal orders are combined resulting in ten different search algorithms. Since the efficiency is strongly dependent on the level of decomposition, this user specified parameter is optimized first. This optimization is realized by a probabilistic model that expresses the total computation time in function of the node traversal cost and the distance computation cost. All comparisons are based on the total computation time for the optimal level of decomposition. (C) 2002 Elsevier Science B.V. All rights reserved.
Language
English
Source (journal)
Pattern recognition letters. - Amsterdam
Publication
Amsterdam : 2003
ISSN
0167-8655
Volume/pages
24:9-10(2003), p. 1437-1451
ISI
000181368900030
Full text (publisher's version - intranet only)
UAntwerpen
Faculty/Department
Research group
Publication type
Subject
Affiliation
Publications with a UAntwerp address
External links
Web of Science
Record
Identification
Creation 03.01.2013
Last edited 20.11.2017
To cite this reference