M-021
近似k近傍グラフの作成による計算コスト削減手法の提案

◎廣中雅大・後藤佑介（岡山大）

　近年，k近傍グラフはデータベースの索引付けや画像探索に利用されており，大きな注目を集めている．しかし，探索対象となる事例の数が増加すると，k近傍グラフの構築にかかる計算量は膨大となる．本研究では，k近傍グラフに比べて計算コストを削減する近似k近傍グラフの作成手法を提案する．提案手法では，類似探索手法の一つである Locality Sensitive Hashing (LSH)， および近似k近傍グラフ構築手法の一つであるNN-Descent 法を組み合わせて近似k近傍グラフを作成する．また，半教師あり学習によるラベルの推定を行うことで，分類精度を維持しつつ，近似k近傍グラフの作成時間および探索時間を短縮する．評価では，k近傍グラフと比較して提案手法の有用性を確認する．