空間計算量の評価実験

第6章 実験 37

(1)ラベル種類数|Φ|を変化 (2)平均集合サイズW を変化 図 6–10: top-k類似検索におけるEA-FILに対するVWEA-FILの計算回数の割合

第6章 実験 38

らである．これにより，空間計算量においても，VWEA-FILがEA-FILを上回る 性能であることが示された．

39

第 7 _章 関連研究

CSPEQ問題は2016年に提唱された新しい問題であり，この問題を扱った先行

研究は[1]だけである．本章では，ストリームデータの類似検索に関してまとめる．

ストリームデータの類似検索は，時間経過に伴って(1)データベースが変化するタ イプ，(2)クエリが変化するタイプ，(3)クエリとデータベース両方が変化するタ イプがあり得る．(1)のデータベースが時間経過に伴って変化するタイプがこれま で最も盛んに研究されている．Yangら[6]はユーザの嗜好性を表すクエリ関数F に対して，データベースからF(S)の値が最大になるデータを探索するtop-k問題 を考えた．データには有効期間が設定されており，top-k内のデータの有効期間が 切れた時にいかに効率よくtop-kを更新するかが論点である．Raoら[7]は複数の クエリ間でデータを評価した結果を共有させることでクエリの処理効率を向上さ せている．Lianら[8]は実数値が追加されるデータストリームに対して，W 次元 データに対する類似検索をLocality-Sensitive Hashing[2]で実現した．この方法で は時間経過と共にハッシュ関数を更新する．

本研究が取り扱うCSPEQ問題[1]は(2)のクエリのみが変化する問題である．

Kontakiら[9]は，クエリとデータベースが両方変化する状況での類似検索を考え

た．DFT(Discrete Fourier Transform)係数をストリームの特徴量として使用し，

特徴量を効率よく更新する方法を提案した．

Datarら[10]は本研究と同様に時間と共に変化する集合を取扱い，Min-Hashの ハッシュ値を効率的に更新する手法を開発した．この手法は3.2節で述べた Min-Hashベースの近似解法のサブルーチンとして使える技術であるが，具体的な類 似検索問題への適用までは議論されていない．また，本研究ではスライディング ウィンドウ内のデータを集合として取り扱うが，これを文字列として扱う研究は

第7章 関連研究 40

古くから多くなされている．近年の研究成果としては，ハミング距離がクエリ文 字列と高々k異なるパターンを発見するk-mismatch problemをストリーミング環 境[11][12]で解いた例がある．

41

第 8 _章 結論

本論文では，CSPEQ問題に対する厳密解アルゴリズムEA-FILとこの問題を拡 張した問題とその高速な厳密解法を提案した．

このアルゴリズムは，頻度を考慮した転置インデックスによって，類似度が変 化する可能性がある集合のみを処理対象とした．また，類似度の計算を前回の類 似度，クエリに追加される要素と除かれる要素から，O(1)で行うことができるよ うにした．このとき，転置インデックスによる類似度の更新を可能にするため，特 定の要素を含まない集合を処理対象から除外するようアルゴリズムを改良した．

そして，従来の厳密解法および，近似解法との比較実験を行った．その結果提 案手法は，従来の近似解法と同じくらい高速であり，従来の厳密解法を凌駕する 性能であることが確認できた．

本論文では，CSPEQ問題の欠点を補う新しい問題設定を考案した．この問題設 定では，ウインドウサイズの最大値と最小値を決めておき，その中から各集合に 対して一番Jaccard係数が大きいものを集合とクエリとの類似度とすることで，集 合のサイズの差により類似度の上限値が小さくなる問題を緩和した．また，その 問題設定に対して単純にEA-FILを適用するよりも数倍高速な厳密解アルゴリズ ムを提案した．

参考文献 42

参考文献

[1] X. Xu, C. Gao, J. Pei, K. Wang, and A. Al-Barakati, ”Continuous similarity search for evolving queries,” Knowledge and Information Systems, vol.48(3), pp.649-678, September 2016.

