A-021
データストリームに対する頻出値問題を解くアルゴリズムの実証実験

◎鳥谷部直弥・谷　陽太・喜田拓也（北大）

データストリームに対するマイニングの重要な問題の一つとして，頻出値問題が存在する．頻出値問題は，大別してφ頻出問題とε近似頻出問題の二つがある．φ頻出問題を解くアルゴリズムとしては，MisraとGriesらによって提案されたk-reduced bag法と，Metwallyらによって提案されたSpace Saving法がある．一方，ε近似頻出問題を解くアルゴリズムとしては，MankuとMotwaniらによって提案されたLossy Counting法がある．CormodeとHadjieleftheriouらが2010年の論文で示唆している通り，これらのアルゴリズムはφ頻出問題とε近似頻出問題の両方に適用できる．本論文では，上述した三つのアルゴリズムの実装を行い，各問題に適用した際の性能比較実験の結果を示す．