DEIM Forum 2019 D4-1

データストリームに対する効率良い頻出アイテム発見アルゴリズム
鳥谷部直弥†

喜田 拓也†† 北海道大学 大学院情報科学研究科 〒 060–0814 北海道札幌市北区北 14 条西 9 丁目
E-mail: †{toriyabe,kida}@ist.hokudai.ac.jp
あらまし データストリームから頻出なアイテムを見つける主要なカウンタベースのアルゴリズムとして，Frequent，Lossy counting，Space saving の三つが存在する．Frequent は出力されるアイテムの頻度とその推定値との誤差の範囲を保証することができないため，他の二つと比べて精度が低いという結果が出ている．本稿では，Frequent で用いられる k-reduced bag という考え方に基づいた新たなアルゴリズム（KRB）を提案する．KRB は，辞書に新たなアイテムを挿入する時，アイテムとその推定頻度に加えて k-reduction 操作が行われた回数を保持することで，理論上，Space saving より小さい誤差の範囲を保証できる．加えて，辞書の更新操作をならし O(1) 時間，作業領域は与えられたエラーパラメータ ϵ に対して，O( 1ϵ ) 語空間であり，共に Lossy counting よりも優れている．本稿における実験の範囲では，KRB が既存のアルゴリズムと同等の実行時間，精度を達成することを確認した．
キーワード 頻出値発見, 頻度計測, Lossy Counting
用することに加え，カウンタで保持するための条件を満たさな

1 はじめに頻出アイテム問題は，アイテムの列から与えられた閾値より多く出現するアイテムを求める問題である．この問題は，計算機科学における基本的な問題であり，これまで，多くの研究がされてきた [3] [8].
オンラインに際限なく流れてくるアイテムを順番に処理し，処理し終わったアイテムを破棄するアイテム処理の流れをデー
タストリーム [1] とよぶ．本稿では，データストリームは単にアイテムの列であるとし，過去のアイテムにはアクセスできないという制約が存在するものとする．アクセスの制約により，データストリームに対する処理は流れてくるアイテムの個数に依存しない限られたメモリ空間で高速に行う必要がある．

くなったアイテムを削除する k-reduction 操作の回数を記憶する．既存アルゴリズムとの理論比較では，KRB は更新時間と作業領域が Lossy counting より小さく，誤差の範囲が Spacesaving より小さかった．加えて，本稿で行った実験の範囲では，
KRB は，Lossy counting や Space saving と同等の実行速度，
精度を達成することを確認した．
本稿の構成は次のとおりである．2 節では，問題の定義と関連研究の説明，Misra&Gries [11] のアルゴリズムの説明を行う．

3 節では，提案アルゴリズム（KRB）の説明をする．4 節では，
KRB と他のアルゴリズムとの比較する．5 節で結論を述べる．

2 背景

頻出アイテム問題を解くための主要なアプローチは二つ存在

本節では，データストリームに関する基本的な定義と，関連する．一つ目は，ハッシュベースのアプローチ [2] [4] [5] である．

研究について述べる．有限な記号の集合をアルファベット A

複数のハッシュ表で構成されるデータ構造を用いることで，全とし，アルファベットの各要素をアイテムとよぶ．データストてのアイテムとその頻度を要約して保持することができる．二リーム S は，際限なく流れてくるアイテムの列と定義する．各つ目は，カウンタベースのアプローチ [6] [7] [9] [10] である．こ

時間に，一つのアイテムが流れてくるものとし，時間 N のデーのアプローチは，カウンタを用いて，頻出だと思われる候補のタストリームを SN = s1 s2 ... sN , ∀st ∈ A とかく. 加えて，アイテムのみを（部分的または推定された）頻度とともに保持アイテム i の頻度を fi ，アルゴリズム内での頻度の推定値を fˆi

する．

で表す．

本稿では，カウンタベースのアプローチのなかで，三つの主要なアルゴリズムである Frequent [6]，Lossy counting [9]，Space saving [10] に焦点をあてる．サーベイ論文 [3] [8] によると，Frequent は，他の二つと比べて少ないメモリで頻出アイ
テム問題を解くことができる．一方，出力されるアイテムの頻

