Fast Multidimensional Nearest Neighbor Search Algorithm Using Priority Queue

• Ajioka Shiro

  Faculty of Engineering, The University of Tokushima

• Tsuge Satoru

  Faculty of Engineering, The University of Tokushima

• Shishibori Masami

  Faculty of Engineering, The University of Tokushima

• Kita Kenji

  Center for Advanced Information Technology, The University of Tokushima

Bibliographic Information

Other Title

• 順位キューを用いた多次元データの高速近傍検索アルゴリズム
• ジュンイ キュー オ モチイタ タジゲン データ ノ コウソク キンボウ ケンサク アルゴリズム

Abstract

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.

Journal

• IEEJ Transactions on Electronics, Information and Systems

  IEEJ Transactions on Electronics, Information and Systems 126 (3), 353-360, 2006

  The Institute of Electrical Engineers of Japan

Keywords

• Nearest neighbor search
• High dimensional space
• Fast linear search
• Priority queue
• Multimedia information retrieval

Details

• CRID: 1390001204606139392
• NII Article ID: 10017276789
• NII Book ID: AN10065950
• DOI: 10.1541/ieejeiss.126.353
• ISSN: 13488155
• ISSN: 03854221
• NDL BIB ID: 7856885
• Web Site: https://ndlsearch.ndl.go.jp/books/R000000004-I7856885
• Web Site: http://www.jstage.jst.go.jp/article/ieejeiss/126/3/126_3_353/_pdf
• Text Lang: ja
• Data Source:
  • JaLC
  • NDL
  • Crossref
  • CiNii Articles
  • KAKEN
• Abstract License Flag: Disallowed