数理解析研究所講究録
第 1799 巻 2012 年 159-162

159

2011 年度冬の LA シンポジウム [S3]ストリーム中の頻出アイテム発見に対するO(loglog$N$ ) 領域乱択アルゴリズム
緒方 正虎 *

1

山内 由紀子 *概要

来嶋 秀治 *
ムのシンボル数を頻出アイテム発見は与えられたアイテム集合から，ある割合

山下 雅史 *

ビッとした時の下界，トを示した．Manku ら [5] は lossy counting と呼ばれる別の決定性アルゴリズムを提案した．この手法は$\Omega(|\Sigma|\log(N/|\Sigma|))$$|\Sigma|$$O(\epsilon^{-1}\log\delta^{-1}\log N)$を越える頻度で出現するアイテムを発見する問題である．ユー ビットの記憶領域で動作する近似数え上げアルゴリズムを基にザが与える閾値
に対して，データ長 $N$ のストリーム しており，任意のについての頻度を越えるアから回を越える頻度で出現するアイテムを発見する．2003 イテムを出力する．
$\theta\in(0,1)$$\epsilon\in(0,1)$$(\theta-\epsilon)$$\theta\cdot N$

年に Karp らはこの問題に対して偽陽性を許す $0(\theta^{-1}\log N)$ ビッ

トの決定性オンラインアルゴリズムと，決定性アルゴリズムに単一ストリーム上の確率的手法については Toivonen ら [6] がビットの記憶領域で動作するアルゴリズム$o(\epsilon^{-2}\log\delta^{-1}\log N)$よる頻出アイテム発見の下界を示した．本論文ではこの問題のを提案した．この手法はデータの一様サンプリングを基にしてビットの記憶領ですべての頻出アイテムを乱択する．Manku[5]
記憶領域に着目し，おり，確率$O(\theta^{-2}\log^{2}\theta^{-1}+\log\log N)$$1-\delta$域で動作する，シンプルな乱択アルゴリズムを提案する．提案 らも sticky samPling と呼ばれる別のアルゴリズムを提案して手法は他のビットで動作し，ビットで動作する乱択アルゴリズム，決いる．このアルゴリズムは$0(\log N)$$O(\epsilon^{-1}\log\delta^{-1}\log N)$定性アルゴリズムと比較してメモリのオー-バーフローに対して 確率頑健である，$1-\delta$ですべての頻出アイテムを出力する．両アルゴリズ

ムは到着したアイテムに応じて乱択確率を変更することで頻出アイテムを発見する．しかし，ここで触れたすべてのアルゴリズムは頻出アイテム検知に $O(\log N)$ ビットの記憶領域を要はじめにする．

