カウント・ディスティンクト問題

コンピュータサイエンスにおいて、個数カウント問題^[1] （応用数学ではカーディナリティ推定問題とも呼ばれる）は、繰り返し要素を含むデータストリーム中の重複しない要素の数を求める問題です。これは多くの応用分野を持つよく知られた問題です。これらの要素は、ルーターを通過するパケットのIPアドレス、ウェブサイトへのユニークビジター数、大規模データベースの要素、 DNA配列のモチーフ、RFID /センサーネットワークの要素などを表す場合があります。

正式な定義

例: 繰り返しのある要素のストリームを考えます。ストリーム内の異なる要素の数を 、異なる要素の集合を と表します。${\displaystyle x_{1},x_{2},\ldots,x_{s}}$ ${\displaystyle n}$ ${\displaystyle \{e_{1},e_{2},\ldots ,e_{n}\}}$

目的:ストレージユニットのみを使用した場合の推定値を見つけます。${\displaystyle {\widehat {n}}}$ ${\displaystyle n}$ ${\displaystyle m}$ ${\displaystyle m\ll n}$

カーディナリティ推定問題のインスタンスの一例は、ストリーム です: 。このインスタンスでは、 です。 ${\displaystyle a,b,a,c,d,b,d}$ ${\displaystyle n=|\left\{{a,b,c,d}\right\}|=4}$

素朴な解決策

この問題の単純な解決法は次のとおりです。

カウンタcをゼロに初期化します。ハッシュテーブルや検索木など、挿入とメンバーシップを高速に実行できる  
 
 効率的な辞書データ構造Dを初期化します。各要素 に対して、メンバーシップクエリが発行されます。 
     が Dのメンバーでない場合は( )をDに追加し、 c を1
         増やします。
     そうでない場合は( )何も行いません。
 出力。${\displaystyle c\leftarrow 0}$ ${\displaystyle x_{i}}$ ${\displaystyle x_{i}}$  ${\displaystyle x_{i}\notin D}$ 
         ${\displaystyle x_{i}}$ ${\displaystyle c\leftarrow c+1}$ ${\displaystyle x_{i}\in D}$ ${\displaystyle n=c}$ 

異なる要素の数がそれほど多くない限り、Dはメインメモリに収まり、正確な答えを取得できます。しかし、このアプローチは、限られたストレージ容量や、各要素に対して実行される計算を最小限に抑える必要がある場合にはスケールしません。このような場合に備えて、固定数のストレージユニットを使用するストリーミングアルゴリズムがいくつか提案されています。 ${\displaystyle x_{i}}$

HyperLogLogアルゴリズム

ストリーミングアルゴリズム

ストレージの制限に対処するため、ストリーミングアルゴリズムはランダム化を用いて、要素の個数（ ）の非正確な推定値を生成します。最先端の推定器は、ハッシュ関数（ ）を用いて各要素を低次元のデータスケッチにハッシュします。これらの手法は、保存するデータスケッチの種類によって分類できます。 ${\displaystyle n}$ ${\displaystyle e_{j}}$ ${\displaystyle h(e_{j})}$

最小/最大スケッチ

最小/最大スケッチ^{[2] [3]}は、最小/最大のハッシュ値のみを保存します。既知の最小/最大スケッチ推定量の例として、Chassaingら^{[4]は、この問題に対する}最小分散不偏推定量である最大スケッチを提示しています。連続最大スケッチ推定量^[5]は、最大尤度推定量です。実際には、HyperLogLogアルゴリズム^[6]が推定量として選択されます。

このような推定量の背後にある直感は、各スケッチが所望の量に関する情報を持っているというものです。例えば、すべての要素が一様RV ,に関連付けられている場合、 の期待最小値は です。ハッシュ関数は、のすべての出現において が同一であることを保証します。したがって、重複の存在は、極値順序統計量の値に影響を与えません。 ${\displaystyle e_{j}}$ ${\displaystyle h(e_{j})\sim U(0,1)}$ ${\displaystyle h(e_{1}),h(e_{2}),\ldots ,h(e_{n})}$ ${\displaystyle 1/(n+1)}$ ${\displaystyle h(e_{j})}$ ${\displaystyle e_{j}}$

