Presentation | 2006-03-16 An Accelerated High Dimensional Nearest Neighbor Search based on An Efficient Distance Computational Strategy Koji Takemoto, Takekazu Kato, Toshikazu Wada, |
---|---|
PDF Download Page | PDF download Page Link |
Abstract(in Japanese) | (See Japanese page) |
Abstract(in English) | In this paper, we propose an accelerated Nearest Neighbor (NN) search algorithm in high dimensional space. The methods proposed so far can be classified into two types: 1) NN candidate narrowing and 2) pruning of distance computation. In high dimensional space over 30D, while NN candidate narrowing becomes brute force search, the latter method, pruning of distance computation is still effective for acceleration. For realizing more efficient NN search in high dimensional space, we integrate these two methods. As well, orthogonal expansion of patterns ordered by contribution ratio is incorporated for efficient pruning, because the distance computation starting from the most contributed component provides good approximation of the true distance. We confirmed through extensive experiments that our method is faster than existing methods. |
Keyword(in Japanese) | (See Japanese page) |
Keyword(in English) | |
Paper # | PRMU2005-240 |
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) | An Accelerated High Dimensional Nearest Neighbor Search based on An Efficient Distance Computational Strategy |
Sub Title (in English) | |
Keyword(1) | |
1st Author's Name | Koji Takemoto |
1st Author's Affiliation | Graduate School of System Engineering, Wakayama University() |
2nd Author's Name | Takekazu Kato |
2nd Author's Affiliation | Graduate School of System Engineering, Wakayama University |
3rd Author's Name | Toshikazu Wada |
3rd Author's Affiliation | Graduate School of System Engineering, Wakayama University |
Date | 2006-03-16 |
Paper # | PRMU2005-240 |
Volume (vol) | vol.105 |
Number (no) | 673 |
Page | pp.pp.- |
#Pages | 8 |
Date of Issue |