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

コンピュータサイエンスにおいて、ストリーミングアルゴリズムは入力データストリームを項目のシーケンスとして処理し、通常はデータに対して1回（または数回）の処理を行います。これらのアルゴリズムは、一般的にストリームのサイズやストリーム内の最大値に対して対数的なメモリ制限があり、項目ごとの処理時間も制限されている場合があります。

こうした制約の結果、ストリーミングアルゴリズムは、データストリームの要約または「概略」に基づいて近似的な回答を生成することが多い。

歴史

ストリーミングアルゴリズムは、1978年にはすでにMunroとPaterson ^{[ 1 ]}によって、また1982/83年にはPhilippe FlajoletとG. Nigel Martin ^{[ 2 ]}によって研究されていましたが、ストリーミングアルゴリズムの分野が初めて形式化され普及したのは、1996年にNoga Alon、Yossi Matias、Mario Szegedyによる論文でした^{[ 3 ]}。この論文により、著者らは後に「ストリーミングアルゴリズムへの基礎的な貢献」で2005年にゲーデル賞を受賞しました。それ以来、理論、データベース、ネットワーク、自然言語処理など、コンピュータサイエンスのさまざまな分野にわたるデータストリーミングアルゴリズムを中心とした膨大な研究が行われてきました。

セミストリーミングアルゴリズムは、グラフのストリーミングアルゴリズムの緩和として2005年に導入されました^{[ 4 ]。}このアルゴリズムでは、許容される空間は頂点数nに対して線形ですが、エッジ数mに対しては対数的です。この緩和は密なグラフに対しても依然として意味があり、ストリーミングアルゴリズムでは解決できない興味深い問題（接続性など）を解決できます。 $o(n)$ 空間。

モデル

データストリームモデル

データストリームモデルでは、入力の一部または全部が、（ある有限ドメインからの）整数の有限シーケンスとして表現され、これは一般的にランダムアクセスには利用できず、代わりに「ストリーム」として一度に1つずつ到着します。^{[ 5 ]}ストリームの長さがnでドメインのサイズがmの場合、アルゴリズムは一般的にmとnの対数的な空間を使用するように制約されます。一般的に、ストリームに対して小さな定数回数しかパスを実行できず、場合によっては1回しか実行できません。^[⁶^]

回転式改札機とレジのモデル

ストリーミングに関する文献の多くは、保存するには大きすぎる頻度分布の統計を計算することに関係している。この種の問題には、ベクトルが存在する。 $\mathbf {a} =(a_{1},\dots ,a_{n})$ （ゼロベクトルに初期化） $\displaystyle \mathbf {0} }$ ストリームで更新が提示される）これらのアルゴリズムの目標は、関数を計算することです。 $\mathbf {a}$ 表現するのに必要なスペースよりもかなり少ないスペースを使用する $\mathbf {a}$ まさにその通りです。このようなストリームを更新するための一般的なモデルは2つあり、「レジ」モデルと「回転式改札機」モデルと呼ばれています。^{[ 7 ]}

レジモデルでは、各更新は次の形式になります。 $\langle i,c\rangle$ 、となることによって $a_{i}$ 正の整数だけ増加します $c$ 注目すべき特別なケースは、 $c=1$ （ユニットの挿入のみが許可されます。）

ターンスタイルモデルでは、各更新は次の形式になります。 $\langle i,c\rangle$ 、となることによって $a_{i}$ （負の場合もある）整数だけ増加する $c$ 「厳密な回転式改札機」モデルでは、 $a_{i}$ いつでもゼロ未満になる可能性がある。

スライド式窓モデル

いくつかの論文では、「スライディングウィンドウ」モデルについても検討している。このモデルでは、対象となる関数は、ストリーム内の固定サイズのウィンドウ上で計算される。ストリームが進むにつれて、ウィンドウの末尾にある項目は考慮対象から除外され、ストリームからの新しい項目がその場所に配置される。

