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

[[210234]]

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

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

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

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

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

發(fā)現(xiàn)趨勢

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

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

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

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

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

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

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

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

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

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

小數(shù)據(jù)

小數(shù)字比大數(shù)字容易跟蹤。

想象一下，假如你正在監(jiān)視0到50000000之間的一個數(shù)字流(這項任務類似于按照IP地址來記錄互聯(lián)網(wǎng)用戶)。可以使用50000000項索引來跟蹤這些數(shù)字，但是很難處理這么龐大的索引。更好的方法是把每個八位數(shù)字視為連接在一起的四個兩位數(shù)字。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

構建塊

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

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

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

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

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

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