2. 1 頻出アイテム問題
頻出アイテム問題の問題設定を定義する．一つ目は厳密な解を求める問題設定であり，二つ目と三つ目は厳密でない解を求める問題設定である．

度とその推定値との誤差の範囲を保証しておらず，精度が非常

定義 1 ((厳密な) 頻出アイテム問題). N 個のアイテムと，閾

に低いことがわかっている．そこで，本稿では，Frequent を

値 ϕ (0 < ϕ < 1) を与えた時，出現回数が ϕN より多いアイテ改善し，出力されるアイテムの頻度とその推定値との誤差のムを過不足なく含む集合を出力する．

範囲に保証を与えた新たなアルゴリズム（KRB）を提案する．

KRB は，Frequent で用いられる k-reduced bag の考え方を利データストリーム上で厳密な頻出アイテム問題を解くためには，全てのアイテムの頻度を正確に数え上げる必要があり，現実的ではない．そのため，定義 2 に，出力に偽陽性の解を含む

Algorithm 1 MG の 1 パス目

ことを許容した問題設定を，定義 3 に，出力される偽陽性の解

Input: オフラインのデータ s1 , ..., sN ，閾値 ϕ(0 < ϕ < 1)の出現頻度がある値を越えているという制約を与えた問題設定

Output: データに対する k-reduced bag

をそれぞれ定義する．

1
1: D ← ∅, k ← ⌈ ϕ⌉.

定 義 2 (ϕ-頻 出 ア イ テ ム 問 題). N 個 の ア イ テ ム と ，閾 値

2: for all t (1 <=t<
= N ) do3:

ϕ (0 < ϕ < 1) を与えた時，以下の条件を満たす集合を出

4:

力する．

5:

if st ∈ D thenfˆs ← fˆs + 1nn（ 1 ） 出現回数が ϕN より多いアイテムを必ず含む

6:else if |D| < k − 1 thenD ← D ∪ {sn }, fˆs ← 1（ 2 ） 他のアイテムを含む恐れがある．

7:

else

n

定義 3 (ϵ-近似頻出アイテム問題). N 個のアイテムと，閾値

9:for all j ∈ D dofˆj ← fˆj − 1

ϕ, ϵ (0 < ϵ < ϕ < 1) を与えた時，以下の条件を満たす集合を

10:

if fˆj = 0 then

出力する．

11:

8:

（ 1 ） 出現回数が ϕN より多いアイテムを必ず含む（ 2 ） 出現回数が (ϕ − ϵ)N 以下のアイテムを含まない（ 3 ） 他のアイテムを含む恐れがある．

12:
13:
14:

D ← D \ {j}end ifend forend if

15: end for2. 2 Hash-List 構造
カウンタベースのアプローチでは，カウンタを格納するため

度を 1 だけ減らし，頻度が 0 になったアイテムを削除する．

に辞書型のデータ構造を用いる．本稿では，ハッシュ表と双方

MG は 2 パスのアルゴリズムである．1 パス目では，受け向連結リストを組み合わせた Hash-List 構造 [7] [10] を用い取ったオフラインのデータに対して，単位時間に一つずつ先頭

る．ハッシュ表は，アイテムの挿入，探索，削除を効率よく行から順にアクセスする．各時点では，それまでに受け取った全

うための辞書としての役割を持つ．辞書内の全てのアイテムのてのアイテムに対する k-reduced bag を保持する．

頻度を効率よく管理するために，双方向連結リストを用いる．

ここで，辞書内に k 種類未満のアイテムしか含まれていない

ハッシュ表は，アイテムとその頻度を指し示すポインタを保持場合，これ以上，k-reduction 操作を行うことができないため，するカウンタで構成される．双方向連結リストは，ある整数とその時点までに受け取った全てのアイテムに対する k-reduced

その整数値と等しい推定頻度を持つ全てのアイテムにアクセス

