講演情報
[4D-01]異周期カウンタと挿入遅延によるデータストリームに対する頻度クエリの精度向上
*山川 竜太郎1、古賀 久志1 (1. 電気通信大学)
発表者区分：学生
論文種別：ロングペーパー
インタラクティブ発表：あり
論文種別：ロングペーパー
インタラクティブ発表：あり
キーワード：
ストリームデータ、頻度クエリ、スライディングウィンドウ、問合せ処理、スケッチ
Iotなどに活用されているストリームデータは大容量なので，すべて保存するのは難しい．そのためスケッチと呼ばれる要約を用いる．Count-Min Sketch(以下，CMS)は指定された要素の近似頻度を返すための代表的なスケッチである．CMSでは真の頻度よりも大きな値を返す複数のカウンタを用意し，その最小値を近似頻度とすることで誤差を抑制する．Sliding Sketch(以下，SS)は，CMSをスライディングウィンドウモデルに拡張した手法である．しかし，SSではカウンタ毎に保持期間が異なっており，保持期間が最も短いカウンタが最小値を取りやすく，複数のカウンタを用いることによる頻度の補正能力が弱くなっている．本研究では，(1)リセットする周期をカウンタによって変える異周期カウンタと (2)前処理により頻度誤差を補正する遅延挿入という2種類の要素技術を提案し，SSの近似頻度の精度を向上させる．