《大數據算法》一3.1　空間亞線性算法概述

本節書摘來異步社區《大數據算法》一書中的第3章，第3.1節，王宏誌　編著, 更多章節內容可以訪問雲棲社區“異步社區”公眾號查看。

第3章　空間亞線性算法

3.1　空間亞線性算法概述

空間亞線性算法指的是在算法運行過程中需要的空間小於數據量的實際存儲空間，在一些情況下，空間亞線性算法也叫作數據流算法。因此我們首先介紹數據流模型。
1.數據流模型
數據流，顧名思義指的是流動的、源源不斷的數據，這些數據隻能順序掃描一次或幾次。因為數據是流起來的，所以隻能順序掃描，且隻能掃描常數次。這意味著對於這樣的數據，時間複雜度超過O(n)的算法是不可行的，而且能夠使用的內存是有限的。注意，“有限”指的是數據可能無限增大，但是能夠使用的內存是有限的，這就導致空間要求是亞線性的，而且最好所需空間和數據量是無關的。
為了基於這個模型實現算法，通常的方法是維護一個中間的內存結果，一般稱為數據略圖，它給出的是數據相關性質的一個有效估計。而這個中間結果的數據量往往是比較小的，通常與整個數據集合的數據量無關。
由於如下兩個方麵的原因，數據流模型適用於大數據。第一，時間有保障，它順序掃描數據僅一次。第二，內存要求低，通常是亞線性的。而且通過本節的一些實例可以看到，其內存需求量和數據量沒有特別直接的關係。
數據流模型中的數據流指的是來自某個域中的元素序列，可以表示為。注意後麵的省略號，一些和序列有關的問題往往以xn結尾，但是對數據流模型沒有xn，因為我們假定數據是源源不斷到來的，沒有結束。數據流模型的第二個要素是有限的內存，也就是內存的規模遠小於全部數據需占用內存的規模。這意味著把數據全部放到內存中計算不可行，通常所需要的內存為　若log計算中未標明底數，則默認底數為2。或，甚至是一個常數。而且當新元素到來時，需要快速處理每個元素，因為元素到來的快慢是不一定的，可能速度非常快，留給每個元素的處理時間並不充足。
通常，我們感興趣的函數是輸入流σ的元素中多重集的統計屬性，這個多重集可以用向量f=（f1,f2,…，fn）來表示，其中fj={i:ai=j}=σ中j出現的次數換句話說，σ隱式地定義了向量f，本章要討論的是形式為Φ(f)的函數的計算。在處理這種流時，當我們掃描每一個符號j∈［n］時，計算結果是頻率fj的一個增量，因此，可以認為σ是對於向量f的更新。
定義了這個概念後，我們要更多地考慮關於f的更新方法。比如，如果頻率fj能夠既是增加的又是減少的，並且由變量決定呢？這就引出了更加嚴格的模型。
定義3-1(十字轉門模型)　σ中的符號都屬於［n］×{-L,…,L},解釋如下:根據接收到的符號ai=(j,c)更新fj←fj+c。
向量f初始化為0。在這個廣義的模型中，改變變量m的作用是很常見並且自然的想法:m不代表流的長度，而代表在某一時刻這個多重集的項的最大數目。更形式化地，在任何時候，有這個模型的一種特殊情況叫作嚴格的十字轉門模型，在這種模型下假定任何時候f≥0。一種更加嚴格的模型叫作現金注冊模型，在這個模型中隻考慮正數的更新，比如要求每一次更新(j,c)滿足c>0。
2.數據流用途
那麼，從數據流中計算什麼？對數據庫和算法理論有一些了解的讀者可能知道，大概十年前數據流是數據庫研究的熱點之一，今天依然有很多人在研究。可以從數據流中計算和挖掘多種統計量，如最大值(max)、最小值(min)、和(sum)、平均值(avg)這些基本的聚集的值，也可以計算中位數、分位數、頻繁元素等更複雜的統計量，還可以做一些分析、挖掘、預警等，這些工作都吸引了大量研究人員。
3.數據流算法質量分析
因為人們已經證明很多函數不能通過亞線性空間來求解，因而我們從數據流中計算出的函數Φ(σ)的值通常是一個接近Φ(σ)的估計。而在算法設計過程中，我們通常使用隨機化的算法，盡管可能會導致一些錯誤，但都是可控製的。於是有了下列基本定義。
定義3-2　令A(σ)表示隨機流算法A在輸入σ時產生的輸出。注意這是一個隨機值。令Φ代表A要計算的函數。如果我們能夠得到則稱算法A為(ε,δ)乘法近似Φ。如果我們能夠得到則稱算法A為(ε，δ)加法近似Φ。
注意，上麵的定義先強調了乘法的接近。但是當Φ(σ)接近或者等於0的時候，我們可能要用到加法的接近。
4.數據流實例
考慮一個數據流的實例：{32,112,14,9,37,83,115,2,…}。
對於這個數據流容易計算的函數包括:最大值,最小值,和,計數。保存“和”與“計數”，相除結果即為avg。處理這些函數時通常采用單個寄存器s，並直接更新寄存器s。如求最大值，首先把寄存器初始化為0，然後比較當前元素x和寄存器中s的大小，將較大的量放到寄存器s當中，計算結束。在任意時刻，寄存器s中保存的數據都是當前數據流中的最大值。
計算sum的方法類似。首先都是把s初始化為0，所不同的是對於每個接收的x，將x累加到寄存器s中。這樣，在任何時刻單個寄存器s保存的數據就是當前到來的數據流的所有數據的和。
5.數據流合並
上麵例子中的數據概要就是單個值寄存器s。寄存器s是可合並的，即從一部分數據流得到x1，從另一部分數據流得到x2，通過x1和x2的累加或比較就可以得到整個數據流中當前所有元素的結果。例如，第100個之前的數放在x1，第100個以後的數放在x2，則x1和x2可以合並。通過比較x1和x2的大小，較大者就是這200個數中的最大值。同樣，和的略圖也是可合並的。前100個數據和存於x1，100個以後的數據和存於x2，將x1和x2相加就是當前所有元素的和。