本論文では未知のデータ長 $N$ に対し近年，スーパーの POS システムやインターネットのパケットモニタリングなど，大規模なデータのストリームを出力する計 loglogN) ビットの記憶領域で動作する頻出アイテム発見アル算機システムが増加している．頻出アイテム発見はこのような ゴリズムを提案する．提案手法は loglogN ビットの記憶領域大規模データ処理の基本的な問題として注目されている．頻出 で到着アイテムの近似数え上げを行う．これは Morris ら [9],$O(\theta^{-2}\log^{2}\theta^{-1}+$

アイテム発見問題は入力されるストリームを $x=(x_{1},x_{2}, \ldots x_{N})$Flajolet[10] らと同様のアイデアに基づいている．提案アルゴとした時，ユーザが与える閾値

リズムは指数近似による頻出アイテムの数え上げと，入力に対$\theta\in(0,1)$に対して，$\theta\cdot N$回以上出現するすべてのアイテムを発見する問題である．ストリーして平均して定数時間での動作が可能である．また，他の乱択ムデータ処理では，アルゴリズムは未知の入カサイズに対してアルゴリズムと比較してメモリオーバーフローに対してロバス正常に動作することが求められる．仮にメモリオーバーフロートである．
が生じると重篤な問題を引き起こしかねないため，動作に要す本論文の構成は次の通りである．第 2 章で問題設定，第 3 章
る記憶領域を慎重に設定する必要がある．でアルゴリズムのアイデアを示す．第 4 章でアルゴリズムの動単一ストリーム上の頻出アイテム発見問題について，これ作の解説と証明を行い，第 5 章で結論を述べる．
までさまざまな研究がなされてきた．Boyer ら [1] は majority
algorithm として知られる $\theta=1/2$ に対する $O(\log N)$ アルゴリズムを与えた．これとは独立に Fischer[2] らも本質的に同様の 2アルゴリズムを与えた．2003 年には Karp ら [4], Demain ら[3]問題$\Sigma$をアイテムの全集合とする．簡単の為， は有限集合で，$\Sigma$が決定性アルゴリズムを提案した．この手法は偽陽性を含む 集合の各要素は$\sigma:=\log|\Sigma|$

頻出アイテム集合を出力するもので，ビットで識別できるとする． の$\Sigma$

ビットの記憶 要素から成る系列 $x=(x_{1}, \ldots, x_{N})$$f(s)\in\{0, \ldots, N\}$に対して，領域で実行されることが知られている．また，Karp らは同時 を 中のアイテムの出現回数とすれば，与えられた定$O(\frac{1}{\theta}\log N)$$x$に厳密な頻出アイテム検知に必要な記憶領域について，アイテ 数
九州大学$\theta\in(0,1)$$s\in\Sigma$に対して，$f(s;x)\geq\theta N$

1604を満たす時， を頻出であるという．
$s$

提案アルゴリズム$\theta\in(0,1)$

3.

$\gamma\in(0,1),$ $\delta\in(0,1)$

タとする．与えられた提案手法のアイデア$\delta$$\theta,$$\gamma,$をユーザの定めるパラメーに対し，提案アルゴリズムがを満たす全てのアイテムを出力し，げ $(s)<N\theta\}$ を満たすアイテムを頻出アイテム集合に含ま$\{s|f(s)\geq N\theta(1-\gamma)\}$仮に，ストリーム$x$のデータ長 $N$ が既知であるならば 頻$\{s$出アイテムの発見は容易である． を近似パラメータとして，ない確率は$1-\delta$ 以上である．以下に $x=(x_{1},x_{2}, \ldots,x_{N})$ の文
それぞれのアイテム ; が到着するたびに確率 $c/N$ で乱択し，字列に対する提案アルゴリズムを示す．提案アルゴリズムは頻
$c$

$x$

すべてのアイテムが入力されたのちに閾値を越えるアイテムを –$\underline{Algorithml}$
pairs of an item, and ansisting of出力すればよい．しかし，実際のアプリケーションを考えれば，データ長 $N$ が既知であるというのは不自然な仮定である．

$K$

未知のデータ長 $N$ に対するアルゴリズム設計のアイデアの一つに，ビットシフトがある．ビットシフトアルゴリズムは入$s$

力されるデータ長を数え上げ，到着アイテム数に応じて乱択確$N$$2^{b}$$\infty$

where uses bits, and $K[s]$ uses bits.
Set: “exponent” $h=0$ .
1. Read . Suppose $X:=S^{*}$ for convenience.
If no more input, then goto 5.
in $K$ :record
2. With probability
in $K$ unless in $K$ , and $K[s^{*}]++$ .
add
If $\sum_{s\in K}K[s]=2^{b}$ , then “flush” :率を指数的に減少させる．この時，一度乱択したアイテムも確率的に捨てられていく．固定サイズの記憶領域で乱択したアイテムを保持できるため，未知の入力長

0. Initialize
number $(s, K[s])$ ,$b$$\sigma$$x_{i}$$2^{-h}$に対して有効なアイ$s^{*}$$s^{*}$

デアだが，解析が困難である．

解析の難しさを除けばビットシフトは良い戦略だと思われる$s^{*}$

Set $h++$For each $s\in K$ ,3-()憶領域が必要となる．読み込んだデータ長に応じて記憶領域を, andwith probability
Choose
確保するインクリメンタルなプログラムを組むことは可能であ$K[s]:=k$
Set
るが，$o(\log N)$ ビットの記憶領域が必要であり，より少ない領域で動くアルゴリズムの方が好ましい． Delete symbol $s\in K$ if $K[s]=0$
4 Goto 1
提案手法の基本的なアイデアはストリームのデータ長 $N$ の(1 $-$satisfying that $K(s)$5. Output every
指数近似である．データ長の指数部のみを近似することによ)$o$ (loglogN) ビットの記憶領域でのアルゴリズム設計が可り，
力$\nwarrow$

ストリームのデータ長の数え上げに $o(\log N)$ ビットの記$3arrow(i)$$(^{K[\epsilon]}k)/2^{K[s]}$$k$$3-(\ddot{u}i)$$\geq$$s$$\gamma/2$

能となった．提案手法は指数近似のデ タ長を用いて，ビット$\theta\sum_{s’\in K}K[s’]$–$=$シフトのアイデアを導入する．アイテム$x_{i}$

を読み込む時，す出アイテム候補の記憶に$(b+\sigma)2^{b}+\lceil lgh\rceil$ビット，その他の決める．一度乱択され，頻出アイテム集合 $K$ に保持されたア

作業領域に $0(lgh)$ ビットを用いる，Step 2 で用いられる確率は，計算機上で確率 1/2 のベルヌーイ試行を 回繰り返す

イテムは瓦が増加するに従い，再度乱択される．この操作はことにより $O(lgh)$ 領域で実現できる．つまり到着したアイテが 2 倍になるごとに，保持“flush” と呼ばれ，提案手法ではされている全アイテムを確率 1/2 で再度乱択する．乱択確率のアルゴリズム中の $Step3-(\ddot{u})$ の”flush” についても同様のアイでに到着したアイテム総数$N_{l}$の指数近似により，乱択確率を$N_{i}$$h$$2^{-h}$ム$x_{i}$

は$h$

回投げたコインがすべて表だった場合に乱択される．

減少と保持するアイテムの更新によって，提案手法はストリーデアを用いている．これらの試行はすべて到着アイテム数を近のムの全アイテムをあたかも同一確率で乱択したかのように動作 似したに従って実行される．ここで $h+b$ はストする．また uflus によりアイテム保持に用いる記憶領域を定 リーム長 $N\geq-2^{b}$ の近似である-ので ,[出はアイるテムのテ出ム
数にとどめ，アルゴリズムのオーバーフローを いでいる．ア現数 $f(s)$ を 似している．ア ゴリズムが ffl カするアイテム$h$$\mathfrak{U}\circ gh\rceil$$h^{}$$\tilde$$\Re$$J\nu$$\grave{:}E$2-h-K.

$\hat$

ルゴリズムの記憶領域はデータ長 $N$ の指数近似のみに依存し，は最大で $1/(\theta(1-\gamma/2))$ 個である．
(loglogN) ビットを必要とする．
定理 41. 任意の定数 $\theta\in(0,1),$ $\gamma\in(0,1),$$O$

次の章でアルゴリズムの擬似コードを示し，その証明を行う．

アルゴリズムは $O(\theta^{-2}\log^{2}(\theta^{-1})+\log\log N)$ ビットで動作し，その記憶領域は $N\gg|\Sigma|\gg 1/\theta$ の条件下でアイテム集合に対して独立である．

$|\Sigma|$$o-$

る．パラメータ$\delta\in(0,1)$を与え2))\rceil+3$を $b\geq\lceil lg((\theta\gamma/2)^{-}\ln(3((1-\gamma/2)\theta\delta)$-1$$b$とした時，任意のストリームに対して提案アルゴリズムがすべての頻出アイテムを出力し，かつ，$f(s)<(1-\gamma)\cdot\theta N$ を満た$s$

す頻出でないアイテム$s\in\Sigma$を出力しない確率は$1-\delta$である．

定理 41 はアルゴリズムが以下の記憶領域を必要とすることを示している．

161
上の考察 42 を用いることによって次の補題を導く．
$2^{b}(b+\sigma)+1glgN$

補題 42. パラメータ$o( \frac{\log^{2}(\theta^{-1})}{\theta^{2}}+\log\log N)$$=$

証明の簡便さのため

ビット．発見する確率はは最適化されていないことを断っておく． 証明．

$s\in\Sigma$

$b$

$b$

$\geq$「 $lg((\theta\gamma/2)^{-2}\ln(3((1-$が成り立つ時，とする．
アルゴリズムがすべての頻出アイテム $\{s\in\Sigma|f(s)\geq N\theta\}$ を$\frac{32\ln(\frac{3}{(1-\gamma/2)\theta\delta})}{(\gamma\theta)^{2}}lg(\frac{\ln(\frac{3}{(1-\gamma/2)\theta\delta})}{(\gamma\theta)^{2}})+1glgN$$\simeq$

を$b$$\sum_{s’\in K}K[s’]\geq 2^{b-2}$$\gamma/2)\theta\delta)^{-1}))\rceil+3$$1-\delta/3$以上である．

を $f(s)\geq\theta N$ を満たす頻出アイテムとする．超幾何分布に関する Chvatal[11] による以下の不等式を用いる．

考察 41. ストリーム $x=(x_{1}, \ldots,x_{N})$ を最後まで読み込んだ

時，それぞれのアイテム

$N-M$

$M$

$k$

$\sum\underline{(_{j})\cdot(_{n-j})}\leq e^{-2()^{2}n}\frac{k}{n}-\nabla M$がアルゴリズムに乱択されている
(2)
$j=0$
確率は等しくである．ここで， はアルゴリズム 1 の終了時における磯 onent である．上の不等式のパラメータをそれぞれ，$N=|x|,$ $M=f(s)$ ,$x_{i}$$(\begin{array}{l}Nn\end{array})$$2^{-h}$$h$証明．あるアイテムする．この時$x_{i}$$x_{i}$が到着した時の exponent の値を $h’$ とは $2^{-h’}$ の確率で $K$ に保存される．またアルゴリズムの $Step3-(ii)$ で $h’$ が更新された時，記憶した率 1/2 で $K$に従う．従って任意のアイテム

補題 41. パラメータ$\gamma/2)\theta\delta)^{-1}))\rceil+3$