最小/最大スケッチ以外にも推定手法は存在します。カウント・ディスティンクト推定に関する最初の論文^{[7]では、ビットパターンスケッチである}フラジョレ・マーティンアルゴリズムが説明されています。この場合、要素はビットベクトルにハッシュされ、スケッチはハッシュされたすべての値の論理和を保持します。この問題に対する最初の漸近的に空間的および時間的に最適なアルゴリズムは、ダニエル・M・ケイン、ジェラーニ・ネルソン、そしてデビッド・P・ウッドラフによって提示されました^[8]。

底-メートルスケッチ

ボトムmスケッチ ^[9] は最小スケッチの一般化であり、最小値を維持する。カウント・ディスティンクト推定アルゴリズムの理論的概要については Cosma et al. ^[2]を、 比較シミュレーション結果を含む実践的概要については Metwally ^{[10]を参照されたい。}${\displaystyle m}$ ${\displaystyle m\geq 1}$

KnuthのCVMアルゴリズムのPython実装

定義algorithm_d (ストリーム, s : int ):   
    p  =  1.0
    バッファ =  {}
     イン ストリームの 場合:
         バッファ 内 の場合:
            バッファ. pop ( a )
        u  = 一様( 0 ,  1 )
         u  <  pの場合:
             len (バッファ)  <  sの場合:
                バッファ[ a ]  =  u
            それ以外：
                a_p ,  u_p  =  max ( buffer . items (),  key = lambda  x :  x [ 1 ])
                 u  >  u_p の場合:
                    p  =  u
                それ以外：
                    バッファ.ポップ( a_p )
                    バッファ[ a ]  =  u
                    p  =  u_p
     len (バッファ)  /  pを返す

CVMアルゴリズム

