Fast multidimensional nearest neighbor search algorithm using priority queue
Fast multidimensional nearest neighbor search algorithm using priority queue
复制标题
DOI：
10.1002/eej.20502
复制
发表时间：
2008-08
影响因子：
0.4
通讯作者：
Shiro Ajioka;S. Tsuge;M. Shishibori;K. Kita
中科院分区：
文献类型：
--
作者：
Shiro Ajioka;S. Tsuge;M. Shishibori;K. Kita
高维空间的最近邻搜索是一个有趣而重要的问题，它涉及到多媒体信息检索、数据挖掘和模式识别等广泛的应用。对于此类应用，高维的诅咒往往成为开发高效搜索方法的主要障碍。本文研究了利用优先队列设计高维最近邻搜索算法的问题。该算法基于一种简单的线性搜索算法，消除了多维向量间距离计算中不必要的算术运算。此外，我们提出了两种技术，即维度排序方法和基于PCA的方法来加速多维搜索。实验结果表明，即使在非常大的维度上，我们的方案也能很好地扩展。©2008 Wiley期刊公司电气工程学报，164(3):69-77,2008；在线发表于Wiley InterScience （www.interscience.wiley.com）。DOI 10.1002 / eej.20502
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