@techreport{oai:ipsj.ixsq.nii.ac.jp:00048253,
 author = {北, 研二 and 獅々堀正幹 and 大恵俊一郎 and Kenji, Kita and Masami, Shishibori and Shun-Ichiro, Oe},
 issue = {98(2003-NL-157)},
 month = {Sep},
 note = {高次元空間における最近傍検索(nearest neighbor search)は、マルチメディア・コンテンツ検索、データ・マイニング、パターン認識等の分野における重要な研究課題の１つである。高次元空間では、ある点の最近点と最遠点との間に距離的な差が生じなくなるという現象が起こるため、効率的な多次元検索手法を設計することが極度に困難となる。本稿では、線形探索アルゴリズムにおける距離計算中の不要な演算を削減することにより、きわめて高速な最近傍検索アルゴリズムを提案する。さらに、不必要な演算を早期検出するために、要素の分散値を用いた次元ソート法、並びに主成分分析に基づくデータ変換法を提案する。実験によると、従来の SR-tree や VP-tree 等よりも 20倍?50倍高速であり、高次元の場合にも性能の劣化はほとんどない。, 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. 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.},
 title = {多次元データの高速近傍検索アルゴリズム},
 year = {2003}
}