Publications
JOURNAL (DOMESTIC) 木構造型インデックスを利用した近似k最近傍グラフによる近傍検索
情報処理学会論文誌
February 01, 2011
大量の多種多様なデータを高速に検索するには空間インデックスが不可欠となる.空間インデックスの1つであるk最近傍グラフによるインデックス(kNNG)では最近傍検索の高速性が確認されているが,インデックス生成のコストがきわめて高いという問題がある.インデックス生成時に生成途中のインデックスを用いてk最近傍検索を行うことでkNNGを近似するインデックスを高速に生成するANNG(Approximate k-Nearest Neighbor Graph)を筆者はすでに提案している.しかし,ANNGではランダムに選択したノードからグラフを探索するのでグラフが大量のノードを有する場合に探索コストが増加するという問題点がある.そこで,本稿ではANNGにおいて木構造型のインデックスを利用することにより低コストで近傍ノードを探索できる方法を提案し,一様分布データおよび画像特徴量を用いて提案手法がANNGよりコストを低減できることを確認した.