Towards a sublinear summarization for streaming partially-ordered data

本研究の3年目にあたる本年は、昨年度に提案したカーネル密度推定 (Kernel Density Estimation, KDE) に基づくサポートサマリ GRACE の予備的な性能評価実験と計算量の理論的な解析を行った。GRACEは、KDEを与える劣線形スケッチ RACE (Repeated Arrays of Count Estimators) をグリッド上に配置した多層的なデータ構造を取る。RACEを基本要素としてGRACEを実装し、密なトランザクションデータストリームのベンチマークとして知られるマッシュルームデータに対して、サポートクエリに対する出力の近似精度とメモリ消費量の関係を検証した（実験結果は知識ベースシステム研究会にて発表)。次にサポートクエリに対してε劣性を満たすGRACEの空間計算量を解析的に調査したところ、トランザクション長を m に対して O(2^m) であることがわかった。ストリーム長 (トランザクションの個数) に依存しない点は一定の評価ができるものの、GRACEにおいてもトランザクションの長さに対する組み合わせ爆発は避けることができない見通しとなった。なお、PODS'16論文において、ε劣性を満たすサポートサマリの空間計算量の下界がΩ(m)であると示されているが、この下界とGRACEの計算量とは大きなギャップが存在している。ただし、下界に近い空間計算量で動作する非サンプリングアルゴリズムは存在し得ない (存在するとすればパターンマイニング研究の極めて重要な発見となる) と考えるのが一般的であり、現在、下界の方を修正することができないか解析を進めている。

本研究の3年目にあたる本年は、昨年度に提案したカーネル密度推定 (Kernel Density Estimation, KDE) に基づくサポートサマリ GRACE の予備的な性能評価実験と計算量の理論的な解析を行った。GRACEは、KDEを与える劣線形スケッチ RACE (Repeated Arrays of Count Estimators) をグリッド上に配置した多層的なデータ構造を取る。RACEを基本要素としてGRACEを実装し、密なトランザクションデータストリームのベンチマークとして知られるマッシュルームデータに対して、サポートクエリに対する出力の近似精度とメモリ消費量の関係を検証した（実験結果は知識ベースシステム研究会にて発表)。次にサポートクエリに対してε劣性を満たすGRACEの空間計算量を解析的に調査したところ、トランザクション長を m に対して O(2^m) であることがわかった。ストリーム長 (トランザクションの個数) に依存しない点は一定の評価ができるものの、GRACEにおいてもトランザクションの長さに対する組み合わせ爆発は避けることができない見通しとなった。なお、PODS'16論文において、ε劣性を満たすサポートサマリの空間計算量の下界がΩ(m)であると示されているが、この下界とGRACEの計算量とは大きなギャップが存在している。ただし、下界に近い空間計算量で動作する非サンプリングアルゴリズムは存在し得ない (存在するとすればパターンマイニング研究の極めて重要な発見となる) と考えるのが一般的であり、現在、下界の方を修正することができないか解析を進めている。