集合間類似度を用いたストリームデータのtop-k類似検索に対する高速な厳密解アルゴリズム

摘要

ストリームデータの類似検索は，正常／異常検出や情報推薦の基盤となる技術として注目されている．本研究では，データストリームの直近の要素集合をクエリとし，データベースから最も類似するk個のデータを検索する問題を取り扱う．本問題に対してはこれまで，現在の時刻で上位k位に入る可能性があるデータを過去に計算した類似度から決定し，それらに対してのみ類似度を計算する枝刈りによる厳密解アルゴリズムが提案されている．これに対して本研究では，既存手法より大幅に実行時間を短縮する高速な厳密解アルゴリズムを提案する．提案手法は，頻度を考慮した転置インデックスを用いて現在時刻と次の時刻で類似度が変わるデータを効率的に特定し，それらに対してのみ，類似度を更新することで類似度の計算回数を減らす．さらに，類似度もO（1）で更新することで処理時間を短縮する．