著者

北 研二 獅々堀正幹 大恵俊一郎

雑誌

情報処理学会研究報告自然言語処理(NL)

巻号頁・発行日

vol.2003, no.98(2003-NL-157), pp.9-16, 2003-09-29

---

高次元空間における最近傍検索(nearest neighbor search)は、マルチメディア・コンテンツ検索、データ・マイニング、パターン認識等の分野における重要な研究課題の1つである。高次元空間では、ある点の最近点と最遠点との間に距離的な差が生じなくなるという現象が起こるため、効率的な多次元検索手法を設計することが極度に困難となる。本稿では、線形探索アルゴリズムにおける距離計算中の不要な演算を削減することにより、きわめて高速な最近傍検索アルゴリズムを提案する。さらに、不必要な演算を早期検出するために、要素の分散値を用いた次元ソート法、並びに主成分分析に基づくデータ変換法を提案する。実験によると、従来の SR-tree や VP-tree 等よりも 20倍?50倍高速であり、高次元の場合にも性能の劣化はほとんどない。