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

摘要

データストリームに対する重要な問題の一つに，頻出アイテム問題（頻出値問題）がある.いま，ある集合Σの要素（アイテム）が絶え間なく入力されるデータストリームを考える.また，Σの各要素は自然数に一対一に写像されるものとする.このとき，頻出値問題とは，与 えられた閾値以上の頻度でデータストリーム中に出現す る自然数を見つけ出すことである.データストリームの 性質上，すべての値の出現回数を保持するのは多くの記 憶容量を必要とするため，頻出値問題を厳密に解くこと は困難である.したがって，ここでは，出力に偽陽性の 解が含まれることを許容する問題を考える.