bag を保持している．そのため，アクセスしたアイテムの頻度するための双方向連結リストを保持する頻度バケットにより構を正確に数え上げていき，辞書内に k 種類のアイテムが含まれ成される．頻度バケットは保持している整数値の昇順に並べらた時点で k-reduction 操作を行うことにより，辞書内に含まれれている，Hash-List 構造の作業領域は O(c) 語空間であり，各るアイテムの種類数は常に k 未満となり，k-reduced bag を保アイテムの挿入と削除，検索操作をそれぞれ O(1) 平均時間で持し続けることができる．すなわち，データ内のアイテムにア行うことができる．ただし，c はこの構造が保持するアイテム

クセスした際に行う辞書の更新操作は，(i) アイテムの頻度を 1の最大数である．

増やす，(ii) 新たなアイテムを挿入する，(iii) k-reduction 操作の三つになる．ここで，データに先頭から順にアクセスするこ

2. 3 Misra&Gries のアルゴリズム（MG）とにより，削除されるアイテムの組が一意に定まり，入力デー

1982 年に Misra と Gries [11] は，オフラインのデータに対し

タに対して k-reduced bag も一意に定まることに注意したい．

て，頻出アイテム問題を厳密に解くためのアルゴリズムを提案

2 パス目では，データを再び捜査し，1 パス目で求めたデータ全した．彼らのアルゴリズム（MG）は，k-reduced bag という体に対する k-reduced bag 内に残ったアイテムのみを厳密に数特別な集合を用いている．

え上げる．MG の 1 パス目をアルゴリズム 1 として記載する．

定義 4 (k-reduced bag). 多重集合から異なる k 種類のアイテ

以下の補題と定理は，MG の正当性を示している．

ムを削除する操作を k-reduction 操作とよぶ．多重集合に対し補題 5 ( [11]). N 個のアイテムを与えた時，MG の 1 パス目でて，k-reduction 操作をできる限り行った結果として残った多行われる k-reduction 操作の回数は，多くても ⌊ N⌋ 回である．
k

重集合を，元の多重集合の k-reduced bag とよぶ．
多重集合の k-reduced bag は，削除するアイテムの組み合 わ せ に よって 変 化 す る た め ，一 意 に は 定 ま ら な い ．例

定理 6 ( [11]). MG は厳密な頻出アイテム問題を解くアルゴリ
ズムである．

え ば ，{1, 1, 1, 1, 2, 2, 2, 3, 3, 4} に 対 す る 3-reduced bag は ，Proof. 全ての k-reduction 操作の対象となったアイテムは，真{1, 1, 1, 2} と {1} があり得る.

の頻度と MG による推定頻度との差が最も大きくなる．補題 5

アルゴリズム内で多重集合は辞書型のデータ構造を用いて，により，N 個のアイテムが与えられた時に，MG の 1 パス目でアイテムとその頻度の組で表現することができる．辞書に対す

k-reduction 操作が行われる回数は，多くても ⌊ N⌋ 回である．
k

る k-reduction 操作は，辞書内の異なる k 種類のアイテムの頻与えられたパラメータ ϕ に対して，k = ⌈ ϕ1 ⌉ とすると，真の頻度と MG による推定頻度との差は ϕN で抑えられることがAlgorithm 2 mFR algorithm

わかる．従って，真の頻度が ϕN より大きいアイテムは，必ずInput: データストリーム SN = s1 ...sN , 閾値 ϵ, ϕ(0 < ϵ < ϕ < 1)

k-reduced bag 内に含まれていることがわかる．ただし，真のOutput: ϵ-近似頻出アイテム問題の解

頻度が ϕN 以下のアイテムも含まれている可能性がある．MG

1: D ← ∅, k ← ⌈ 1ϵ ⌉.

の 2 パス目で，k-reduced bag 内のアイテムの頻度を正しく数え上げることにより，頻度が ϕN 以下のアイテムが除外される．従って，MG は厳密な頻出アイテム問題を解くことができる．

2. 4 Frequent（FR）

2: for all t (1 <=t<
= N ) do3:
4:

if st ∈ D thenfˆs ← fˆs + 1
n

n

6:

else if |D| < k − 1 thenD ← D ∪ {sn }, fˆs ← 1