上記のような頻度に基づく問題以外にも、他のタイプの問題も研究されてきました。グラフの隣接行列や隣接リストが未知の順序でストリームされる設定では、多くのグラフ問題が解決されています。また、ストリームの順序に大きく依存する問題（非対称関数など）もあり、例えば、ストリーム内の反転の数を数えたり、最長増加部分列を見つけたりといった問題が挙げられます。

評価

データストリーム上で動作するアルゴリズムのパフォーマンスは、次の3つの基本的な要素によって測定されます。^{[ 8 ]}

アルゴリズムがストリームに対して行う必要がある処理回数。
利用可能なメモリ。
アルゴリズムの実行時間。

これらのアルゴリズムは、すべてのデータが揃う前に意思決定を行う必要があるという点で、オンラインアルゴリズムと多くの類似点がありますが、全く同じではありません。データストリームアルゴリズムは利用可能なメモリが限られていますが、一連のデータが到着するまで処理を延期できる場合があります。一方、オンラインアルゴリズムは、各データが到着するたびにすぐに処理を実行する必要があります。

アルゴリズムが近似アルゴリズムである場合、答えの精度も重要な要素です。精度はしばしば次のように表されます。 $(\epsilon ,\delta )$ 近似とは、アルゴリズムが以下の誤差を達成することを意味する。 $\epsilon$ 確率で $1-\delta$ 。

アプリケーション

ストリーミングアルゴリズムは、ネットワークリンクのエレファントフローの監視、異なるフローの数のカウント、フローサイズの分布の推定など、ネットワークにおいていくつかの用途があります。 ^[⁹^]また、データベースにおいても、結合のサイズの推定などの用途があります。

ストリーミングに問題が発生する場合があります

周波数モーメント

周波数の集合のk番目の周波数 $モーメント$ $\mathbf {a}$ は次のように定義される。 $F_{k}(\mathbf {a} )=\sum _{i=1}^{n}a_{i}^{k}$ 。

最初の瞬間 $F_{1}$ は単に頻度の合計（つまり、総数）です。 $F_{2}$ これは、ジニ係数などのデータの統計的特性を計算するのに役立ちます。 $F_{\infty }$ は、最も頻繁に出現する項目の頻度として定義されます。

アロン、マティアス、セゲディによる画期的な論文は、周波数モーメントの推定という問題を取り扱っていた。

周波数モーメントの計算

周波数モーメントを直接求めるには、すべての異なる要素 $a$ $i$ $\in (1,2,3,4,...,$ $N$ $)に対してレジスタ$ $m i$ を維持する必要があり、そのためには少なくともオーダーのメモリが必要となります。 $\Omega (N)$ ^{[ 3 ]}しかし、スペースに制限があるため、はるかに少ないメモリで計算するアルゴリズムが必要です。これは、正確な値の代わりに近似値を使用することで実現できます。F $k$ の( ε,δ ) 近似値を計算するアルゴリズム。ここで、 $F$ $' k$ $はF$ $k$ の( ε,δ ) 近似値です。^[¹⁰^]ここで、εは近似パラメータ、δは信頼度パラメータです。^[¹¹^]

F ₀（データストリーム内の異なる要素）の計算

FMスケッチアルゴリズム

Flajolet らは^{[ 2 ]}で、 Robert Morrisの論文^{[ 12 ]}に触発された確率的計数法を導入した。Morrisは論文の中で、精度の要件を放棄すれば、カウンタn をlog $log n$ のカウンタに置き換えることができ、 $log log n$ ビットに格納できると述べている。^{[ 13 ]} Flajolet らは^{[ 2 ]} $で、ハッシュ空間 (長さL$ のバイナリ文字列) に要素を均一に分布させると想定されるハッシュ関数 $h$ を使用することで、この方法を改良した。

h:[m]\rightarrow [0,2^{L}-1]

