ランダムサンプリング

論文翻訳: Sampling From a Moving Window Over Streaming Data

Takami Torao 2002年の論文
  • このエントリーをはてなブックマークに追加

Brian Babcock*

Mayur Datar*

Rajeev Motwani

Abstract

直近のアイテムの移動ウィンドウを使用してデータストリームからサンプリングする問題を紹介し、この問題に対する "チェーンサンプリング" (chain sampling) と "優先度サンプリング" (priority sampling) アルゴリズムを開発する。

Table of Contents

  1. Abstract
  2. 1 導入
  3. 2 シーケンスベースのウィンドウ
  4. 3 タイムスタンプベースのウィンドウ
  5. Acknowledgements
  6. References
  7. 翻訳抄
  1. *Dept of Computer Science, Stanford Univ, CA 94305. E-mail: {babcock , datar . stanford.edu

1 導入

多くのアプリケーションではデータの適時性 (timeliness) が重要であり、最新のデータが最も興味深いと考えられている。古いデータは "期限切れ" でありクエリを評価する際にはもはや使用されない。ここでは、データストリームの最新の要素からなる "移動ウィンドウ" 上で指定されたサイズ \(k\) の一様にランダムなサンプルを維持する問題を考える。(ストリーミングデータモデルの概要については [2] を参照。) 我々は移動ウィンドウの 2 つの定義の下でこの問題に対するメモリ効率の良いアルゴリズムを提示する。サイズ \(n\) のシーケンスベースのウィンドウ (sequence-based window) は最近到着した \(n\) 個のデータ要素で構成され、一方で時間 \(t\) のタイムスタンプベースのウィンドウ (timestamp-based window) は到着タイムスタンプが現在時刻から時間間隔 \(t\) 以内の全てのデータ要素で構成される。

オンラインで到着するデータに対して特定のサイズ \(k\) のサンプルをどのように維持するかという問題は過去に研究されてきた。標準液な解決策は [6] で開発された Vitter のリザーバーサンプリング技術を使用することである。リザーバーサンプリングは受信データが挿入と更新のみを行う場合にはうまく機能するが、データの期限切れのように、データの削除を行う場合には困難となる。[3] で使用されている解決策は、データベース全体の高価なスキャンによって、多くの削除が発生したときにサンプルを定期的に再生成する方法である。[4] の削除に対するアプローチはランダムなサンプルを維持しようとするのではなく、確率的なカウントを用いて最も一般的なデータ要素のカウントを維持することである。

2 シーケンスベースのウィンドウ

シーケンスベースの移動ウィンドウを使用したサンプリングアルゴリズムの 1 つは、ストリーム内の最初の \(n\) 個のデータ要素に対してリザーバーにサンプルを維持し、その後に新しいデータ要素の到着によって要素がストリーム内に存在する場合を除いて、サンプルの維持を停止することである。サンプルの有効期限が切れると期限切れの要素は新しく到着した要素に置き換えられる。このアルゴリズムは \(k\) 個のデータ要素を保持するのに十分なメモリしか必要とせず、最後の \(n\) 要素のウィンドウに渡って一様にランダムなサンプルを維持するが、非常に周期性が高いという欠点がある。シーケンス番号 \(i\) のデータ要素がサンプルに含まれている場合、すべての整数 \(c \gt 0\) に対してシーケンス番号 \(i+cn\) のデータ要素も含まれる。この規則性により、この手法は多くのアプリケーションでは受け入れられなくなる。

もう 1 つの単純なアルゴリズムは、各新規データ要素を確率 \(\frac{2ck \log n}{n}\) で "バックサンプル" (backing sample) に追加し、バックサンプルからダウンサンプリングしてサイズ \(k\) のサンプルを生成することである。データ要素が期限切れになるとそれらはバックサンプルから削除される。Chernoff 境界を使った議論によるとバックサンプルのサイズは、確率 \(c'n^{-c}\) を除いて、\(k\) と \(4ck \log n\) の間になることを示している。このアルゴリズムは高い確率でサイズ \(k\) の望ましいサンプルを供給するのに十分な大きさのバックサンプルを保持し、\(O(k \log n)\) のメモリしか使用しない。

以前のアルゴリズムで期待されるメモリ使用量は \(O(k \log n)\) である。我々が "チェーンサンプル" (chain sample) と呼ぶ新しい手法は、\(O(k \log n)\) と同じ高確率の上限を維持しながらこれを \(O(k)\) に改善する。(後述するチェーンサンプルアルゴリズムはサイズ 1 のサンプルを生成する。サイズ \(k\) のサンプルを生成するには \(k\) 個の独立したチェーンサンプルを維持する。)

"チェーンサンプル" アルゴリズムでは、\(i\) 番目の要素が到着するとそれが確率 \({\rm Min}(i,n)/n\) でサンプルになるように選択される。\(i\) 番目の要素がサンプルとして選択された場合、アルゴリズムは、その要素が期限切れになったときに置き換わる要素のインデックスも選択する (その要素が期限切れになったときまだサンプルに存在すると仮定する)。このインデックスは範囲 \(i+1\ldots i+n\) から一様にランダムに選択され、\(i\) 番目の要素が期限切れになったときにアクティブになる要素のインデックスの範囲を表す。選択されたインデックスを持つ要素が到着すると、アルゴリズムはそれをメモリに保存し、その期限が切れたときにそれを置き換える要素のインデックスを選択する。これによりサンプル内の現在の要素の有効期限が切れたときに使用する要素のチェーンが構築される。

サンプル内の要素が期限切れでなく \(i\) 番目に古い要素である場合の要素のチェーンの期待される長さは、\(T[n] \le e\) によって期待される長さを制限する再帰: \[ \begin{eqnarray*} T[1] & = & 1 \\ T[i+1] & = & 1 + \frac{1}{n} \sum_{j=1}^i T[j] \end{eqnarray*} \] で与えられる。

また単一チェーンのメモリ使用量について \(O(\log n)\) の高確率上限を導き出すこともできる。\(x\) 個以上のデータ要素を持つ可能な要素チェーンの数は、\(x\) で順序づけされた整数部分への \(n\) の分割数、つまり \(\binom{n}{x}\) によって境界が決められる。そのような各チェーンは確率 \(n^{-x}\) を持つため、このようなチェーンが発生する確率は \(\binom{n}{x} n^{-x}\) より小さく、Stirling の近似により \(\left(\frac{e}{x}\right)^x\) より小さくなる。\(x=O(\log n)\) のとき、この確率は定数 \(c\) に対する \(n^{-c}\) より小さい。

3 タイムスタンプベースのウィンドウ

前のセクションで説明した手法は、移動ウィンドウ内のデータ要素数が時間の経過と共に変化する可能性があるためタイムスタンプベースのウィンドウには利用できない。我々はタイムスタンプベースのウィンドウで使用するために "優先度サンプル" (priority sample) と呼ぶアルゴリズムを開発した。各データ要素が到着すると 0 から 1 の間でランダムに選択された優先度が割り当てられる。サンプルに含めるために選択される要素は、優先度が最も高い "アクティブ" (期限切れでない) 要素である。(サイズ \(k\) のサンプルを維持するには、各要素に対して \(k\) 個の優先度 \(p_1\ldots p_k\) を生成し、各 \(i\) に対して最も高い \(p_i\) を持つ要素を選択する。)

メモリに格納する必要があるデータ要素は、タイムスタンプが遅く、かつ優先度が高い要素が存在しないデータ要素のみである。これは、これらの要素のみがサンプルで使用できるためである。この特性を使用するとすべての要素のリンクリストを簡単に維持でき、優先度の降順とタイムスタンプの増加によってリンクリストを並べ換えることができる。

このアルゴリズムによって維持されるリンクリストは、タイムスタンプが完全に順序づけされ、優先度がヒープ順序付けされた "ツリープ" (treap) の右スパインに似ている。したがって [1] の議論により \(n\) 個のアクティブな要素がある場合に期待されるこのリストの長さは \(H(n)\) の \(n\) 番目の調和数である。さらに、調和数に対する Chernoff 束縛 ([5] 参照) を適用すると、アクティブな要素が \(n\) 個ある場合にリストの長さが \(2c \ln n+1\) を超える確率は \(2 (n/e)^{-c} \ln(c/e)\) より小さいことを示している。したがって \(O(k \log n)\) は "優先度サンプル" の期待されるメモリ使用量であると同時にメモリ使用量の高確率の上限でもある。

Acknowledgements

The authors thank Adam Meyerson and Sergey Brin for helpful suggestions.

References

  1. C. R. Aragon and R. G. Seidel. Randomized search trees. In Proc. 30th IEEE FOCS, 1989.
  2. g S. Babu and J. Widom. Continuous queries over data streams. Technical report, Stanford University Database Group, March 2001.
  3. P. B. Gibbons, Y. Matias, and V. Poosala. Fast incremental maintenance of approximate histograms. In Proc. 23rd VLDB, 1997.
  4. Y. Matias, J. S. Vitter, and M. Wang. Dynamic maintenance of wavelet-based histograms. In Proc. 26th VLDB, 2000.
  5. K. Mulmuley. An Introduction through Randomized Algorithms. Prentice Hall, 1993.
  6. J. S. Vitter. Random sampling with a reservoir. ACM Trans. on Math. Software, 11:31-35, 1985.

翻訳抄

データストリームから得られる最近の \(n\) 個のデータからランダムサンプリングを行うために移動ウィンドウを使用した手法を解説する 2002 年の論文。1 つの「現在選択されているサンプル」と複数の「選択されているサンプルまたはその後継者がウィンドウを外れたときにサンプルとして選択される後継者」をチェーン状に保持することで、サイズ \(n\) の移動ウィンドウの中で常に 1 つの要素をサンプリングする。期限切れとはデータがウィンドウから外れるときという意味。

  1. B. Babcock, M. Datar, and M. Rajeev, Sampling from a Moving Window Over Streaming Data. Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 633-634, 2002