7:

else

5:

n

MG の 1 パス目が，2002 年に Demaine ら [6]，2003 年に

9:

for all j ∈ D dofˆj ← fˆj − 1

Karp ら [7] により，それぞれ再発見され，データストリームに

10:

if fˆj = 0 then

対するアルゴリズム (Frequent; FR) として提案された．

11:

8:

D ← D \ {j}12:

end if定理 7 ( [6], [7]). Frequent は，辞書の更新操作をならし O(1)13:

end for

時間，作業領域を O( ϕ1 ) 語空間で ϕ-頻出アイテム問題を解く．

14:

end if

15: end for2. 5 関 連 研 究

16: output the set {i|fˆi > (ϕ − ϵ)N } from D

Cormode と Hadjieleftheriou [3] と Liu ら [8] はそれぞれデー
タストリームに対するアイテムマイニングのサーベイ論文を記

テムの頻度とその推定値との誤差の範囲を保証する ϵ-近似頻出

述している．

アイテム問題を解く．本稿では，FR の適合率の低さは問題設

カウンタベースのアルゴリズムは，解の候補となるアイテムと定によるものと仮定し，FR で用いている k-reduced bag の考

その頻度を持つカウンタをデータ構造を用いて保持する．2.3 節

え方を用いて，ϵ-近似頻出アイテム問題を解く手法について考で説明した Frequent [6] は，最大 k − 1 個のアイテムのカウンタ

察する．

を管理しているカウンタベースのアルゴリズムである．Mankuと Motwani [9] によって提案された Lossy Counting（LC）は，

3. 1 Modified Frequent（mFR）

与えられたデータを等間隔の ∆-バケットに分けて考える．LC

mFR は，FR の自然な拡張である．Liu ら [8] によると，FR

では，現在見ている ∆-バケットの数より小さい推定頻度を持を拡張し ϵ-近似頻出アイテム問題を解くことは理論的に可能だつアイテムを辞書から削除することで，頻度が大きいアイテムと記述されている．しかし，我々の知る限り，そのアルゴリズ

を辞書内に保持することができる．Liu ら [8] では，LC を改善

ムを明記した論文は存在しない．

した手法（modified LC; mLC）が説明されている．MetwallymFR の基本的な考え方は，LC や SS と同様である．ϵ-頻出ら [10] によって提案された Space Saving（SS）は，辞書内にアイテム問題を解き，その解から絞り込まれた最終的な出力が最大 k 個のカウンタを保持する．辞書内で保持しているカウン

ϵ-近似頻出アイテム問題の解となる．mFR をアルゴリズム 2

タが k 個になった時に，新たに出現したアイテムと推定頻度がに記載する．

一番小さいアイテムとを入れ替える．この時，新たに出現したアイテムの推定頻度は，削除したアイテムより 1 だけ大きい値とする．LC と SS は共に ϵ 近似頻出アイテム問題を解くアルゴリズムである．
ハッシュベースのアルゴリズム [2] [4] [5] は，スケッチとよば

補題 8. mFR において，アイテム i の頻度を fi ，推定頻度をˆfˆi とすると，不等式 fi − ϵN <= fi が成り立つ.
= fi <

Proof. エラーパラメータ ϵ に対して，k = ⌈ 1ϵ ⌉ とする．この時，辞書内のアイテムの推定頻度は頻度と比べて，多くてもれるデータ構造を用いる．

k-reduction 操作が起こった回数だけ小さくなる．補題 5 より，

3 提案アルゴリズム

k-reduction 操作の最大回数は，受け取ったアイテム数 N に対ˆ
して ϵN である．従って，fi − ϵN <= fi が成り立つ.
= fi <FR は ϕ-頻出アイテム問題を解くアルゴリズムである．過去のサーベイ論文 [3] [8] によると，実験により，FR は他の既存
アルゴリズム（LC, SS）と比べて，適合率（precision）が低い
ことが示されている．ϕ-頻出アイテム問題の解となるアイテム

