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

[[210234]]

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

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

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

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

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

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

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

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

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

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

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

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

這方面的工作大多數(shù)依賴索引(index)。想象一下，設(shè)若你試圖識(shí)別頻繁的搜索字詞。一個(gè)辦法就是為英語中的每個(gè)單詞分配一個(gè)編號(hào)，然后將該編號(hào)與跟蹤該詞搜索了多少次的第二個(gè)編號(hào)配對(duì)起來。也許“aardvark” 以單詞編號(hào)17被編入索引，并在數(shù)據(jù)庫(kù)中顯示為(17，9)，意思是單詞編號(hào)為17的單詞已被搜索9次。這種方法離將最頻繁的項(xiàng)放在手邊更近了一步，因?yàn)樵谌魏翁囟〞r(shí)刻，你知道每個(gè)單詞到底被搜索了多少次。

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

但要是字典里只有100個(gè)單詞，將會(huì)怎么樣?羅伊·尼爾森說：“遍歷字典中的每個(gè)單詞花不了太長(zhǎng)時(shí)間。”

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

小數(shù)據(jù)

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

構(gòu)建塊

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

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

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

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

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

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