講演抄録/キーワード |
講演名 |
2017-05-12 13:30
集合間類似度を用いたストリームデータのtop-k類似検索に対する高速な厳密解アルゴリズム ○山崎智博・古賀久志・戸田貴久(電通大) COMP2017-1 |
抄録 |
(和) |
ストリームデータの類似検索は,正常/異常検出や情報推薦の基盤となる技術として注目されている.本研究では,データストリームの直近の要素集合をクエリとし,データベースから最も類似する$k$個のデータを検索する問題を取り扱う.本問題に対してはこれまで,現在の時刻で上位$k$位に入る可能性があるデータを過去に計算した類似度から決定し,それらに対してのみ類似度を計算する枝刈りによる厳密解アルゴリズムが提案されている.これに対して本研究では,既存手法より大幅に実行時間を短縮する高速な厳密解アルゴリズムを提案する.提案手法は,頻度を考慮した転置インデックスを用いて現在時刻と次の時刻で類似度が変わるデータを効率的に特定し,それらに対してのみ,類似度を更新することで類似度の計算回数を減らす.さらに,類似度も$O(1)$で更新することで処理時間を短縮する. |
(英) |
|
キーワード |
(和) |
ストリームデータ / 類似検索 / 転置インデックス / / / / / |
(英) |
/ / / / / / / |
文献情報 |
信学技報, vol. 117, no. 28, COMP2017-1, pp. 1-8, 2017年5月. |
資料番号 |
COMP2017-1 |
発行日 |
2017-05-05 (COMP) |
ISSN |
Print edition: ISSN 0913-5685 Online edition: ISSN 2432-6380 |
著作権に ついて |
技術研究報告に掲載された論文の著作権は電子情報通信学会に帰属します.(許諾番号:10GA0019/12GB0052/13GB0056/17GB0034/18GB0034) |
PDFダウンロード |
COMP2017-1 |