BIDE: Efficient Mining of Frequent Closed Sequences

今読んでる論文のアブストラクトの日本語訳をメモっておきます。あくまで個人的なメモなので、参考程度で。。。

BIDE : 頻出飽和系列の効率的なマイニング
これまでの研究によって、頻出系列マイニングアルゴリズムは頻出系列を抽出するのではなく、飽和系列を抽出することが明らかになった。これは、飽和系列が完全な結果セットを小型化したものというだけでなく、より効率的なものだからである。しかし、これまでの抽出候補の保持とテスト(the candidate maintenance-and-test)を基にした多くの飽和系列マイニングアルゴリズムの研究は、支持度の閾値が低い時や系列長が長くなった時は本質的に計算時間とメモリ使用量が大きくなる。
本論文では、抽出候補の保持を行わない頻出飽和系列の効率的なマイニング手法 BIDE を提案する。双方向拡張(BI-Directional Extension)と呼ばれる新しい系列終了チェック方法(a novel closure checking scheme)を適用し、BackScan削減手法とScanSkip最適化テクニックを用いることで、これまでのマイニング手法と比べ探索空間をより削減する。実際に観測されたデータによるパフォーマンス評価によって、BIDEはこれまでの手法より優れていることを示す。また、データベースの大きさに対して線形のオーダーであることなども示す。

[pdf]BIDE: Efficient Mining of Frequent Closed Sequences
Author: Jiawei Han