カウント・ディスティンクト問題に対する他の近似アルゴリズムと比較して、CVMアルゴリズム^[11]（ドナルド・クヌースが、スーラフ・チャクラボルティ、NV・ヴィノドチャンドラン、クルディープ・S・ミールの頭文字にちなんで命名）は、ハッシュ法ではなくサンプリング法を用いる。CVMアルゴリズムは、標準的な(ε-δ)保証に加えて、ストリーム内の異なる要素の数について不偏推定値を提供する^[12]。以下は、ドナルド・クヌースによる若干の修正を加えたCVMアルゴリズムである^{[12] 。}

 ${\displaystyle p\leftarrow 1}$ 
 最大バッファサイズを初期化します。ここで、
 空のバッファBを初期化します。サイズのデータ​​ストリームの各要素に対して、次の操作を実行します。 
   がBにある場合は、Bからランダムな数値を削除します。がB にある場合は、Bに
           挿入します。${\displaystyle s}$ ${\displaystyle s\geq 1}$   
 ${\displaystyle a_{t}}$ ${\displaystyle A}$ ${\displaystyle n}$ ${\displaystyle (a_{t},u),\forall u}$ 
       ${\displaystyle (a_{t},u)}$ 
   ${\displaystyle u\leftarrow }$ ${\displaystyle [0,1)}$ 
   ${\displaystyle u<p}$ 
       ${\displaystyle |B|<s}$ ${\displaystyle (a_{t},u)}$ 
       それ以外
           ${\displaystyle (a',u')}$ /*がBで最大となる*/${\displaystyle u'=\max\{u'':(a'',u'')\in B,\forall a''\}}$ ${\displaystyle (a',u')}$ ${\displaystyle u'}$ 
           もしそうなら
               ${\displaystyle u>u'}$ ${\displaystyle p\leftarrow u}$ 
           それ以外End For returnに
               置き換えます。${\displaystyle (a',u')}$ ${\displaystyle (a_{t},u)}$ 
               ${\displaystyle p\leftarrow u'}$ 
 
 ${\displaystyle |B|/p}$ 

CVMアルゴリズムの以前のバージョンは、ドナルド・クヌースによる以下の変更によって改良されており、Bが確実に減少するようにwhileループが追加されています。 ^[12]

 初期化${\displaystyle p\leftarrow 1}$ 
 最大バッファサイズを初期化します。ここで、
 空のバッファBを初期化します。サイズのデータ​​ ストリーム内の各要素に対して、次の操作を実行します。 
   がBにある場合は、 Bからランダムな数値を削除します。Ifの場合は、 Bに
       挿入します。Whileの場合は、Bの
       すべての要素を削除します。End Whileの
   場合は、${\displaystyle s}$ ${\displaystyle s\geq 1}$   
 ${\displaystyle a_{t}}$ ${\displaystyle A}$ ${\displaystyle n}$ ${\displaystyle a_{t}}$ 
       ${\displaystyle a_{t}}$ 
   ${\displaystyle u\leftarrow }$ ${\displaystyle [0,1)}$ 
   ${\displaystyle u\leq p}$ ${\displaystyle (a_{t},u)}$ 
   ${\displaystyle |B|=s\wedge u<p}$ ${\displaystyle (a',u')}$ ${\displaystyle u'>{\frac {p}{2}}}$ 
       ${\displaystyle p\leftarrow {\frac {p}{2}}}$ 
   ${\displaystyle u<p}$ 戻り値としてB Endに
       挿入します。${\displaystyle (a_{t},u)}$ 
 
 ${\displaystyle |B|/p}$ 

重み付きカウント・ディスティンクト問題

重み付け版では、各要素に重みが関連付けられており、重みの合計を推定することが目的です。正式には、

インスタンス: 繰り返しのある重み付き要素のストリームと整数。を異なる要素の数、つまり とし、これらの要素を とします。最後に、を の重みとします。${\displaystyle x_{1},x_{2},\ldots ,x_{s}}$ ${\displaystyle m}$ ${\displaystyle n}$ ${\displaystyle n=|\left\{{x_{1},x_{2},\ldots ,x_{s}}\right\}|}$ ${\displaystyle \left\{{e_{1},e_{2},\ldots ,e_{n}}\right\}}$ ${\displaystyle w_{j}}$ ${\displaystyle e_{j}}$

目的:ストレージユニットのみを使用した場合の推定値を見つけます。${\displaystyle {\widehat {w}}}$ ${\displaystyle w=\sum _{j=1}^{n}w_{j}}$ ${\displaystyle m}$ ${\displaystyle m\ll n}$

重み付き問題のインスタンスの例は次のとおりです。このインスタンスでは、重みはおよびです。 ${\displaystyle a(3),b(4),a(3),c(2),d(3),b(4),d(3)}$ ${\displaystyle e_{1}=a,e_{2}=b,e_{3}=c,e_{4}=d}$ ${\displaystyle w_{1}=3,w_{2}=4,w_{3}=2,w_{4}=3}$ ${\displaystyle \sum {w_{j}}=12}$

応用例として、サーバーが受信したIPパケットが挙げられます。各パケットはいずれかのIPフローに属します。重みは、フローがサーバーに課す負荷を表します。つまり、重みは、パケットが属するすべてのフローがサーバーに課す負荷の合計を表します。 ${\displaystyle x_{1},x_{2},\ldots ,x_{s}}$ ${\displaystyle n}$ ${\displaystyle e_{1},e_{2},\ldots ,e_{n}}$ ${\displaystyle w_{j}}$ ${\displaystyle e_{j}}$ ${\displaystyle \sum _{j=1}^{n}{w_{j}}}$ ${\displaystyle x_{1},x_{2},\ldots ,x_{s}}$

重み付きカウント・ディスティンクト問題を解く

重み付けなし問題に対する任意の極値順序統計量推定量（最小/最大スケッチ）は、重み付け問題に対する推定量に一般化できます。^[13] 例えば、Cohenら^[5]が提案した重み付け推定量は、連続最大スケッチ推定量を重み付け問題を解くように拡張することで得られます。特に、HyperLogLogアルゴリズム^[6]は重み付け問題を解くように拡張できます。拡張されたHyperLogLogアルゴリズムは、重み付け問題に対する他の既知のアルゴリズムの中で、統計精度とメモリ使用量の点で最高の性能を提供します。

参照

• カウント・ミニマムスケッチ
• ストリーミングアルゴリズム
• 最大尤度
• 最小分散不偏推定量

参考文献

1. ジェフ・ウルマン;ラジャラマン、アナンド。レスコヴェツ、ジュレ。 「マイニング データ ストリーム」(PDF)。 {{cite journal}}:ジャーナルを引用するには|journal=（ヘルプ）が必要です
2. Cosma, Ioana A.; Clifford, Peter (2011). 「確率的計数アルゴリズムの統計分析」. Scandinavian Journal of Statistics . arXiv : 0801.3552 .
3. ジロワール, フレデリック; フージー, エリック (2007). 2007 Proceedings of the Fourth Workshop on Analytic Algorithmics and Combinatorics (ANALCO) . pp.  223– 231. CiteSeerX 10.1.1.214.270 . doi :10.1137/1.9781611972979.9. ISBN  978-1-61197-297-9。
4. Chassaing, Philippe; Gerin, Lucas (2006). 「大規模データセットのカーディナリティの効率的な推定」.第4回数学・コンピュータサイエンスコロキウム講演論文集. arXiv : math/0701347 . Bibcode :2007math......1347C.
5. Cohen, Edith (1997). 「推移的閉包と到達可能性への応用を伴うサイズ推定フレームワーク」J. Comput. Syst. Sci . 55 (3): 441– 453. doi : 10.1006/jcss.1997.1534 .
6. フィリップ・フラジョレ、エリック・フュジー、オリヴィエ・ガンドゥエ、フレデリック・ムニエ (2007). 「HyperLoglog: 近似最適カーディナリティ推定アルゴリズムの分析」(PDF) .アルゴリズム分析.
7. Flajolet, Philippe ; Martin, G. Nigel (1985). 「データベースアプリケーションのための確率的計数アルゴリズム」(PDF) . J. Comput. Syst. Sci . 31 (2): 182– 209. doi :10.1016/0022-0000(85)90041-8.
8. Kane, Daniel M. ; Nelson, Jelani ; Woodruff, David P. (2010). 「個別要素問題に対する最適アルゴリズム」.第29回ACM SIGMOD-SIGACT-SIGARTシンポジウム「データベースシステムの原理」の議事録. pp.  41– 52. doi :10.1145/1807085.1807094. ISBN 978-1-4503-0033-9。
9. Cohen, Edith ; Kaplan, Haim (2008). 「ボトムkスケッチを用いたより厳密な推定」(PDF) . PVLDB .
10. Metwally, Ahmed; Agrawal, Divyakant; Abbadi, Amr El (2008), 「線形化できるのに対数化が必要なのはなぜか？：検索トラフィックの効果的な個別カウントに向けて」、データベース技術の拡張に関する第11回国際会議議事録：データベース技術の進歩、pp.  618– 629、CiteSeerX 10.1.1.377.4771 
11. チャクラボルティ、スーラフ;ネバダ州ヴィノドチャンドラン;ミール、クルディープ S. (2022)。ストリーム内の個別の要素: (テキスト) ブックのアルゴリズム。ライプニッツ国際情報学会議 (LIPIcs)。 Vol. 244. ダグシュトゥール城 – Leibniz-Zentrum für Informatik。ページ 6 ページ、727571 バイト。arXiv : 2301.10191。土井：10.4230/LIPIcs.ESA.2022.34。ISBN 978-3-95977-247-1. ISSN  1868-8969。
12. Knuth, Donald (2023年5月). 「ストリーム内の個別要素を推定するためのCVMアルゴリズム」(PDF) . {{cite journal}}:ジャーナルを引用するには|journal=（ヘルプ）が必要です
13. Cohen, Reuven ; Katzir, Liran ; Yehezkel, Aviv (2014). 「基数推定量を総和集約に一般化するための統一スキーム」. Information Processing Letters . 115 (2): 336– 342. doi :10.1016/j.ipl.2014.10.009.