$bit(y,k)$ は $y$ の二進数表現におけるk番目のビットを表すものとする。

y=\sum _{k\geq 0}\mathrm {bit} (y,k)*2^{k}

させて $\rho (y)$ は、適切な規則に従って、 $y i$ のバイナリ表現における最下位 1 ビットの位置を表します。 $\rho (0)$ 。

\rho (y)={\begin{cases}\mathrm {Min} (k:\mathrm {bit} (y,k)==1)&{\text{if }}y>0\\L&{\text{if }}y=0\end{cases}}

A を長さMのデータストリームのシーケンスとし、そのカーディナリティを決定する必要があるとする。BITMAP [0... L − 1]を

$ρ$ （ハッシュ値）が記録されるハッシュ空間。次に、以下のアルゴリズムによってAのおおよその濃度が決定されます。

手順 FM-Sketch: i が 0 から L − 1 までの場合、 BITMAP[i] := 0 終了 for x in A: を実行する インデックス := ρ(hash(x)) BITMAP[index] = 0 の場合 BITMAP[index] := 1 endif 終了 B := BITMAP[] の左端の 0 ビットの位置 2 ^ B を返す

データストリームにN個の異なる要素がある場合。

のために $i\gg \log(N)$ すると、BITMAP [ i ]は確かに0になります。
のために $i\ll \log(N)$ すると、BITMAP [ i ] は確かに 1 になります。
のために $i\approx \log(N)$ すると、BITMAP [ i ] は 0 と 1 の境界になります

K最小値アルゴリズム

前述のアルゴリズムは、FlajoletとMartinによるデータストリームにおけるF0_を近似する最初の試みについて説明したものである。彼らのアルゴリズムは、ハッシュ空間内でハッシュ値を均一に分布させると仮定したランダムなハッシュ関数を選択する。

Bar-Yossef らは^{[ 11 ]}で、データストリーム内の異なる要素の数を決定するための k 最小値アルゴリズムを導入しました。彼らは、[0,1] に正規化できる同様のハッシュ関数hを使用しました。 $h:[m]\rightarrow [0,1]$ しかし、ハッシュ空間内の値の数に制限tが設けられた。tの値は次のオーダーであると想定される。 $O\left({\dfrac {1}{\varepsilon _{2}}}\right)$ （つまり、近似値εが小さいほどtが多く必要になります）。KMVアルゴリズムは、ハッシュ空間にt最小のハッシュ値のみを保持します。ストリームのm個の値がすべて到着した後、 $\upsilon =\mathrm {Max} (h(a_{i}))$ 計算に使用されます $F'_{0}={\dfrac {t}{\upsilon }}$ つまり、ほぼ均一なハッシュ空間では、少なくともt個の要素が以下であると予想されます。 $O\left({\dfrac {t}{F_{0}}}\right)$ 。

手順2：K最小値 KMVの最初のt値を初期化する a1 の a に対して、 h(a) < Max(KMV) の場合 KMVセットからMax(KMV)を削除します KMVにh(a)を挿入する endif 終了 return t/Max(KMV)

KMVの複雑性分析

KMVアルゴリズムは以下のように実装できます。 $O\left(\left({\dfrac {1}{\varepsilon _{2}}}\right)\cdot \log(m)\right)$ メモリビット空間。各ハッシュ値にはオーダーの空間が必要です。 $O(\log(m))$ メモリビット。ハッシュ値は次のオーダーです。 $O\left({\dfrac {1}{\varepsilon _{2}}}\right)$ t個のハッシュ値をバイナリツリーに格納すれば、アクセス時間を短縮できます。したがって、時間計算量は次のように削減されます。 $O\left(\log \left({\dfrac {1}{\varepsilon }}\right)\cdot \log(m)\right)$ 。

$F$ $k$ の計算

Alonらは、与えられた空間と時間内で計算できる確率変数を定義することによって $F kを推定する。$ ^{[ 3 ]}確率変数の期待値は $F k$ の近似値を与える。

