Publications
JOURNAL (DOMESTIC) 近似k最近傍グラフによる距離空間の近傍検索
情報処理学会論文誌:データベース
March 01, 2010
大量の多種多様なデータを高速に検索するには空間インデックスが不可欠となる.空間インデックスの 1 つである k 最近傍グラフによるインデックス (kNNG) では最近傍検索の高速性が確認されているが,高コストなインデックス生成および非連結グラフに起因する検索精度の低下といった問題がある.本稿ではこの kNNG に着目し,インデックス生成時に連結グラフを保証しながら逐次ノードを追加し,かつ,生成途中のインデックスを用いてk最近傍検索を行うことで kNNG を近似する ANNG (Approximate k-Nearest Neighbor Graph) を高速に生成する方法を提案する.さらに,一様分布データや実際の画像特徴量を用いて ANNG の評価を行い,kNNG の問題に対して ANNG が優位であることを確認した.
PDF : 近似k最近傍グラフによる距離空間の近傍検索