補題 9 ( [9]). パラメータ ϕ, ϵ(0 < ϵ < ϕ < 1) を与えた時，不ˆˆ
等式 fi − ϵN <= fi が成り立つならば，{i|fi > (ϕ − ϵ)N }= fi <
は，ϵ-近似頻出アイテム問題の解になる．

は，頻度とその推定値との誤差の範囲を保証されていない．一定理 10. mFR は，辞書の更新操作をならし O(1) 時間，作業方，LC と SS は ϕ-頻出アイテム問題に対して，ϕ = ϵ とした領域を O( 1ϵ ) 語空間で ϵ-近似頻出アイテム問題を解く．

問題設定（ϵ-頻出アイテム問題）の解を求め，その解から最終

Proof. 補題 8 と 9 から，mFR は ϵ-近似頻出アイテム問題を的な出力となるアイテムを絞り込むことにより，出力するアイ

解くことができる．Hash-List 構造を使うことで，k-reduced

Algorithm 3 KRB

操作が起こった回数を ∆(t) とすると，拡張頻度 fi′ = fˆi + ∆(t)

Input: データストリーム SN = s1 ...sN , 閾値 ϵ, ϕ(0 < ϵ < ϕ < 1)は，真の頻度 fi と比べて，多くても ∆(t) まで大きくなる．従っOutput: ϵ-近似頻出アイテム問題の解′(t)て，fi <= fi <= fi + ∆ が成り立つ.

1: D ← ∅, k ← ⌈ 1ϵ ⌉, ∆(0) ← 0.
2: for all t (1 <=t<
= N ) do

補題 12. パラメータ ϕ, ϵ(0 < ϵ < ϕ < 1) を与えた時，不等式

if st ∈ D then

′
(t)
′
fi <
= fi <= fi + ∆ が成り立つならば，{i|fi > ϕN } は，ϵ-近3:fs′ n ← fs′ n + 1

4:

似頻出アイテム問題の解になる．

else if |D| < k − 1 then5:

D ← D ∪ {sn }, fs′ n ← ∆(t) + 1

6:

else

7:
8:

for all j ∈ D do

9:fj′ ← fj′ − 1

10:

if fj′ = 0 then11:

D ← D \ {j}12:

end if13:

end for14:∆(t) ← ∆(t) + 1
end if15:

16: end for
17: output the set {i|fi′ > ϕN } from D′ <Proof. Metwally ら [10] によると，不等式 fi − <fi +ϵN= fi =

が成り立つならば，{i|fi′ > ϕN } は，ϵ-近似頻出アイテム問題の(t)(N ) <
解になる．ここで，t <= N と補題 5 より，∆ <=∆= ϵN で′(t)あるので，fi − <= fi <= fi +∆ <= fi +ϵN が成り立つ．従って，′(t)′
不等式 fi − <= fi <= fi + ∆ が成り立つならば，{i|fi > ϕN }は，ϵ-近似頻出アイテム問題の解になる．
定理 13. KRB は，辞書の更新操作をならし O(1) 時間，作業
領域を O( 1ϵ ) 語空間で ϵ-近似頻出アイテム問題を解く．

Proof. 補題 11 と 12 から，KRB は ϵ-近似頻出アイテム問題
を解くことができる．辞書の更新時間と作業領域は，mFR と同一である．

bag を保持するための辞書の更新操作はならし O(1) 時間で実行できる．加えて，辞書内に挿入されるアイテム数の最大値は⌈ 1ϵ ⌉ − 1 であるので，作業領域は O( 1ϵ ) 語空間である．

3. 3 アルゴリズムの性能の比較
本節では，頻出アイテム問題を解くアルゴリズムを比較した．
表 1 に，辞書の更新時間と作業領域，頻度の誤差の範囲を比較

3. 2 KRB Algorithm

した結果を示す．ここで，頻度の誤差の範囲 [a, b] は，辞書に

本節では，k-reduced bag の考え方を用いて，ϵ-近似頻出ア

含まれるアイテム i の真の頻度を fi ，アルゴリズムによる推定

イテム問題を解くもう一つのアルゴリズムである KRB を提頻度または拡張頻度を ei とした時，fi + a <= ei <= fi + b が成案する．

