順序逆転のある時系列センサデータのための効率的な索引付方法の提案と性能評価

摘要

近年，センサ技術やネットワーク技術の発展によって，実空間の刻々と変化する状態をデータとして取得することが可能になりつつある．今後，センサの増加により，時系列センサデータの流通量が爆発的に増えると考えられる．このような時系列センサデータに対して，特定変化パターンをリアルタイムに検出することと，再利用可能な形で高速に格納·蓄積することが求められている．特定変化パターンの検出においては，データ順序の正確性が求められるが，シンクノードにおける遅延などにより入力時に順序逆転が起きるという問題がある．一方，データの蓄積においては，従来ではフィルタによりデータを間引いて格納する方式が取られており，データの再利用性が低いという問題がある．そこで我々は，順序逆転のある時系列センサデータに対し，リアルタイムな検索と，間引くこのない格納を行うための，索引付方法を提案する．提案方法ではOffset bitmapという新しいデータ構造により従来の索引付方法であるSparse indexを拡張し，入力データの順序逆転に対応しつつ，高速なデータ格納を実現する．本稿において，従来の索引付方法との比較実験を行い，提案方法の有効性を示した．