摘要：為了高效地分析海量的數據，科學家首先要將大數打破成碎片。作者循序漸進地闡述了一個處理海量數據流的***流式算法，算法經過不斷改進，是超大規模數據流高性能分析的新算法，以下是譯文。

[[210234]]

當從消防水帶出來的水沖擊你的臉部時，很難計量水。從某種意義上說，這正是分析數據流所面臨的挑戰，數據源源不斷地向我們奔流而來，永不停息。如果在Twitter上看一篇篇推文不停閃過，你可能想要暫停一下，以便弄清楚時下的流行話題是什么。話雖這么說，但這行不通，所以需要找到一種方法，以便實時記錄主題標簽。

執行這種實時計算的計算機程序稱為流式算法。因為數據以龐大的量持續不斷地出現，流式算法試圖記錄下重要的數據，同時戰略性遺忘其余數據。30多年來，計算機科學家一直致力于構建更好的流式算法。去年秋天，一個研究小組發明了一種近乎***的算法。

哈佛大學的計算機科學家杰拉尼·尼爾森(Jelani Nelson)表示：“我們開發了一種新算法，從各個標準維度來看，也是***的算法”，他與丹麥奧胡斯大學的卡斯珀·格林·拉森(Kasper Green Larsen)、哥本哈根大學的邁克爾·托魯普(Mikkel Thorup)以及東北大學的阮惠(Huy Nguyen)一起提出了這個新算法。

[[210235]]
哈佛大學的理論計算機科學家杰拉尼·尼爾森與別人共同開發出了新算法。
圖片來源：Yaphet Teklu

這種***的流式算法的工作原理是，通過記住足夠多的數據來告訴你它最?？吹降氖鞘裁?。這表明在數據流分析中固有的折衷實際上似乎并不必要。這也為戰略性遺忘的新紀元指明了前進的道路。

發現趨勢

流式算法在監視連續不斷更新的數據庫的任何情況下都是有幫助的。這可能是AT&T持續不斷的選項卡數據包或者Google繪制永無止境的搜索查詢流程。在這些情況下，流式算法是非常有用的，甚至是必要的，即使沒有重新檢查或甚至記住你所見過的每一段數據，都有一種方法來回答數據方面的實時問題。

這里有一個簡單的例子。假設有一連串的數字，想知道目前為止你所看到的所有數字的總和。這種情況下，很顯然不是記住每一個數字，只需要記住一個數字：累計總數。

然而，當想問的關于數據的問題變得更復雜時，這個挑戰就更難了。想象一下，假設不是想計算總和，而是想回答以下問題：哪些數字最常出現?看不太出來有什么捷徑可以快速給出正確的答案。

這個特殊的謎題被稱為“頻繁項”(frequent item，或heavy hitter)問題。解決這個難題的***個算法是在20世紀80年代初由康奈爾大學的大衛·格里斯(David Gries)和得克薩斯大學奧斯汀分校的賈亞德夫·米斯拉(Jayadev Misra)開發的。他們的算法在許多方面是有效的，但卻不能處理所謂的“變化檢測”。它可以告訴你最常搜索的詞語，但是無法告訴哪些詞語很流行。以Google為例，它可以將“維基百科”視為一個受歡迎的搜索詞語，卻發現不了與艾爾瑪颶風等重大事件相伴隨的熱搜。

沃里克大學的計算機科學家格雷厄姆·科爾莫德(Graham Cormode)說：“這是一個編碼問題 ——你將信息編碼為簡潔的摘要，并嘗試提取信息，讓你恢復最初的內容。”

在接下來的30多年里，科爾莫德和其他計算機科學家改進了Gries和Misra的算法。比如說，一些新的算法能夠檢測出流行詞語，另一些算法能夠更精細地定義某個詞語怎樣才算是頻繁詞語。所有這些算法都有其弊端，比如犧牲速度以換去準確性，或者犧牲內存消耗來保證可靠性。

這方面的工作大多數依賴索引(index)。想象一下，設若你試圖識別頻繁的搜索字詞。一個辦法就是為英語中的每個單詞分配一個編號，然后將該編號與跟蹤該詞搜索了多少次的第二個編號配對起來。也許“aardvark” 以單詞編號17被編入索引，并在數據庫中顯示為(17，9)，意思是單詞編號為17的單詞已被搜索9次。這種方法離將最頻繁的項放在手邊更近了一步，因為在任何特定時刻，你知道每個單詞到底被搜索了多少次。

盡管如此，它還是有缺點的，那就是要花很多的時間用一個算法來梳理英語中成千上萬的單詞。

但要是字典里只有100個單詞，將會怎么樣?羅伊·尼爾森說：“遍歷字典中的每個單詞花不了太長時間。”

可惜，字典里的單詞數量實在是太多了。正如新算法的作者發現的那樣，除非你可以把大字典分解成更小的字典，并找到一種巧妙的方法把它重新組合起來，否則無計可施。

小數據

小數字比大數字容易跟蹤。

想象一下，假如你正在監視0到50000000之間的一個數字流(這項任務類似于按照IP地址來記錄互聯網用戶)?？梢允褂?0000000項索引來跟蹤這些數字，但是很難處理這么龐大的索引。更好的方法是把每個八位數字視為連接在一起的四個兩位數字。