り立つことを示している.

mFR では，アイテムを受け取りながら，各時点でのデータ

まず，k-reduced bag を用いたアルゴリズム（FR, mFR,

ストリームに対する k-reduced bag を保持した．これに加えて，KRB）の比較を行った．辞書の更新操作は，全てのアルゴリズ

KRB では時間 t での k-reduction 操作の回数（∆ 値）の情報

ムがならし O(1) 時間である．作業領域は，辞書に格納されるを用いる．すなわち，時点 t で，アイテム i が辞書に挿入される時，アイテムの推定頻度 fˆi とその時点での ∆ 値の和を拡張

アイテムの最大数に依存するため，FR は他の二つと比べて小頻度 fi′ = fˆi + ∆t として保持する．k-reduced bag を保持するに制約を設けていない．一方，mFR と KRB は，誤差の範囲

他の二つの操作（頻度を 1 だけ増やす操作，k-reduction 操作）
は mFR と同様である．ただし，fˆi が 0 かどうかを確認するたを定めているが，∆(t) <= ϵN であるため，KRB は mFR と比めに，k-reduction 操作に次のような変更を加える．

•

k-reduction 操作時に，推定頻度を減らす操作はしない．
′

さくなった．頻度の誤差の範囲に関しては，FR は誤差の範囲

べてより誤差の範囲が小さいことがわかる．
次に，KRB と mLC，SS の比較を行った．辞書の更新操作と作業領域に関しては，KRB と SS は，mLC と比べて小さかっ

fi′ = ∆t となるアイテムを辞書から削除する．
′
t′
ここで，t′ は t′ >= t を満たすある時点を表す．fi = ∆ が成た．頻度の誤差は，KRB と mLC が ∆(t) 以下，SS が ϵN 以

り立つ時，∆t − ∆t = fˆi が成り立つことになり，fˆi 回だけ

バケットの個数を表す．最後の ∆-バケットに含まれるアイテ

k-reduction 操作が行われたことで，アイテム i の推定頻度が 0

ムが挿入された時に，∆(t) = ϵN が成り立つ．KRB においてになったとみなすことができる．KRB をアルゴリズム 3 に記∆(t) = ϵN が成り立つ時，(i)k-reduction 操作の回数が ϵN で載する.

ある．(ii)ϵN 回目の操作の後にアイテムが挿入される．の二つ•′

補題 11. KRB において，アイテム i の頻度を fi ，推定頻度を fˆiとする．この時，推定頻度と挿入時の ∆ 値の和を fi′ = fˆi +∆(t)(t)′とすると，不等式 fi <= fi + ∆ が成り立つ.
= fi <

Proof. 辞書内のアイテム i の推定頻度 fˆi は頻度 fi と比べて，
k-reduction 操作が起こった回数だけ小さくなる．ここで，時間t でアイテム i が辞書に挿入された時，時間 t での k-reduction

下となっている．ここで，mLC において ∆(t) は確認した ∆-の条件を満たしている必要がある．それゆえ，KRB と mLC において，多くのアイテムが持つ ∆ 値は，ϵN より小さいことが
わかる．

4 実

験

本節では，KRB と他のカウンタベースのアルゴリズム（FR，表 1 辞書の更新時間と作業領域，頻度の誤差範囲の比較
名前

Frequent[Demaine ら，2002 年]
Modified Frequent[FR の自然な拡張 ]KRB[本論文の提案手法 ]Lossy counting[Manku と Motwani，2002 年]
Modified Lossy counting[Liu ら，2011 年]

更新時間

作業領域

頻度の誤差範囲

O(1) amortized

1
O( ϕ
)

[−ϕN , 0]O(1) amortizedO( 1ϵ )[−ϵN , 0]O(1) amortizedO( 1ϵ )

[0, ∆(t) ]O(log ϵN ) amortized O( 1ϵ log ϵN )[−ϵN , 0]O(log ϵN ) amortized O( 1ϵ log ϵN )[0, ∆(t) ]Space saving

O(1)[Metwally ら，2005 年]

FR
mFR