数列の長さmは既知であると仮定します。次に、次のように確率変数Xを構築します。

$p$ $を$ 、インデックス $pを持つシーケンス$ $A$ のランダムな要素として選択します。 $a_{p}=l\in (1,2,3,\ldots ,n)$
させて $r=|\{q:q\geq p,a_{q}=l\}|$ $は、p$ $に$ 続くシーケンス $A$ のメンバー内で $l$ が出現する回数を表します。
確率変数 $X=m(r^{k}-(r-1)^{k})$ 。

S _{1 が}次のオーダーであると仮定します。 $O(n^{1-1/k}/\lambda ^{2})$ そしてS2_はオーダーである $O(\log(1/\バレプシロン ))$ アルゴリズムはS2_個のランダム変数を取ります $Y_{1},Y_{2},...,Y_{S2}$ そして中央値を出力する $Y$ 。ここで $Y i は$ $X ij$ の平均であり、1 ≤ j ≤ S ₁である。

次に、確率変数 $E (X)$ の期待値を計算します。

{\begin{array}{lll}E(X)&=&\sum _{i=1}^{n}\sum _{i=1}^{m_{i}}(j^{k}-(j-1)^{k})\\&=&{\frac {m}{m}}[(1^{k}+(2^{k}-1^{k})+\ldots +(m_{1}^{k}-(m_{1}-1)^{k}))\\&&\;+\;(1^{k}+(2^{k}-1^{k})+\ldots +(m_{2}^{k}-(m_{2}-1)^{k}))+\ldots \\&&\;+\;(1^{k}+(2^{k}-1^{k})+\ldots +(m_{n}^{k}-(m_{n}-1)^{k}))]\\&=&\sum _{i=1}^{n}m_{i}^{k}=F_{k}\end{array}}

$F$ $k$ の複雑さ

$上記で説明したF k を$ 計算するアルゴリズムから、各乱数変数 $X は$ $a p$ と $r$ の値を格納することがわかります。したがって、 $Xを計算するには、$ $a$ $p$ $を格納するためにlog(n)$ ビット、 $r$ を格納するために $log($ $n$ $)$ ビットのみを保持する必要があります。乱数変数 $X$ の総数は⁠ $S_{1}*S_{2}$ ⁠ .

したがって、アルゴリズムが必要とする全体の空間計算量は次のオーダーである。 $O\left({\dfrac {k\log {1 \over \varepsilon }}{\lambda ^{2}}}n^{1-{1 \over k}}\left(\log n+\log m\right)\right)$

$F2$ $を$ 計算するためのより簡単な方法

前述のアルゴリズムは、 $F_{2}$ の順に $O({\sqrt {n}}(\log m+\log n))$ メモリビット。Alon らは^{[ 3 ]}で、値をマッピングした 4 つ独立な乱数を使用してこのアルゴリズムを簡略化しました。 $\{-1,1\}$ 。

これにより計算の複雑さがさらに軽減されます $F_{2}$ に $O\left({\dfrac {\log {1 \over \varepsilon }}{\lambda ^{2}}}\left(\log n+\log m\right)\right)$

頻繁に登場する要素

データストリームモデルにおいて、頻出要素問題とは、ストリームの一定割合以上を占める要素のセットを出力することです。その特殊なケースとして、多数決問題があります。これは、ある値がストリームの過半数を占めるかどうかを判定する問題です。

より厳密には、1より大きい正の定数cを固定し、ストリームの長さをmとし、f _iをストリーム内の値iの頻度とします。頻出要素問題は、 { i | f _i > m/c }の集合を出力することです。 ^[¹⁴^]

注目すべきアルゴリズムには以下のようなものがある。

イベント検出

