Title
PCA-based branch and bound search algorithms for computing K nearest neighbors PCA-based branch and bound search algorithms for computing K nearest neighbors
Author
Faculty/Department
Faculty of Sciences. Physics
Publication type
article
Publication
Amsterdam ,
Subject
Computer. Automation
Source (journal)
Pattern recognition letters. - Amsterdam
Volume/pages
24(2003) :9-10 , p. 1437-1451
ISSN
0167-8655
ISI
000181368900030
Carrier
E
Target language
English (eng)
Affiliation
University of Antwerp
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.
E-info
https://repository.uantwerpen.be/docman/iruaauth/d476c1/af95884.pdf
http://gateway.webofknowledge.com/gateway/Gateway.cgi?GWVersion=2&SrcApp=PARTNER_APP&SrcAuth=LinksAMR&KeyUT=WOS:000181368900030&DestLinkType=RelatedRecords&DestApp=ALL_WOS&UsrCustomerID=ef845e08c439e550330acc77c7d2d848
http://gateway.webofknowledge.com/gateway/Gateway.cgi?GWVersion=2&SrcApp=PARTNER_APP&SrcAuth=LinksAMR&KeyUT=WOS:000181368900030&DestLinkType=FullRecord&DestApp=ALL_WOS&UsrCustomerID=ef845e08c439e550330acc77c7d2d848
http://gateway.webofknowledge.com/gateway/Gateway.cgi?GWVersion=2&SrcApp=PARTNER_APP&SrcAuth=LinksAMR&KeyUT=WOS:000181368900030&DestLinkType=CitingArticles&DestApp=ALL_WOS&UsrCustomerID=ef845e08c439e550330acc77c7d2d848
Handle