[2] M. Datar, N. Immorlica, P. Indyk and V.S. Mirrokni, ”Locality-sensitive Hashing Scheme Based on P-stable Distributions”, Proc. Twentieth Sympo-sium on Computational Geometry, pp.253-262, 2004.

[3] A. Z. Broder, M. Charikar, A. M. Frieze and M. Mitzenmacher, ”Min-Wise In-dependent Permutations”, Journal of Computer and System Sciences, vol.60(3), pp.630-659, 2000

[4] http://fimi.ua.ac.be/data/

[5] http://www.philippe-fournier-viger.com/spmf/index.php?link=datasets.php [6] D. Yang, A. Shastri, E. A. Rundensteiner, and M. O. Ward,”An Optimal Strategy for Monitoring Top-k Queries in Streaming Windows”,Proc. 14th International Conference on Extending Database Technology, pp.57-68, 2011.

[7] W Rao, L Chen, S Chen and S Tarkoma, ”Evaluating continuous top-k queries over document streams” World Wide Web vol.17(1), pp.59-83, 2012.

[8] X. Lian,L. Chen and B. Wang, ”Approximate similarity search over multiple stream time series”, Proc. 12th international conference on database systems for advanced applications(DASFAA’07), pp.962-968, 2007.

[9] M. Kontaki,A. N. Papadopoulos and Y. Manolopoulos,”Adaptive similarity search in streaming time series with sliding windows”, Data & Knowledge Engineering, vol.63(2), pp.478-502, 2007.

[10] M. Date and, S. Muthukrishnan ”Estimating rarity and similarity over data stream windows”, Proc. 10th European Symposium on Algorithms(ESA’02), pp.323-335, 2002.

参考文献 43

[11] R. Clifford and B. Sach. ”Pseudo-realtime pattern matching: Closing the gap”, Proc. 21st Symp. on Combinatorial Pattern Matching, pp.101-111, 2010.

[12] R. Clifford, and A. Fontaine, E. Porat,B. Sach, and T. Starikovskaya, ”The k-mismatch problem revisited”, Proc. Twenty-seventh Annual ACM-SIAM Symposium on Discrete Algorithms, pp.2039-2052, 2016.

44

謝辞

本研究を行うにあたり，研究の場と適切なご指導，ご助言を頂いた古賀久志准教 授，南泰浩教授に深く感謝いたします．日頃から研究に関する活発なご意見，ご助 言を頂いた戸田貴久助教授と中鹿亘助教授に深く感謝いたします．多忙の中，多 くのご助言，ご指導下さった柳生智彦客員准教授と鈴木一哉客員准教授に深く感 謝いたします．また，研究室での生活や研究の様々な場面でご助言を頂きました 南·古賀·戸田· 中鹿研究室の学生の皆さま，すでにご卒業された先輩方に感謝い たします．

平成30年3月7日

45

図一覧

2–1 問題設定 . . . 3

4–1 頻度を考慮した転置インデックス . . . 15

5–1 拡張した問題設定 . . . 22

6–1 データ数nを変化させたときの実行時間 . . . 29

6–2 ラベル種類数|Φ|を変化させたときの実行時間 . . . 29

6–3 ウインドウサイズWを変化させたときの実行時間 . . . 30

6–4 実データに対するtop-k類似検索の実行時間 . . . 31

6–5 人工データに対するtop-k類似検索の枝刈り効率 . . . 32

6–6 人工データに対するtop-k類似検索の空間計算量 . . . 33

6–7 データ数nを変化させたときの拡張した問題設定に対する各アルゴ リズムの実行時間 . . . 34

6–8 ラベル種類数|Φ|を変化させたときの拡張した問題設定に対する各 アルゴリズムの実行時間 . . . 35

6–9 平均集合サイズW を変化させたときの拡張した問題設定に対する 各アルゴリズムの実行時間 . . . 36

6–10 top-k類似検索におけるEA-FILに対するVWEA-FILの計算回数の 割合 . . . 37

6–11人工データに対するtop-k類似検索の空間計算量 . . . 37