$b$を

$b$

$k/n\leq(1-\gamma/2)\theta,$$k=(1-\gamma/2)\theta n$$M/N\geq\theta$$\geq$$x_{i}$$Pr$「 $lg((\theta\gamma/2)^{-2}\ln(3((1-$とする．この時$[K[s]<(1- \gamma/2)\theta\sum K[s’]]$$s’\in K$がアルゴリズムである．ロ$2^{-h}$.

が成り立つことより，次の不等式をえる．

$s\in\Sigma$の最後まで $K$ に保持されている確率はムを確中に保持し，1/2 の確率で消去する．するとアルの出現数は幾何分布

ゴリズム終了時の任意のアイテム$(^{K[s]}k)/2^{K[s]}$$x_{i}$$n= \sum_{s\in K}K[s’]\geq 2^{b-2},$$(1-\gamma/2)\theta n(^{M})\cdot(\begin{array}{l}N-Mn-j\end{array})$$\leq$$\sum_{j=0}$$\frac{J}{(\begin{array}{l}Nn\end{array})}$$e^{-2(\theta-(1-\gamma/2)\theta)^{2}2^{b-2}}\leq e^{-2(\theta\gamma/2)^{2}2^{b-2}}\leq\underline{(1-\gamma/2)\theta\delta}$$\leq$$h\geq 1$ が成り立つ時，アルゴリズとする．

1 について以下の確率が成り立つ．頻出アイテムは高々$1/\theta$3個しかないので，偽陰性の確率は以下である．

$\lfloor 1/\theta\rfloor(1-\gamma/2)\theta\delta/3\leq\delta/3$$Pr[\sum_{s’\in K}K[s’]\leq 2^{b-2}]\geq 1-\frac{\delta}{3}$

補題 43. パラメータ$\gamma/2)\theta\delta)^{-1}))\rceil+3$