データストリーム内のイベントの検出は、上記に挙げたような強力なアルゴリズムを使用して行われることが多い。これらのアルゴリズムのいずれかを使用して最も頻繁に出現する項目とその頻度が決定され、前の時点からの最大の増加がトレンドとして報告される。このアプローチは、指数加重移動平均と分散を正規化に使用することで改良できる。^{[ 15 ]}

異なる要素を数える

ストリーム内の異なる要素の数を数えること（ $F 0$ モーメントと呼ばれることもあります）は、よく研究されているもう 1 つの問題です。最初のアルゴリズムは Flajolet と Martin によって提案されました。2010 年にDaniel Kane、Jelani Nelson、David Woodruff は、この問題に対する漸近的に最適なアルゴリズムを発見しました。^{[ 16 ]} $このアルゴリズムはO (ε 2 + log d)$ の空間を使用し、最悪の場合の更新と報告時間は $O (1)$ で、ユニバーサルハッシュ関数と $r$ 個の独立したハッシュファミリーを使用します。ここで $r = Ω(log(1/ ε) / log log(1/ ε)) です$ 。

エントロピ

周波数の集合の（経験的）エントロピー $\mathbf {a}$ は次のように定義される。 $F_{k}(\mathbf {a} )=\sum _{i=1}^{n}{\frac {a_{i}}{m}}\log {\frac {a_{i}}{m}}$ 、どこ $m=\sum _{i=1}^{n}a_{i}$ 。

オンライン学習

訓練データセットを一度だけ処理することで、モデル（例えば分類器）を学習する。

下限値

これまで研究されてきた多くのデータストリーミング問題について、下限値が算出されている。これらの下限値を算出する最も一般的な手法は、通信複雑度を用いることである。

注記

↑Munro, J. Ian; Paterson, Mike (1978). "Selection and Sorting with Limited Storage". 19th Annual Symposium on Foundations of Computer Science, Ann Arbor, Michigan, USA, 16–18 October 1978. IEEE Computer Society. pp. 253–258. doi:10.1109/SFCS.1978.32.
123Flajolet & Martin (1985)
1234Alon, Matias & Szegedy (1996)
↑Feigenbaum, Joan; Sampath, Kannan (2005). "On graph problems in a semi-streaming model". Theoretical Computer Science. 348 (2): 207–216. doi:10.1016/j.tcs.2005.09.013.
↑Babcock, Brian; Babu, Shivnath; Datar, Mayur; Motwani, Rajeev; Widom, Jennifer (2002). "Models and issues in data stream systems". Proceedings of the twenty-first ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems. PODS '02. New York, NY, USA: ACM. pp. 1–16. CiteSeerX 10.1.1.138.190. doi:10.1145/543613.543615. ISBN 978-1-58113-507-7. S2CID 2071130.
↑Bar-Yossef, Ziv; Jayram, T. S.; Kumar, Ravi; Sivakumar, D.; Trevisan, Luca (2002-09-13). "Counting Distinct Elements in a Data Stream". Randomization and Approximation Techniques in Computer Science. Lecture Notes in Computer Science. Vol. 2483. Springer, Berlin, Heidelberg. pp. 1–10. CiteSeerX 10.1.1.12.6276. doi:10.1007/3-540-45726-7_1. ISBN 978-3-540-45726-8. S2CID 4684185.
↑Gilbert et al. (2001)
↑Nordahl, Christian; Boeva, Veselka; Grahn, Håkan; Persson-Netz, Marie (2025). "On Evaluation of Data Stream Clustering Algorithms: A Survey". IEEE Access. 13: 139524–139546. doi:10.1109/ACCESS.2025.3596435. ISSN 2169-3536.
↑Xu (2007)
↑ Indyk, Piotr; Woodruff, David (2005-01-01). "データストリームの周波数モーメントの最適近似".第37回ACM理論計算機科学シンポジウム（STOC '05）論文集. ニューヨーク州ニューヨーク市、米国: ACM. pp. 202–208 . doi : 10.1145/1060590.1060621 . ISBN 978-1-58113-960-0. S2CID 7911758 .
1 2 Bar-Yossef, Ziv; Jayram, TS; Kumar, Ravi; Sivakumar, D.; Trevisan, Luca (2002-09-13). Rolim, José DP; Vadhan, Salil (編).データストリーム内の異なる要素のカウント. Lecture Notes in Computer Science. Springer Berlin Heidelberg. pp. 1– 10. CiteSeerX 10.1.1.12.6276 . doi : 10.1007/3-540-45726-7_1 . ISBN 978-3-540-44147-2. S2CID 4684185 .
↑モリス（1978）
↑ Flajolet, Philippe (1985-03-01). "近似計数: 詳細な分析". BIT Numerical Mathematics . 25 (1): 113– 134. CiteSeerX 10.1.1.64.5320 . doi : 10.1007/BF01934993 . ISSN 0006-3835 . S2CID 2809103 .
↑ Cormode, Graham (2014). "Misra-Gries 要約". Kao, Ming-Yang (編).アルゴリズム百科事典. Springer US. pp. 1–5 . doi : 10.1007/978-3-642-27848-8_572-1 . ISBN 978-3-642-27848-8。
↑ Schubert, E.; Weiler, M.; Kriegel, HP (2014). SigniTrend: ハッシュ化された有意性閾値によるテキストストリームにおける新興トピックのスケーラブルな検出. 第20回ACM SIGKDD国際知識発見・データマイニング会議 - KDD '14 論文集. pp. 871–880 . doi : 10.1145/2623330.2623740 . ISBN 978-1-4503-2956-9。
↑ケイン、ネルソン、ウッドラフ（2010）

