距離計算を行わない最近傍探索アルゴリズム : Grafting Trees(テーマセッション,大規模データベースとパターン認識)

書誌事項

タイトル別名
  • Grafting Trees A Nearest Neighbor Search Algorithm without Distance Computation

この論文をさがす

説明

本報告では、K-D木を用いた最近傍探索アルゴリズムにおけるPriority Searchを識別問題としてとらえ、距離計算を行わない最近傍探索アルゴリズムを提案する。K-D木を用いた最近傍探索では、1)木探索によって暫定最近傍解を求め、2)A*アルゴリズムによる真の最近傍の探索が行われる。このうち、2)のA*アルゴリズムによる最近傍の探索に処理時間の大半が費やされてしまう。この傾向は、格納されているデータ分布の次元数が上昇するにつれて顕著になる。本報告では、木探索でたどり着いた葉ノードに対応する空間のBOX分割を考え、そのBOX内のどこにクエリが存在するかにより、Pnority Searchで見つかる最近傍は決まっていることに着目し、BOX毎に識別器を用意して、距離計算なしで最近傍探索を行う方法を提案する。具体的には、K-D木の葉の部分に決定木を継ぎ足したGrafting Treesというデータ構造を用いた最近傍探索アルゴリズムを提案する。Grafting Treesでは、データ分布の次元数が上昇するにつれて決定木の構造が深くなってしまうという問題が起きるため、登録したデータを母点とするVoronoi境界付近では、木探索の代わりに距離計算を行うHybrid Grafting Treesについても提案する。実験では、D. MountらのANNライブラリとGrafting Treesの速度比較を行い、ANNよりも高速であることを示す。

収録刊行物

キーワード

詳細情報 詳細情報について

  • CRID
    1573105977757186304
  • NII論文ID
    110009728815
  • NII書誌ID
    AN10541106
  • 本文言語コード
    ja
  • データソース種別
    • CiNii Articles

問題の指摘

ページトップへ