メトリック空間における最近傍ペア探索アルゴリズムの高速化

• 倉沢央

• 高須淳宏

• 安達淳

抄録

我々は，データセット中のオブジェクトのペアのうち類似度の高い上位k個のペアを見つける処理の高速化について取り組んでいる．いかにして類似度の低いオブジェクトのペアを枝刈りするかが本研究の課題である．従来手法では，最近傍ペア間の距離を考慮して空間を分割し，枝刈りすることで距離計算コストを削減していた．これに対して，我々は2つの改善手法を提案する．1つは空間の多分割手法である．多分割化することで枝刈りできるオブジェクト数を多くした．もう1つは最近傍ペア間の距離の予想値の収束化手法である．この予想値は枝刈りに使うしきい値と同値であり，枝刈り効率の向上に役立てた．実験により，提案手法は距離計算コストの削減に効果があることを確かめた．

収録刊行物

• 第73回全国大会講演論文集

  第73回全国大会講演論文集 2011 (1), 507-508, 2011-03-02

  一般社団法人情報処理学会

キーワード

• データベースとメディア

詳細情報

• CRID: 1050574047113625856
• NII論文ID: 110008600896
• NII書誌ID: AN00349328
• Web Site: http://id.nii.ac.jp/1001/00108258/
• 本文言語コード: ja
• 資料種別: conference paper
• データソース種別:
  • IRDB
  • CiNii Articles