参考文献

Alon, Noga ; Matias, Yossi ; Szegedy, Mario (1999)、「周波数モーメントの近似における空間複雑性」、Journal of Computer and System Sciences、58 (1): 137–147、doi : 10.1006/jcss.1997.1545、ISSN 0022-0000 初出論文は、Alon, Noga; Matias, Yossi; Szegedy, Mario (1996)、「周波数モーメントの近似における空間複雑性」、第28回ACM理論計算機科学シンポジウム（STOC 1996）論文集、pp. 20–29、CiteSeerX 10.1.1.131.4984、doi : 10.1145/237814.237823、ISBN として出版された。 978-0-89791-785-8S2CID 1627911 。
Babcock, Brian; Babu, Shivnath; Datar, Mayur; Motwani, Rajeev ; Widom, Jennifer (2002)、「データストリームシステムのモデルと課題」、第21回ACM SIGMOD-SIGACT-SIGARTデータベースシステム原理シンポジウム（PODS 2002）議事録（PDF）、pp. 1–16、CiteSeerX 10.1.1.138.190、doi : 10.1145/543613.543615、ISBN 978-1-58113-507-7S2CID 2071130、2017年7月9日にオリジナル（PDF）からアーカイブ、2013年7月15日に取得。
Flajolet, Philippe; Martin, G. Nigel (1985). "データベースアプリケーションのための確率的計数アルゴリズム" (PDF) . Journal of Computer and System Sciences . 31 (2): 182– 209. doi : 10.1016/0022-0000(85)90041-8 . 2016-12-11に取得.
Gilbert, AC ; Kotidis, Y.; Muthukrishnan, S. ; Strauss, MJ (2001)、「ストリーム上のウェーブレットサーフィン：近似集計クエリのためのワンパス要約」（PDF）、国際超大規模データベース会議議事録：79–88。
Kane, Daniel M.; Nelson, Jelani; Woodruff, David P. (2010). 「異なる要素問題に対する最適アルゴリズム」.第29回ACM SIGMOD-SIGACT-SIGARTデータベースシステム原理シンポジウム議事録. PODS '10. ニューヨーク州ニューヨーク、米国: ACM. pp. 41–52 . CiteSeerX 10.1.1.164.142 . doi : 10.1145/1807085.1807094 . ISBN 978-1-4503-0033-9. S2CID 10006932 . 。
Karp, RM ; Papadimitriou, CH ; Shenker, S. (2003)、「ストリームとバッグ内の頻出要素を見つけるためのシンプルなアルゴリズム」、ACM Transactions on Database Systems、28 (1): 51–55、CiteSeerX 10.1.1.116.8530、doi : 10.1145/762471.762473、S2CID 952840 。
Lall, Ashwin; Sekar, Vyas; Ogihara, Mitsunori; Xu, Jun; Zhang, Hui (2006). 「ネットワークトラフィックのエントロピーを推定するためのデータストリーミングアルゴリズム」. Proceedings of the Joint International Conference on Measurement and Modeling of Computer Systems (ACM SIGMETRICS 2006) . p. 145. doi : 10.1145/1140277.1140295 . hdl : 1802/2537 . ISBN 978-1-59593-319-5. S2CID 240982 . 。
Xu, Jun (Jim) (2007)、ネットワークデータストリーミングに関するチュートリアル(PDF)。
Heath, D.、Kasif, S.、Kosaraju, R.、Salzberg, S.、Sullivan, G.、「限られた記憶容量でのネストされた概念の学習」、Proceeding IJCAI'91、第12回国際人工知能合同会議議事録 - 第2巻、777～782ページ、Morgan Kaufmann Publishers Inc.、サンフランシスコ、カリフォルニア州、アメリカ合衆国 ©1991
Morris, Robert (1978)、「小さなレジスタにおける多数のイベントのカウント」、Communications of the ACM、21 (10): 840–842、doi : 10.1145/359619.359627、S2CID 36226357 。

