Premium
Fast multidimensional nearest neighbor search algorithm using priority queue
Author(s) -
Ajioka Shiro,
Tsuge Satoru,
Shishibori Masami,
Kita Kenji
Publication year - 2008
Publication title -
electrical engineering in japan
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.136
H-Index - 28
eISSN - 1520-6416
pISSN - 0424-7760
DOI - 10.1002/eej.20502
Subject(s) - priority queue , curse of dimensionality , computer science , queue , sorting , k nearest neighbors algorithm , search algorithm , best bin first , algorithm , nearest neighbor search , computation , scheme (mathematics) , simple (philosophy) , data mining , artificial intelligence , mathematics , mathematical analysis , programming language , philosophy , epistemology
Nearest neighbor search in high‐dimensional spaces is an interesting and important problem which is relevant for a wide variety of applications, including multimedia information retrieval, data mining, and pattern recognition. For such applications, the curse of high dimensionality tends to be a major obstacle in the development of efficient search methods. This paper addresses the problem of designing an efficient algorithm for high‐dimensional nearest neighbor search using a priority queue. The proposed algorithm is based on a simple linear search algorithm and eliminates unnecessary arithmetic operations from distance computations between multidimensional vectors. Moreover, we propose two techniques, a dimensional sorting method and a PCA‐based method, to accelerate multidimensional search. Experimental results indicate that our scheme scales well even for a very large number of dimensions. © 2008 Wiley Periodicals, Inc. Electr Eng Jpn, 164(3): 69–77, 2008; Published online in Wiley InterScience ( www.interscience.wiley.com ). DOI 10.1002/eej.20502