抄録
D-022
クラスタリングを利用した距離尺度の組み合わせによるTop-k検索
◎鈴木貴敦（東大）・高須淳宏・安達　淳（NII）
クエリとの類似度評価にEuclid距離を用いたTop-k検索問題の中で、オブジェクトの組み合わせを対象とした問題を取り上げる。これは、データセットUとクエリQが与えられたときに、U中のオブジェクトvを重複なく組み合わせたものに対して、クエリとのEuclid距離が最も小さくなる上位k組の組み合わせを求める検索タスクである。本手法では、事前処理としてk-meansによるクラスタリングを行い、類似度の高いオブジェクトをまとめて扱うことで高速化を行う。実験の結果、全て解を列挙する方法と比較して、最大で80%以上の計算時間短縮を確認した。