本文為 STOC'04 Algorithms for Dynamic Geometric Problems over Data Streams 的閱讀筆記。
論文作者 Piotr Indyk， 研究領域：高維幾何問題, 流式演演算法，摘要資料結構維護, 稀疏傅立葉變換。
在假設 \(\text{P}\neq\text{NP}\) 的情況下，近似演演算法一般針對 NP 最佳化問題(NPO)，有兩點要求
演演算法 \(M\) 是確定性或者隨機的多項式演演算法。
演演算法近似界限 \(r\) 要儘可能低。
其中 \(M'\) 為最優解演演算法，\(X\in\text{NPO}\)。
通過 \(r(n)\) 可以定義一系列近似複雜度類，例如 \(f(n)\text{-APX}\) 表示存在近似演演算法 \(M\) 使得 \(r(n)\in O(f(n))\) 的問題集合。
一般來說 \(O(1)\text{-APX}\)(可以簡寫為 \(\text{APX}\)) 演演算法比較常見。
還有一些問題問題，存在演演算法可以無限逼近最優解，但是越逼近時空開銷越大，所以有 \(\text{PTAS}\subset \text{APX}\)，若對於任意 \(\epsilon>0\), \(\exists\) 時間複雜度為 \(O(f(n,1/\epsilon))\) 的演演算法，\(f\) 是 \(n\) 的多項式，\(r<1+\epsilon\)。若 \(f\) 為 \(n\) 和 \(1/\epsilon\) 的二元多項式，則為 \(\text{FPTAS}\)。
有時候，若得到的概率分佈滿足為
近似演演算法的演演算法複雜度可能涉及三個引數 \(n\), \(1/\epsilon\), \(1/\delta\)。
一般來說常見的近似演演算法是貪心等基本的組合演演算法，另一類常見的演演算法是規約到線性規劃然後採用隨機擾動(rounding)，原始對偶，線性鬆弛等。
另一類研究的比較少的近似演演算法，是針對 \(\sharp P\) 計數問題，常用的方法是馬爾可夫鏈蒙特卡洛方法。
流式演演算法適用的問題一般比 \(\text{NPO}\) 簡單，大多數是 \(\text{PO}\) 內，但是空間不足以存下之前的輸入或者要求強制線上，需要維護一個摘要或者取樣的演演算法，所以很難得到精確解，同樣需要借用用近似演演算法的評價標準。
早期流式演演算法研 究為一些簡單的統計量的維護：
中位數. 普遍情況是求第 \(k\) 小。
流式演演算法最早研究 Selection and sorting with limited storage（1978）。
文中介紹了一個亂資料下空間複雜度為 \(\theta(n ^{1/2})\) 錯誤率極低的流式隨機演演算法。
文章還嚴格證明了 \(p\) 次重複讀入的確定性演演算法空間複雜度上下界 \(\Omega(n^{1/p})\) 和 \(O(n^{1/p}\log^{2-2/p} n)\)。
不同元素個數 \(F_0\)。普遍地有 k 階頻率矩 \(F_k=\sum\limits_x f(x)^k\).
The space complexity of approximating the frequency moments(1996)
文章證明了 \(F_0, F_1, F_2\) 存在 \(O(\log n)\) 空間的逼近演演算法，用通訊複雜度證明了 \(F_k(k\ge 6)\) 則需要 \(n^{\Omega(1)}\) 的空間。
文章用到了均勻取樣，隨機變數，切比雪夫不等式，切爾諾夫界等概率論工具，以及通訊複雜度，將流式隨機演演算法的研究形式化，並且將這些工具廣開來成為現在的主流研究方法，可以算這個領域的開山之作。
文章構造了 \(2\log(1/\delta)\) 個隨機變數 \(Y_i\)，\(E(F_k)=E(\overline{Y_i})\)，然後 \(Y_i=\overline{X_{ij}}\) 為 \(8kn^{1-1/k}/\epsilon^2\) 個隨機變數的均值，\(X\) 為互相獨立的均勻取樣集生成的隨機變數，方法為 \(X=m(r^k-(r-1)^k)\), \(r=|\{q|q\ge p,a_p=a_p\}|\)，其中 \(p\) 為隨機抽樣的下標。維護這樣的 \(X\) 和 \(Y\) 空間複雜度為 \(O\left(\frac{k\log(1/\delta)}{\epsilon^2}n^{1-1/k}(\log n+\log m)\right)\)。
文中用切比雪夫不等式證明了單個 \(Y_i\) 相對誤差大於 \(\epsilon\) 的概率小於 \(\frac{1}{8}\)，根據切爾諾夫界，可以的到 \(2\log(1/\delta)\) 個 \(Y_i\) 的平均值的越界概率小於 \(\delta\)。文章針對 \(F_2\) 設計了專門的隨機變數，得到了更優的結果。
隨機變數估計的一個另一個更早的例子是，Probabilistic counting(FOCS,1983) 中提出演演算法，\(E(\log F_0)=E(\max(\text{lowbit}(\text{hash}(x))))\)，將統計量 \(F_0\) 用 \(\max(\text{lowbit}(\text{hash}(x)))\) 進行無偏估計，然後用一些概率論的技巧計算出其錯誤率，然後用 Median trick 可以降低錯誤率。
在後續的研究中有人引入和穩態分佈和隨機投影。
取樣最早是從統計學和資料科學中發展來的方法，看起來很簡單，但是合理的取樣方法可以在流式演演算法中起到出乎意料的作用。
隨機投影是高維問題中經常使用的方法。The Johnson-Lindenstrauss 引理指出高維空間中的一小部分點可以以點之間的距離幾乎被保留的方式嵌入到低維空間中。
通常的方法是把一些高維的範數分解成多個一維和二維的穩態分佈來近似。
通訊複雜度研究的是，將一個問題的輸入劃分到兩個或多個圖靈機，假設所有圖靈機有無窮的計算能力且彼此互信，協定相同，求解決問題需要傳輸的最小位元量與輸入規模之間的關係。
一個經典的協定是，兩臺圖靈機可以在傳遞 \(O(\log n)\) 個位元的情況下，計算出輸入的中位數。
通訊複雜度在很多領域例如計算複雜性理論，量子淺層析
的取樣複雜度下界，電路複雜度下界等領域有重要的作用。
在資料結構空間下界和流式演演算法空間下界中的應用方法一般是
一種方法是將流式問題轉化為分散式問題，即將資料流分配給多個參與者，讓他們各自處理自己的資料，並且在必要時進行通訊，最後輸出結果。這樣，流式問題的記憶體空間限制就變成了分散式問題的通訊限制。
另一種方法是使用資訊理論的工具，即將資料流看作是隨機變數，利用熵、互資訊等概念來量化流式問題中所需的資訊量，從而得到通訊複雜度的下界。
可壓縮性分析的核心思想是將流式演演算法與有限狀態自動機(DFA) 建立關係，利用 Myhill–Nerode 定理來尋找輸入的等價類數目，確定 DFA 可壓縮的下界從而刻畫出流式演演算法空間複雜度的下界。
Stanford University CS154 的 Note 中使用這種方法重新將頻率矩 \(F_k\) 下界複雜度的結論證明了一遍。
規約是在計算複雜性理論和精細複雜度領域常用的非常技巧。
本文研究的問題是在離散 \(d\) 維度量空間 \(D=\{1\cdots\Delta\}^d\) 中動態加點或刪點，維護點集的一個函數，其中中點之間的距離被定義為閔可夫斯基範數 \(d(x,y)=\left(\sum\limits_{i=1}^d|x_i-y_i|^p\right)^{1/p}\)。其中 \(\Delta\) 表示不同元素的個數。
這類問題首先在論文 The Geometry of Graphs and Some of its Algorithmic Applications(1994) 中被探討。文章提出了一些高效演演算法，在低維度量空間中以很小的失真嵌入圖。將一些圖上難解的問題例如直徑，最小割問題轉化為幾何問題，使用更高效的近似演演算法來解決。
Probabilistic approximation of metric spaces and its algorithmic applications(1996) 。這篇文章提出了任何度量空間都可以分層良分樹(HST)以 polylog 失真概率近似。
在 Approximating a finite metric by a small number of tree metrics(1998)，這篇文章中使用了線性規劃這種確定性演演算法構造了大小為 \(O(n\log n )\) 的 HST，使得每條邊期望失真不超過 \(O(\log n \log \log n)\)。
本文同樣使用了 HST，介紹了幾個高維度量空間問題的流式演演算法。
Approximating the minimum spanning tree weight in sublinear time(2001) 文中給出了圖上最小生成樹的亞線性任意近似演演算法，時間複雜度為 \(O(\frac{dw}{\epsilon^2}\log\frac{d}{\epsilon})\)，接近下界 \(\Omega(\frac{dw}{\epsilon^2})\)，其中 \(d\) 為點的平均度數，\(w\) 為邊權集合的大小。
The sensor spectrum: technology, trends, and requirements(SIGMOD, 2003) 中對感測器網路通訊代價的研究揭示了高維幾何中最小生成樹問題的實用意義亞線性任意近似演演算法，時間複雜度為 \(O(\mathrm{polylog}(n/\epsilon^{O(1)}))\).
同年 Estimating the Weight of Metric Minimum Spanning Trees in Sublinear-Time(2003) 文中的到了高維幾何(度量空間)中中最小生成樹問題的
基於前面文章的工作，在 Estimating the weight of euclidean minimum spanning trees in data streams(2004) 中提出了只支援插入情況下，最小生成樹問題的任意逼近流式演演算法。
本文對這個問題得到了在同時支援插入和刪除操作的情況下以 \(r=O(d\log \Delta)\) 逼近，空間為 \(O(d\log^2\Delta)\) 的流式演演算法。
Chen, Jayaram, Levi, Waingarten 將這個問題改進到 \(r\le 1.10\)，空間為 \(\Omega(\sqrt{n})\)。
空間中匹配問題分為兩種
本文作者指出 Similarity estimation techniques from rounding(1996) 這篇文章的方法足以解決雙色匹配問題。
本文給出了無色匹配的 \(r=O(d\log \Delta)\)，空間為 \(O(d\log^2\Delta\log\log\Delta)\) 的演演算法。
文中提到，經過仔細分析，可以做到 \(r=1+\epsilon\)，且空間複雜度只乘上 \(O(1/\epsilon^2)\) 因子的演演算法，但是沒有在本文列出。
這類問題由在鐵路上的感測器通訊問題發展而來。
本文給出了一個 \(r=O(d\log^2\Delta)\)，空間為 \(O(d^2\log^2\Delta)\) 的演演算法。
在 Streaming Facility Location in High Dimension via New Geometric Hashing(2022) 中，提出了一種基於重要性取樣的演演算法，改進到了雙次掃描 \(r=O(1)\)，空間為 \((d\log \Delta)^{O(1)}\)，單次掃描 \(r=O(d/\log d)\)。同時這篇文章給出了一種空間為 \(O(n^{1/\epsilon})\) 的任意近似演演算法。
k-聚類問題是幾何問題中非常經典的 NPO 問題，在機器學習等眾多領域有著很重要的作用，已經有眾多有效的啟發式演演算法和近似演演算法。
在作者所在的時間，已經提出了 \(r=3+\epsilon\)，時間為 \(O(n^{1/2\epsilon})\) 的非流式演演算法。目前最優的逼近比是 \(r=2.406\)，由 Improved approximations for Euclidean k-means and k-median, via nested quasi-independent sets(2022) 文中提出。
本文使用了多種工具和演演算法例如互斥計數，中點成本估計，本地搜尋，貪心等。分別做到了不同的複雜度。
在 The Power of Uniform Sampling for k-Median(2023) 中，作者分析了樸素的均勻取樣的方法，如果要達到 \(r=O(1)\)，則取樣率至少為 \(\Omega(1/\beta)\)，\(\beta\) 為均勻度。如果要達到任意近似，則至少達到 \(O(\mathrm{poly}(k/\epsilon\beta))\) 取樣率。
如果一個有根樹 \(T\) 是 k-HST，則滿足
一個 HST 上的度量空間可以定義為其上所有葉節點，而度量為葉節點之間的最短路。
本文參照了前人的結論，任意 \(\{1\cdots\Delta\}^d\) 的子集 \(P\) 上的度量可以被嵌入一系列 2-HST 度量的概率組合，且失真率小於 \(O(d\log\Delta)\)。
文中以該隨機演演算法構建 2-HST
首先對 \(P\) 中所有點增加一個隨機偏移 \(\Delta p\in [0,\Delta]^d\)
樹分為 \(\log\Delta +2\) 層 \(G_0,\cdots, G_{\log\Delta+1}\)。
- \(G_0\) 為 \(P\) 中的點為葉節點。\(G_{\Delta +1}\) 表示根節點。
- \(G_i\) 表示包含了 \(P\) 中點的大小為 \(2^{i-1}\) 的網格。
- \(G_i\) 與 \(G_{i+1}\) 之間按包含關係連邊，邊權為 \(2^i\)。
這是本文創新提出的方法，令統計量 \(\pi_S(c)\) 表示點集 \(S\) 落在網格 \(c\) 中的數量。這種統計量前人已經研究的很多了。本文用這個統計量的組合來逼近要求的問題，將近似最佳化問題轉化為 \(\log\Delta\) 個近似計數問題。
由 Lemma7.1 可以把問題轉化為求 \(w(T)\)。通過定義和恆等變換，很容易得到 5.2 中的式子。
考慮統計每個 \(|G_i|\)，發現可以等價為統計不同元素的個數 \(F_0\)，根據前人的結論可以做到 \(O(\log(n+\Delta^d))=O(d\log\Delta)\) 空間，於是總的空間為 \(O(d\log^2\Delta)\)。
根據 Lemma7.2 可以把問題轉化為 \(\log\Delta\) 個 Odd Count 問題。
維護長度為 \((\frac{\Delta}{2^i})^d\) 的陣列 \(x_i\)
文中提出了一種 \(r=O(1)\)，空間複雜度為 \(O(\log\Delta)\) 的演演算法，有常數概率出錯。如果將演演算法並行執行 \(O(\log\log\Delta)\) 取均值，可以做到超出界限的概率無限減小變為 \(\frac{1}{2\log\Delta}\)。
文章首先構造了一個概率判定演演算法
M="On input \(OC,T\)，\(OC\) 是一個流式 Odd Count 問題，\(T\) 是引數
- 初始以 \(1/T\) 的等價概率選取 \(x\) 下標的一個子集 \(R\)。 \(s\leftarrow 0\)。
- \(\text{Update}(i, c)\)，如果 \(c\in R\), \(s\leftarrow 2 -s\)。
- \(\text{OddCount}\) : 輸出 \(s\) 是否為 \(1\)。
這個演演算法滿足（證明見 Lemma7.3）
YES。YES。通過作者本人之前的文章 pseudorandom generators, embeddings and data stream computation(2000) 中給出的方法，可以用偽亂數生成器以 \(O(d\log \Delta)\) 的空間儲存這個隨機集合。
本文後續沒有介紹如何通過判定問題近似演演算法推出計數問題的演演算法，推測是等比構造了 \(\log \Delta\) 個 \(T\) 將近似比約束在 \(O(1)\) 的範圍內，然後偽亂數可以在不同的並行運算中複用。
總空間複雜度為 \(O(d\log^2\Delta\log\log\Delta)\)，近似度為規約到 HST 的 \(O(d\log\Delta)\)。
根據 Lemma7.4，工廠選址問題可以以 \(O(d\log^2\Delta)\) 的近似度規約到 \(\log\Delta\) 個 Bounded Count 問題
維護 \((\frac{\Delta}{2^i})^d\) 個點集 \(S_x\)。
文章對 Bounded Count 給出的演演算法是用偽亂數生成器構造了一個值域為 \(T\) 的雜湊函數 \(h\)，然後從用這個雜湊函數從流中等價取樣了 \(1/T\) 種不同的值，一旦任意一個值落入某個集合，則這個集合按滿的答案 \(T\) 算，這樣問題便轉化為了求不同元素 \(F_0\)。這種轉化可以保證失真在 \(O(1)\) 內，證明見 Lemma7.5。
在作者自己之前的論文中指出，生成隨機雜湊函數的偽亂數生成器需要消耗 \(O(\log^2 M)\)。在 \(\log\Delta\) 個並行運算中這些可以複用，總空間複雜度為 \(O(d^2\log^2\Delta)\)。
根據 Lemma7.6，存在 \(r=(1+\epsilon)\) 的近似演演算法，針對給定的中心點求出 k-median 的代價。
區域性搜尋也稱為爬山法，是一種很常見的啟發式演演算法，缺點是容易陷入區域性最優解。
本文參照了 Local search heuristics for k-median and facility location problems(2002) 中的結論證明了在 k-median 問題上區域性搜尋可以做到 \(r=5\)。
再引入計算代價的失真，總體可以做到 \(r=5+\epsilon\)，空間複雜度 \(O(k\cdot\mathrm{polylog}(\Delta))\)。
如果換成全域性搜尋可以做到 \(r=1+\epsilon\)。
貪婪法的思路很簡單，初始讓集合為空，每次選擇使得代價減少最多的點。
文中為了降低複雜度，對貪心做了一些優化。
若 MST 為 \(\mathcal{T}\)，生成的 HST 為 \(T\), \(\frac{w(T)}{w(\mathcal{T})}\le O(d\log\Delta)\)。
因為 HST 的兩點距離不大於原來兩點距離的 \(O(d\log\Delta)\) 倍
\[w(T)\le\sum_{u,v\in\mathcal{T}}d_T(u,v)\le O(D\log\Delta)w(\mathcal{T}) \]
HST 上最小匹配等於 \(n+\sum\limits_i^{\log\Delta}2^im_i\)，\(m_i\) 為 \(G_i\) 的 odd count.
考慮 HST 上每個節點到父節點的邊經過的次數，容易發現，如果經過次數大於 \(1\) 次可以將這兩組匹配交叉使得答案更優。所以最多經過一次，且僅當子樹葉子節點數量為奇數時才需要。
6.2 中的判定性問題滿足其中提到的概率條件。
本文參照了 Efficient search for approximate nearest neighbor in high dimensional spaces 中的 Lemma2.1 證明方法，表示兩者相似。
如果 HST 上工廠選址問題最優代價是 \(C\)， \(Q=\sum\limits_{i=1}^{\log\Delta}\left(\sum\limits_{c\in G_i}\min\{2^i\times\pi_P(c),f\}\right)\) 是 \(C\) 的一個 \(O(\log\Delta)\) 近似，滿足
首先，構造一個代價為 \(Q+f\) 的方案，在根節點放一個工廠，然後對所有 \(2^i\times\pi_P(c)\ge f\) 的節點放置一個工廠，這樣的代價為 \(C'\)，\(C\le C'<Q+f\)。
對於等式的另一邊，容易知道對於每一層 \(\sum\limits_{c\in G_i}\min\{2^i\times\pi_P(c),f\}\le C\)，所以總共 \(\log\Delta\) 層加起來小於 \(C\log\Delta\)。
6.3 中的演演算法是 Bounded Count 的 \(O(1)\) 近似演演算法。
若 \(K\) 表示有最終統計出的不同元素個數，\(p(k)=1-(1-1/T)^k\) 表示某個集合有 \(k\) 元素且沒有全部被雜湊函數篩出的概率。
\[E(K)=\sum_i p(|S_i|) \]\[\text{Var}(K)=\sum_i p(|S_i|)-p^2(|S_i|)\le E(K) \]根據切比雪夫不等式
\[P(|K-E(K)|\ge \epsilon E(K))\le \frac{\text{Var}(K)}{\epsilon^2E(x)^2}\le \frac{1}{\epsilon^2} \]
設給定 k-中心點 \(Q\)，k-聚類代價為 \(C(Q,P)\)。
設 \(R_i(Q)=|P-B(Q,r_i)|\)，\(R_i(Q)\) 可以用本文提出的 Exclusive Count 演演算法以 \(r=(1+\epsilon)\)，\(\delta=\frac{1}{2}\)，空間為 \(\Omega(k)\) 得到近似 \(\hat{R_i}(Q)\)，滿足
文章使用 \(\hat{C}(P,Q)=(r_i-r_{i-1})\hat{R}_i(Q)\) 近似 \(C(P,Q)\)。
所以 \(\hat{C}(Q,P)\) 是 \(C(Q,P)\) 的一個 \((1+\epsilon)\) 近似。