多次元データの高速近傍検索アルゴリズム(基盤・要素技術)(セマンティックウェブと自然言語処理その他一般)

スポンサーリンク

概要

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

著者

関連論文

もっと見る

スポンサーリンク