[1] Munro, J. Ian; Paterson, Mike (1978). "Selection and Sorting with Limited Storage". 19th Annual Symposium on Foundations of Computer Science, Ann Arbor, Michigan, USA, 16–18 October 1978. IEEE Computer Society. pp. 253–258. doi:10.1109/SFCS.1978.32.

[:0-2] 123Flajolet & Martin (1985)

[:1-3] 1234Alon, Matias & Szegedy (1996)

[4] Feigenbaum, Joan; Sampath, Kannan (2005). "On graph problems in a semi-streaming model". Theoretical Computer Science. 348 (2): 207–216. doi:10.1016/j.tcs.2005.09.013.

[5] Babcock, Brian; Babu, Shivnath; Datar, Mayur; Motwani, Rajeev; Widom, Jennifer (2002). "Models and issues in data stream systems". Proceedings of the twenty-first ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems. PODS '02. New York, NY, USA: ACM. pp. 1–16. CiteSeerX 10.1.1.138.190. doi:10.1145/543613.543615. ISBN 978-1-58113-507-7. S2CID 2071130.

[6] Bar-Yossef, Ziv; Jayram, T. S.; Kumar, Ravi; Sivakumar, D.; Trevisan, Luca (2002-09-13). "Counting Distinct Elements in a Data Stream". Randomization and Approximation Techniques in Computer Science. Lecture Notes in Computer Science. Vol. 2483. Springer, Berlin, Heidelberg. pp. 1–10. CiteSeerX 10.1.1.12.6276. doi:10.1007/3-540-45726-7_1. ISBN 978-3-540-45726-8. S2CID 4684185.

[turnstile-7] Gilbert et al. (2001)

[8] Nordahl, Christian; Boeva, Veselka; Grahn, Håkan; Persson-Netz, Marie (2025). "On Evaluation of Data Stream Clustering Algorithms: A Survey". IEEE Access. 13: 139524–139546. doi:10.1109/ACCESS.2025.3596435. ISSN 2169-3536.

[9] Xu (2007)

