Range Counting over Multidimensional Data Streams

Subhash Suri, Csaba D. Toth and Yunhong Zhou
Discrete and Computational Geometry
Issue Volume 36, Number 4 / December, 2006
Pages 633-655
http://dx.doi.org/10.1007/s00454-006-1269-4

SoCG2004特集号より．
ストリーム・アルゴリズムの論文．

ストリーム計算では，データがすごいスピードでひっきりなしに飛び込んでくる状況を考える．
この論文では，d次元空間の点が次々にやってくる場合を研究している．
そして，1つ1つの点は飛んできたその時点でしか参照できず，メモリの使用量も限られている状況でどのように計算するか考える．
メモリが限られているので，全ての点をそのまま保存することはできず，ある種の統計量だけを保存することになる．
ストリーム・アルゴリズムがしなくてはならないことは，そのような統計量をどのように決め，どのように更新して，どのように行ないたい操作を行なうか，ということの全てである．
この問題では，range counting (クエリ領域内にある点の個数を数えること) である．
しかし，全ての点を保存するわけではないので，アルゴリズムの答えは近似にしかならない．
この手の理論研究のすばらしいところはその近似誤差を予め指定しておけば，それを必ず達成できるようなデータ構造およびアルゴリズムを与えてくれるところである．

クエリ領域としてaxis-parallel boxとhalfspaceを考えている．
前者の場合，O(ε^{-d} log^{d}εn)の領域しか用いない決定性アルゴリズムとO(ε^{−2d/(d+1)} log^{d}(ε^{2/(d+1)}n))の領域しか用いないモンテカルロ型乱択アルゴリズムを与えている (成功確率は1-o(1)である)．
ここで，nは今までにアルゴリズムに飛び込んできた点の数で，εnが加法的許容誤差である．
データ構造の更新もpolylogarithmic時間で可能である．
アルゴリズムはGreenwald and Khanna (2001) による同じ問題の1次元バージョンに対する結果を軸ごとに組み合わせるというアイディアに基づいている．
後者の場合は，O(ε^{−2d/(d+1)} log^{d+1}ε^{−1})の領域しか用いないモンテカルロ型乱択アルゴリズムを与えている (成功確率は1/2である)．
しかし，こちらの方はデータ構造の更新にO(1)時間かかってしまう．
アルゴリズム自身はstabbing numberの小さいマッチングの存在 (Chazelle and Welzl 1989) とその近似的構成法 (Matousek 1992)，ランダムサンプリングによるε-approximationの構成 (Vapnik and Chervonenkis 1971) といった，現代計算幾何の標準的な技法を用いている．
そのため，結果はVC次元が小さい領域空間にも拡張できる．