Presentation 2006-03-16
Nearest Neighbor Search in High-Dimensional Space based on Space Decomposition and Orthogonal Basis Selection
Hidetaka Arai, Takekazu Kato, Toshikazu Wada,
PDF Download Page PDF download Page Link
Abstract(in Japanese) (See Japanese page)
Abstract(in English) Nearest Neighbor (NN) search is essential for case/instance based reasoning. Most NN search methods proposed so far are based on NN candidate narrowing and these methods degenerates to brute force search in high-dimensional space over 30D. Efficient NN search algorithm dealing with image database in over thousand dimensional space has not been proposed. In this paper, we propose an effective NN search algorithm integrating orthogonal expansion by PCA and space decomposition, which works in very high dimensional space. This method can be regarded as a natural extension of ANN. Through extensive experiments, we confirmed the efficiency of our method.
Keyword(in Japanese) (See Japanese page)
Keyword(in English) Nearest Neighbor Search in high-dimensional space / space decomposition / ANN / PCA
Paper # PRMU2005-239
Date of Issue

Conference Information
Committee PRMU
Conference Date 2006/3/9(1days)
Place (in Japanese) (See Japanese page)
Place (in English)
Topics (in Japanese) (See Japanese page)
Topics (in English)
Chair
Vice Chair
Secretary
Assistant

Paper Information
Registration To Pattern Recognition and Media Understanding (PRMU)
Language JPN
Title (in Japanese) (See Japanese page)
Sub Title (in Japanese) (See Japanese page)
Title (in English) Nearest Neighbor Search in High-Dimensional Space based on Space Decomposition and Orthogonal Basis Selection
Sub Title (in English)
Keyword(1) Nearest Neighbor Search in high-dimensional space
Keyword(2) space decomposition
Keyword(3) ANN
Keyword(4) PCA
1st Author's Name Hidetaka Arai
1st Author's Affiliation Graduate School of Systems Engineering, Wakayama University()
2nd Author's Name Takekazu Kato
2nd Author's Affiliation Graduate School of Systems Engineering, Wakayama University
3rd Author's Name Toshikazu Wada
3rd Author's Affiliation Graduate School of Systems Engineering, Wakayama University
Date 2006-03-16
Paper # PRMU2005-239
Volume (vol) vol.105
Number (no) 673
Page pp.pp.-
#Pages 8
Date of Issue