4B-1
メトリック空間における最近傍ペア探索アルゴリズムの高速化
○倉沢 央（東大），高須淳宏，安達 淳（国立情報学研）
我々は，データセット中のオブジェクトのペアのうち類似度の高い上位k個のペアを見つける処理
の高速化について取り組んでいる．いかにして類似度の低いオブジェクトのペアを枝刈りするか
が本研究の課題である．従来手法では，最近傍ペア間の距離を考慮して空間を分割し，枝刈りす
ることで距離計算コストを削減していた．これに対して，我々は2つの改善手法を提案する．1つ
は空間の多分割手法である．多分割化することで枝刈りできるオブジェクト数を多くした．もう
1つは最近傍ペア間の距離の予想値の収束化手法である．この予想値は枝刈りに使うしきい値と同
値であり，枝刈り効率の向上に役立てた．実験により，提案手法は距離計算コストの削減に効果
があることを確かめた．