Paper Info
Title
PCA-based branch and bound search algorithms for computing K nearest neighbors
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.
Year
DOI
Venue
2003
10.1016/S0167-8655(02)00384-7
Pattern Recognition Letters
Keywords
Field
DocType
branch and bound search algorithm,principal component analysis,decomposition method,search algorithm,k nearest neighbors,different search algorithm,optimal level,total computation time,bound search algorithm,traversal order,efficient decomposition method,non-parametric estimation,node traversal cost,distance computation cost,pca-based branch,k nearest neighbor,probabilistic model,branch and bound
k-nearest neighbors algorithm,Branch and bound,Mathematical optimization,Search algorithm,Tree traversal,Pattern recognition,Decomposition method (constraint satisfaction),Artificial intelligence,Principal component analysis,Nearest neighbor search,Mathematics,Computation
Journal
Volume
Issue
ISSN
24
9-10
Pattern Recognition Letters
Citations 
PageRank 
References 
7
0.58
13
Authors
3
Name
Order
Citations
PageRank
Win D'haes170.58
Dirk Van Dyck238136.58
Xavier Rodet3627107.87