40

KRB
mLC

O( 1ϵ )

SS[0, ϵN ]

FR
mFR

1

KRB
mLC

SS

35
0.8

25

recalltime(msec)

30

20
15
10

0.6
0.4
0.2

5
0

0

0.5

1

1.5

0

2

0

0.5

1

s
図 1 s の変化による実行時間の比較
FR
mFR

KRB
mLC

SS

FR
mFR

1

80000

KRB
mLC

SS

0.8

60000
40000
20000
0

2

図 3 s の変化による再現率の比較

precision

memory(Byte)

100000

1.5

s

0.6
0.4
0.2

0

0.5

1

1.5

0

2

s

0

0.5

1

1.5

2

s

図 2 s の変化によるデータ構造の使用メモリ量の比較

図 4 s の変化による適合率の比較

mFR，mLC，SS）との実験による比較を行う．FR は ϕ-頻出

本稿では，以下の二つの実験を行った．

アイテム問題を解くアルゴリズムであり，他のアルゴリズムは（ 1 ） k-reduced bag を用いたアルゴリズムの比較

ϵ-近似頻出アイテム問題を解くアルゴリズムである．各アルゴ（ 2 ） ϵ-近似頻出アイテム問題を解くアルゴリズムの比較

リズム は，C 言語を用いて実装し，データ構造は Hash-List

各実験では，(i) 実行時間，(ii) データ構造の使用メモリ，(iii)構造を採用した．実行環境として，Mac Book Pro (MacOSX

精度（再現率，適合率）の三つの観点からアルゴリズムの性能

10.14.1, Dual-core Intel Core i5 2.9GHz, 8 GB RAM) を用いを比較した．実行時間は５回測定した結果の平均値で比較をた．実験に用いたデータは，zipf 則に基づく人工データであり，

行った．

1

skew パラメータ s を 0.0 から 2.0 まで変化させた．データスト

はじめに，サポート閾値を ϕ = 0.01 とした時に，skew パラ

リームに流れてくるアイテムの数は 2 × 10 ，アルファベット

メータ s を 0.0 から 2.0 まで変化させて，上記の項目を比較し

8

7

サイズは 10 種類とした．

た．図 1 から 4 はそれぞれ実行時間，データ構造の使用メモリ，
再現率，適合率の比較の結果を表す．次に，skew パラメータ

1：https://github.com/naobird/FrequentItemsMining

を s = 1.0 とした時に，サポート閾値 ϕ を 0.001, 0.005, 0.01,

FR
mFR

time(msec)

40

KRB
mLC

を改善し，偽陽性となる解の頻度に保証を与えた新たなアルゴ

SS

リズムである KRB を提案した．KRB は，k-reduced bag の考35

え方を用いて，ϵ-近似頻出アイテム問題を解くアルゴリズムで30ある．k-reduction 操作の回数である ∆ 値を保持することによ25

り，偽陽性の解となるアイテムの頻度を正確に推定できる．

20
15KRB と既存手法の理論比較では，辞書の更新はならし O(1)10

時間，作業領域は O( 1ϵ ) 語空間であり，共に mLC より小さい

5

値である．加えて，偽陽性の解の頻度保証は ∆ 値であり，SS

0
0.001

0.01

0.1

φ

より小さい値である．
比較実験により，KRB は，FR や mFR と比べて高い適合率であり，mLC や SS と比較しても同等の実行速度，精度である

図 5 ϕ の変化による実行時間の比較

ことを確認した．
6

1x10

FR
mFR

KRB
mLC

SS

今後の課題として，頻出アイテム集合マイニング [12] などの他の問題に対する k-reduced bag の考え方の応用が挙げられる．

memory(Byte)

100000

文

10000
1000
100
10
1
0.1
0.001

0.01

φ

0.1

図 6 ϕ の変化によるデータ構造の使用メモリ量の比較

0.05, 0.1 と変化させて，上記の項目を比較した．図 5 ，6 はそれぞれ実行時間，データ構造の使用メモリの比較の結果を表す．
ここで，それぞれの ϕ に対して，エラーパラメータ ϵ = 0.2ϕとした．精度に関しては，正しい解が存在する時のみ測定を行った．