[10] Indyk, Piotr; Woodruff, David (2005-01-01). "データストリームの周波数モーメントの最適近似".第37回ACM理論計算機科学シンポジウム（STOC '05）論文集. ニューヨーク州ニューヨーク市、米国: ACM. pp. 202–208 . doi : 10.1145/1060590.1060621 . ISBN 978-1-58113-960-0. S2CID 7911758 .

[:2-11] 1 2 Bar-Yossef, Ziv; Jayram, TS; Kumar, Ravi; Sivakumar, D.; Trevisan, Luca (2002-09-13). Rolim, José DP; Vadhan, Salil (編).データストリーム内の異なる要素のカウント. Lecture Notes in Computer Science. Springer Berlin Heidelberg. pp. 1– 10. CiteSeerX 10.1.1.12.6276 . doi : 10.1007/3-540-45726-7_1 . ISBN 978-3-540-44147-2. S2CID 4684185 .

[12] モリス（1978）

[13] Flajolet, Philippe (1985-03-01). "近似計数: 詳細な分析". BIT Numerical Mathematics . 25 (1): 113– 134. CiteSeerX 10.1.1.64.5320 . doi : 10.1007/BF01934993 . ISSN 0006-3835 . S2CID 2809103 .

[14] Cormode, Graham (2014). "Misra-Gries 要約". Kao, Ming-Yang (編).アルゴリズム百科事典. Springer US. pp. 1–5 . doi : 10.1007/978-3-642-27848-8_572-1 . ISBN 978-3-642-27848-8。

[15] Schubert, E.; Weiler, M.; Kriegel, HP (2014). SigniTrend: ハッシュ化された有意性閾値によるテキストストリームにおける新興トピックのスケーラブルな検出. 第20回ACM SIGKDD国際知識発見・データマイニング会議 - KDD '14 論文集. pp. 871–880 . doi : 10.1145/2623330.2623740 . ISBN 978-1-4503-2956-9。

[16] ケイン、ネルソン、ウッドラフ（2010）

[ 1 ]

[ 4 ]。

[ 5 ]

[

[ 7 ]

[ 8 ]

[

[

[ 12 ]

[ 13 ]

[

[ 15 ]

[ 16 ]

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

歴史

モデル

データストリームモデル

回転式改札機とレジのモデル

スライド式窓モデル

評価

アプリケーション

ストリーミングに問題が発生する場合があります

周波数モーメント

周波数モーメントの計算

F ₀（データストリーム内の異なる要素）の計算

FMスケッチアルゴリズム

K最小値アルゴリズム

KMVの複雑性分析

$F$ $k$ の計算

$F$ $k$ の複雑さ

$F2$ $を$ 計算するためのより簡単な方法

頻繁に登場する要素

イベント検出

異なる要素を数える

エントロピ

オンライン学習

下限値

関連項目

注記

参考文献

関連するトピック

コンピュータサイエンス

データストリームを

シーケンス

1回（または数回）の処理を行います。これらのアルゴリズムは、一般的にストリームのサイズやストリーム内の最大値に対して

歴史

モデル

データストリームモデル

回転式改札機とレジのモデル

スライド式窓モデル

評価

アプリケーション

ストリーミングに問題が発生する場合があります

周波数モーメント

周波数モーメントの計算

F 0（データストリーム内の異なる要素）の計算

FMスケッチアルゴリズム

K最小値アルゴリズム

KMVの複雑性分析

F kの計算

F kの複雑さ

F2を計算するためのより簡単な方法

頻繁に登場する要素

イベント検出

異なる要素を数える

エントロピ

オンライン学習

下限値

関連項目

注記

参考文献

関連するトピック

コンピュータサイエンス

データストリームを

シーケンス

1回（または数回）の処理を行います。これらのアルゴリズムは、一般的にストリームのサイズやストリーム内の最大値に対して

F ₀（データストリーム内の異なる要素）の計算

$F$ $k$ の計算

$F$ $k$ の複雑さ

$F2$ $を$ 計算するためのより簡単な方法