@misc{oai:uec.repo.nii.ac.jp:00008704,
 author = {山﨑, 智博},
 month = {2018-04-13},
 note = {2017, IoT の隆盛に伴い，ストリームデータ解析の重要性が高まっている．その中でストリームデータを対象とする類似検索は，正常/異常検出や情報推薦の基盤となる技術として注目されている．
　ストリームデータに対する類似検索には様々な問題設定が知られているが，本研究では，2016年にXuらによって提案された「Continuous Similarity Search for Evolving Queries」(CSPEQ)問題を取り扱う．この問題は，アルファベットを要素とするストリームデータを取り扱い，ストリームの直近の要素群をクエリ集合として，集合のデータベースからクエリと最も類似した上位k個のデータを探すことを目的とし，時間によるユーザの嗜好の変化に適応的に情報推薦を行う状況をモデル化したものである．クエリがユーザの最近の嗜好，検索結果がユーザの嗜好に合わせて推薦されるオブジェクトに相当する．
　この問題に対する自明な解法は，毎時刻クエリと全データ間で類似度を計算することである．一方Xuらは，過去に計算した類似度の値から現在時刻で上位k 位に入る可能性があるデータを決定し，それらに対してのみ類似度を計算する枝刈りによる厳密解法GP(General Pruning algorithm)とMin-Hash を用いた近似解法MHI(MinHash-based algorithm using inverted indices)を提案した．
　これに対して本研究では，前の時刻から類似度が変化する可能性があるデータに対してのみ，現在の類似度を更新することで，類似度の計算回数を大幅に減らし，さらに1回の類似度計算もO(1)で行うことで高速化する新しい手法をEA-FIL(Exact Algorithm using　Frequency-based Inverted Lists)を提案した．そして，実験的にその性能を評価した結果，MHI と同じくらい高速で，GPを10倍以上凌駕する性能であることが確認できた．
　また，CSPEQ 問題はスライディングウインドウサイズを固定していることから，要素数がスライディングウインドウサイズと大きく違うデータベース内の集合は類似度が低くなって検索結果となりにくいという問題を持っている．本論文ではこれを緩和するため，ウインドウサイズに幅を持たせた新しい問題設定を提唱し，それに対する高速なアルゴリズムVWEA-FIL(Variable Window size EA-FIL)も構築した．これについても評価実験を行った結果，EA-FIL を全てのウインドウサイズに適用する単純手法よりも高速で空間計算量も小さいことが確認できた．},
 title = {集合間類似度を用いたストリームデータのtop-k類似検索に対する高速な厳密解アルゴリズム},
 year = {},
 yomi = {ヤマザキ, トモヒロ}
}