設若看到數字12345678。一種高效記憶的方法是將其分解成四個兩位數塊：12,34,56,78。然后，可以將每個塊發送給計算項目頻率的子算法：12發給子算法一，34發給子算法二，56發給子算法三，78發給子算法四。

每個子算法都為它看到的內容建有各自的索引，但由于每個版本都不會看到比兩位數大的索引，所以每個索引只是從0到99。

這種分拆的一個重要特點是，如果大數字——12345678 在整個數據流中頻繁出現，其兩位數字塊部分也將頻繁出現。如果要求每個子算法識別出最常看到的數字，子算法一會給出12，子算法二將給出34，依此類推。只要在四個短得多的列表中查找頻繁項，就能夠找到龐大列表中最常見的內容。

圖片來源：Lucy Reading-Ikkanda/《Quanta》雜志

尼爾森說：“不是花5000萬個時間單位遍歷整個宇宙，只是四個算法，花了100個時間單位。”

這種分而治之策略存在的主要問題是，雖然很容易把一個大數字分解成小的數字，但將小數重新組合成大數比較棘手— 很難找出正確的小數來重新組合，從而獲得正確的大數。

想象一下，你的數據流通常包含幾個數字相同的兩個數：12,345,678和12,999,999。兩者都從12開始。你的算法將每個大數字分成四個較小的數字，然后將每個小數字發送給子算法。然后你問每個子算法，“哪些數最?？吹?”子算法1將會說：“我經?？吹綌底?2.” 一種算法試圖識別是哪個八位數字，在這種情況下，經常不知道這些12是屬于其中某一個八位數的，還是屬于該例中兩個不同的八位數的。

尼爾森說：“難就難在搞清楚哪些兩位數塊與另外哪些兩位數塊連在一起。”

新算法的作者通過將每個兩位數塊封裝成一個不占用大量內存的小標簽來解決這個困境，但是仍然允許算法將兩位數的塊以正確的方式重新組合在一起。

要查看標簽如何工作的簡單方法，不妨從12,345,678開始，并將其拆分成兩位數塊。但這一次，在將每個塊發送到其各自的子算法之前，使用一對唯一的標識號封裝塊，標識號可以將塊重新組合在一起。這些標簽中的***個用作塊的名稱，第二個標簽作為環。這樣一來，12345678成為：

這里，數字12的名稱為“0”，并鏈接到名為“1”的數字。數字34的名稱為“1”，并鏈接到名為“2”的數字，依此類推。

現在，當子算法返回最常見的兩位數字塊時，12找尋一個標有“1”的數字，從而找到34，然后34找尋一個標有“2”的數字，從而找到56， 56找尋一個標有“3”的數字，從而找到78。

這么一來，可以把兩位數字塊視為鏈中的環，并通過這些額外的標記號將這些環連接在一起。

當然許多鏈的問題在于，其牢固性完全取決于最薄弱的那一環。而這些鏈幾乎可以保證會斷掉。

構建塊

沒有一種算法能在每次運行時都***地運行——即使***的算法也會在很小的一段時間內失效。在上述的例子中，一個失效可能意味著第二個兩位數的塊，34，被分配了一個不正確的標簽，結果就是當它去找尋它應該連接的塊時，它沒有找到56所需要的信息。一旦鏈中的一個環節失敗，整個工作就土崩瓦解了。

[[210237]]
哥本哈根大學的計算機科學家邁克爾·托魯普幫助開發了一種防止錯誤的方法來記住數據。
圖片來源：UNIAVISEN.DK

為了避免這個問題，研究人員使用所謂的“擴展圖”。在擴展圖中，每兩個數字塊形成一個點。這些點按線連接(遵循上述的標記過程)形成一個聚類。擴展圖的一個重要特點是，不只是將每個點與其相鄰的塊連接起來，而是將每個兩個數字塊與多個其它塊連接起來。以12345678為例，不僅將12與34連接，也與56連接，這樣即使12和34之間的鏈接失敗，仍然可以知道12和56屬于同一個數字。

擴展圖的結果并不總是***的。有時它無法鏈接本該鏈接的兩個塊，或者會鏈接不屬于一起的兩個塊。為了克服這個不足，研究人員開發了其算法的***環節：“聚類保留”子算法，它可以調查擴展圖，準確地確定哪些點旨在聚合起來、哪些點不是，即使某幾條線丟失、虛假線添加上去也沒關系。

托魯普說：“這確保我可以恢復看起來酷似原始聚類的內容。”

雖然Twitter不會明天就使用這個擴展圖，但其底層技術適用于解決極其廣泛的計算機科學問題，而不是僅僅用來統計推文。該算法還證明了不需要作出某些犧牲，也即以前在回答頻繁項目問題的時候似乎非常必要的犧牲。以前的算法總是放棄一些東西——準確性很高，但很費內存，或者速度很快，但是無法確定哪些頻繁項很流行。這個新的算法表明，若有正確的方法來編碼大量信息，你***能夠集眾者之所長：不僅可以存儲頻繁項，還可以取回頻繁項。