証明．

$\sum_{s\in K’}K[s’]$は $Step3-(\ddot{u})$ の処理を除き単調増加である．

従つて $\sum_{s’\in K}K[s’]$ が$k$となる確率は二項分布

従$(\begin{array}{l}2^{b}k\end{array})/2^{2^{b}}\}_{\llcorner}^{-}$$b$$\square$を$b$$\geq$「 $lg((\theta\gamma/2)^{-2}\ln(3((1-$とする．

$\sum_{s’\in K}K[s’]\geq 2^{b-2}$がアルゴリズ

ム終了まで成立していた時，アルゴリズムが任意の頻出でないアイテム $\{s|f(s)<(1- )\theta N\}$ を出力する確率はを出力する確率は /3 以下で$\delta$$\downarrow\backslash$$\gamma$う．従って以下の式を得る．

ある．

証明．を不等式 $f(s)<(1-\gamma)\theta N$ を満たす，任意の頻出でないアイテムとする．ここで先の不等式をもう一度用いる．$N=$ 国，$s$$Pr[\sum_{s’\in K}K[s’]\leq 2^{b-2}]\leq\sum^{2^{b-2}}(\begin{array}{l}nj\end{array})$$2^{2^{b}}$$j=0$$M=N-f(s)$$k/n<1-(1-\gamma)\theta,$ $M/N\geq 1-(1-\gamma/2)\theta$とすれば，$n= \sum\ovalbox{\tt\small REJECT}$

ここで，二項分布に対する次の不等式を導入する．

$K[\ovalbox{\tt\small REJECT}’\ovalbox{\tt\small REJECT}\geq\ovalbox{\tt\small REJECT}=\ovalbox{\tt\small REJECT}$$\gamma/2)\theta)n$$\sum_{j=0}^{(p-t)n}(\begin{array}{l}nj\end{array})(1-p)^{n-j}\leq e^{-2t^{2}n}$パラメータをそれぞれ $t\in(O,p)$ .

$n=2^{b},$(1)$p=1/2,$ $t=1/4$が成り立つ．すると次の不等式を得る$Pr$$[K[s]\geq(1-\gamma/2)\theta n]$$=$$Pr[n-K[s]<(1-(1-\gamma/2)\theta)n]$とすれば次の不等式を得る．
$\leq$$j \sum_{=0}^{(1-(1-\gamma/2)\theta)n}\frac{(\begin{array}{l}Mj\end{array})\cdot(_{n-j}^{N-M})}{(_{n}^{N})}$$\sum_{j=0}^{2^{b-2}}(\begin{array}{l}nj\end{array})\frac{1}{2^{2^{b}}}\leq e^{-2(1/4)^{2}2^{b}}=e^{-\ln(\delta/3)}=\frac{\delta}{3}$$\leq$$\leq$$e^{-2((1-(1-\gamma)\theta)-(1-(1-\gamma/2)\theta))^{2}2^{b-2}}$$e^{-2(\theta\gamma/2)^{2}2^{b-2}} \leq\frac{(1-\gamma/2)\theta\delta}{3}$口

考察 4.2. $n= \sum_{s’\in K}K[s’]$ とした時，$K$ に含まれている任意のアイテム $s\in\Sigma$ の出現数は次の超幾何分布に従う．

アルゴリズムは最大で $1/(\theta(1-\gamma/2))$ 個の要素を出力する．したがって，偽陽性の確率は$\frac{1}{\theta(1-\gamma/2)}$.

$\frac{(1-\gamma/2)\theta\delta}{3}\leq\frac{\delta}{3}$.

$Pr[K[s]=j]=\frac{(^{f(s)})\cdot(^{N-j(s)})}{(_{n}^{N})}$

口162
これらの補題 41, 42, 43 より定理 41 を得る．最後に $(h+b)$

記憶領域で動作し，メモリのオーバーフローに対してロバストによる $lgN$ の近似の精度を示す．である．今後は計算機実験を行い，実データを用いた他のアル

補題 44. パラメータ$\gamma/2)\theta\delta)^{-1}))\rceil+3$$b$を$b$$\geq$「$lg((\theta\gamma/2)^{-2}\ln(3((1-$とする．アルゴリズムにアイテム$x_{n}$

ゴリズムとの性能比較，各パラメータの最適化を行う．

が入力された時，次の不等式が成り立つ．参考文献[1] R.S. Boyer and J.S. Moore, A fast majority vote
ICSCA-CMP-32, Institute forrithm, TechnicaJComputer Science, University of Texas, 1981.

$Pr[\lfloor lgn\rfloor-1\leq h+b\leq\lceil lgn\rceil+1]\leq 1-\delta$$alg(\succ$$R\epsilon port$

証明．上の不等式は以下を意味していることに注意する．
$Pr$$[\lfloor lgn\rfloor-1\leq h+b\leq\lceil lgn\rceil+1]$$=$$1-(Pr[h+b<lgn-1]+Pr[h+b>lgn+1])$[2] M. Fischer, and S. Salzburg, Finding a majority among
votes: solution to problem 81-5, J. Algorithms, 3 (1982),$n$$X(n;\alpha)$

を$1/2^{\alpha}$の確率で表が出るコインを用いた$n$回のベルヌーイ試行による幾何分布に従う確率変数とする．観察 4.2$X(n;\lfloor lg(n)\rfloor-b-1)<2^{b}$
より，の時，またその時に限り$h+b<\lfloor lg(n)\rfloor-1$である．ここで Chernoff 上界を用いると次の不等式を得る$Pr$$[h+b<\lfloor lg(n)\rfloor-1]\leq Pr[X(n;lg(n)-b-1)<2^{b}]$$=$$Pr[X(n;lg(n)-b-1)<\frac{2^{b}\cdot E[X(n;1g(n)-b-1)]}{E[X(n;lg(n)-b-1)]}]$$=$$Pr[X(n;lg(n)-b-1)<\frac{2^{b}\cdot E[X(n;lg(n)-b-1)]}{n2^{-1g(n)+b+1}}]$$=$$Pr[X(n;lg(n)-b-1)<\frac{2^{b}}{2^{b+1}}E[X(n;lg(n)-b-1)]]$$=$$\leq$376-379.
[3] E.D. Demaine, A. $L6pez$-Ortiz, and J.I. Munro, Frequency estimation of intemet packet streams with lmited space, In Proc. of 10th Amual European Symposium on Algorithms (2002), 348-360.
[4] R.M. $KarP$ , S. Shenker, and C. Papadimitriou, A sim$ple$ algorilhm for finding kequenl elements in slrems
and bags, ACM ‘Ransactions on Databaae Systems, $2S$(2003), 51-55.

[5] G.S. Manku, and R. Motwani, Approximate hequency
over data strems, In Proc. of 28th Intl. Conf. on$Ve\eta$ Large Data $Ba\infty$ (2002), 346-357.
$Pr[X(n;lg(n)-b-1)<(1-\frac{1}{2})E[X(n;lg(n)-b-1)]$$e$$-8+E[X(nilg(n)-b-1)]<e$-奏2$n2^{-lg_{(n)-b-1}}$$-$$-2^{b-2}<^{\underline{\delta}}$$\leq e$$-2$の時，またその時に限り $h+b>$が成り立つことも同様にして証明が可能である．

$X(n;\lfloor lg(n)\rfloor-b+1)\geq 2^{b}$$\lceil lg(n)\rceil+1$

Chernoff 上界を用いれば次の不等式を得られる．

$\infty unts$[6] H. Toivonen, Sampling large database for association
rules, In Proc. of $22nd$ Intl. Conf. on Very Data Bases(1966), 134-145[7] G. Cormode, and M. Hadjieleftheriou, Methods for nding&items in datastreams, The VLDB Joumal, 19$\infty l^{}$(2010), 3-20.

$Pr$$[h+b\geq\lceil lg(n)\rceil+1]\leq Pr[X(n;lg(n)-b+1)\geq 2^{b}]$$=$$Pr[X(n;lg(n)-b+1)\geq\frac{2^{b}\cdot E[X(n;1g(n)-b+1)]}{E[X(n;lg(n)-b+1)]}]$$=$$Pr[X(n;lg(n)-b+1)\geq\frac{2^{b}\cdot E[X(n;lg(n)-b+1)]}{n2^{-1g(n)+b-1}}]$$=$$Pr[X(n;lg(n)-b+1)\geq\frac{2^{b}}{2^{b-1}}E[X(n;lg(n)-b+1)]]$[S] H. Liu, Y. Yuan, and J. Han, Methods for mining
quent items in data strems, Knowl. and $Inf$. Syst, 26$h\triangleright$(2011), 1-30.

smau[9] R. Morris, Counting large numbers of events inters, Commmications of the ACM, 21 (1978), 840$re\dot{\mathfrak{X}}$$=$$\leq$$Pr[X(n;lg(n)-b+1)\geq 2E[X(n;lg(n)-b+1)]$842.

$e^{-\S E[X(n;lg(n)-b+1)]} \leq e^{-:n2^{-lg_{(n)+b-1}}}\leq e^{-2^{b-S}}\leq\frac{\delta}{2}$

口5結論
本研究ではシンプルな頻出アイテム発見乱択アルゴリズムを提案した．アルゴリズムは $O(\theta^{-2}\log(\theta^{-1})+1glgN)$ ビットの[10] P. Flajolet, Approximate
BIT 25 (1985), 113-134.

$\infty$untin : a detailed analysis,$g$[11] V. Chvatal, The tail of the hypergeometric distribution,
Discrete Mathematics 25 (1979), $28k287$.