k-reduced bag の考え方に基づくアルゴリズムである FR とmFR，KRB を比較した結果，実行速度に大きな差はなかった．
データ構造の使用メモリは，問題設定により，FR が mFR や

KRB と比べて小さかった．再現率は，全てのアルゴリズムで 1となり，偽陰性の解を含まないことを確認した．適合率は，FRが mFR や KRB と比べて非常に低い結果となり，ϵ-近似頻出
アイテム問題を解く mFR や KRB の優位性を確認した．特に，我々が行った実験の範囲では，KRB の適合率は全て 1 となっているため，mFR と比べて解となるアイテムが持つ頻度の誤差が小さくなっていると考えられる．

ϵ-近似頻出アイテム問題を解く KRB と mLC，SS を比較した結果，実行速度に大きな差はなかった．データ構造の使用メ
モリは，mLC が概ね小さいという結果となった．再現率は，全てのアルゴリズムで 1 となり，偽陰性の解を含まないことを確認した．加えて，我々が行った実験の範囲では，解の適合率も全てのアルゴリズムで 1 となった．以上の結果から，KRB の実行速度と精度が mLC や SS と同等であることがわかった．

5 おわりに本稿では，カウントベースのアルゴリズムの一つである FR

献[1] Babcock, Brian and Babu, Shivnath and Datar, Mayur andMotwani, Rajeev and Widom, Jennifer, “Models and issues
in data stream systems,” Proceedings of the twenty-first
ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems(PODS), pp.1–16, 2002.
[2] Charikar, Moses and Chen, Kevin and Farach-Colton, Martin, “Finding frequent items in data streams,” TheoreticalComputer Science, Vol. 312, No. 1, pp. 3–15, 2004.
[3] Cormode, Graham and Hadjieleftheriou, Marios, “Methods
for finding frequent items in data streams,” The VLDB
Journal , Vol.19, No. 1, pp. 3–20, 2010.
[4] Cormode, Graham and Muthukrishnan, Shan, “An improved data stream summary: the count-min sketch andits applications,” Journal of Algorithms, Vol. 55, No. 1, pp.
58–75, 2005,[5] Cormode, Graham and Muthukrishnan, Shan, “What’s hot
and what’s not: tracking most frequent items dynamically,”
ACM Transactions on Database Systems (TODS), Vol. 30,
No.1, pp. 249–278, 2005.
[6] Demaine, Erik D and López-Ortiz, Alejandro and Munro, J
Ian, “Frequency estimation of internet packet streams withlimited space,” European Symposium on Algorithms (ESA),
pp. 348–360, 2002.
[7] Karp, Richard M and Shenker, Scott and Papadimitriou,
Christos H, “A simple algorithm for finding frequent elements in streams and bags,” ACM Transactions on
Database Systems (TODS), Vol.28, No. 1, pp.51–55, 2003.
[8] Liu, Hongyan and Lin, Yuan and Han, Jiawei, “Methods
for mining frequent items in data streams: an overview,”
Knowledge and information systems, Vol. 26, No. 1, pp.
1–30, 2011.
[9] Manku, Gurmeet Singh and Motwani, Rajeev, “Approximate frequency counts over data streams,” Proceedingsof the 28th international conference on Very Large Data
Bases(VLDB), pp. 346–357, 2002.
[10] Metwally, Ahmed and Agrawal, Divyakant and El Abbadi,
Amr, “Eﬃcient computation of frequent and top-k elements
in data streams,” International Conference on Database
Theory(ICDT), pp. 398–412, 2005.
[11] Misra, Jayadev and Gries, David, “Finding repeated elements,” Science of computer programming, Vol. 2, pp. 143–
152, 1982.
[12] Yamamoto, Yoshitaka and Iwanuma, Koji and Fukuda,
Shoshi, “Resource-oriented approximation for frequent
itemset mining from bursty data streams,” Proceedings ofthe 2014 ACM SIGMOD international conference on Management of data(SIGMOD), pp. 205–216, 2014.