在許多計算設(shè)置中，相同信息的超載是一個需要關(guān)注的問題。例如，跟蹤其網(wǎng)絡(luò)應(yīng)用以識別整個網(wǎng)絡(luò)的健康狀況以及現(xiàn)場異常或行為變化。然而，事件發(fā)生的規(guī)模是巨大的，每個網(wǎng)絡(luò)元素每小時可能會發(fā)生數(shù)以萬計的網(wǎng)絡(luò)事件。雖然技術(shù)上允許監(jiān)控事件的規(guī)模和粒度在某個數(shù)量級內(nèi)的增加，但是，處理器、內(nèi)存和磁盤理解這些事件的能力幾乎沒有增加。即使規(guī)模很小，信息量也可能過大，無法方便地放在存儲中。

為了應(yīng)對這一挑戰(zhàn)，流數(shù)據(jù)處理模型變得越來越流行。其目的不再是捕獲、存儲和索引每一事件，而是快速處理每一個觀察結(jié)果，以便創(chuàng)建當(dāng)前狀態(tài)的摘要。處理完成后，事件被刪除，不再可訪問。這樣的處理意味著另一種權(quán)衡: 對世界的描述是近似的而不是精確的，而且需要回答的問題性質(zhì)必須事先決定，因此有些問題是無法解決的。然而，用適度的資源以極快的速度處理大量數(shù)據(jù)的能力，可以突破數(shù)據(jù)量的限制。因此，流處理技術(shù)已經(jīng)在許多領(lǐng)域得到應(yīng)用，從電信擴(kuò)展到搜索引擎、社交網(wǎng)絡(luò)、金融以及時間序列分析領(lǐng)域(例如IoT領(lǐng)域)。數(shù)據(jù)摘要的方法是更具成本效益，涉及到算法技巧、系統(tǒng)知識和數(shù)學(xué)洞察力的混合。

具體的方法可能有哪些呢?

抽樣

當(dāng)面對大量需要處理的相同信息時，可能有一種強(qiáng)烈的誘惑，就是完全忽略它。一個稍微有點原則的方法就是忽略大部分，也就是從整個數(shù)據(jù)集中選取少量的樣本，在這個子集上執(zhí)行計算，然后嘗試外推到整個數(shù)據(jù)集。為了給出一個好的估計，抽樣必須是隨機(jī)的。

抽樣方式有很多種，最基本的方式是均勻隨機(jī)抽樣。對于大量的數(shù)據(jù)記錄，隨機(jī)選擇少量記錄作為樣本。然后根據(jù)樣本回答各種問題， 例如，估計什么比例的客戶在一個特定的城市或購買了一個特定的產(chǎn)品。

那么，樣本應(yīng)該有多大才能提供好的結(jié)論呢?根據(jù)標(biāo)準(zhǔn)的統(tǒng)計結(jié)果，對于像客戶記錄中的抽樣問題，s 大小的樣本的標(biāo)準(zhǔn)誤差與1/s 成正比。粗略地說，這意味著在從樣本中估計一個比例時，誤差應(yīng)該看起來像 ± 1/s。因此，觀察一個1000個用戶投票的一個意見調(diào)查，其誤差大約為3% ，即真實的答案在樣本結(jié)果的3% 之內(nèi)，增加樣本數(shù)量會使錯誤以一種可以預(yù)測的方式減少，如果將調(diào)查的誤差降低到0.3% 需要聯(lián)系100,000個用戶。

其次，如何抽取樣本?簡單地獲取第一個 s 記錄并不能保證是隨機(jī)的，所以需要確保每個記錄都有同樣的機(jī)會被包含在樣本中。這可以通過使用標(biāo)準(zhǔn)的隨機(jī)數(shù)生成器來選擇要包含在樣本中的記錄。一個常見的技巧是給每個記錄附加一個隨機(jī)數(shù)，然后根據(jù)這個隨機(jī)標(biāo)記對數(shù)據(jù)進(jìn)行排序，并按照排序順序獲取第一個 s 記錄。只要對整個數(shù)據(jù)集進(jìn)行排序不會花費太多的成本，這種方法就可以很好地工作。

最后，當(dāng)增加新數(shù)據(jù)時，如何維護(hù)樣本呢?一個簡單的方法是，對于 p 的某個選擇值，以概率 p 來挑選每條記錄。當(dāng)一個新的記錄出現(xiàn)時，在0和1之間隨機(jī)選擇一個分?jǐn)?shù)，如果它小于 p，將記錄放入樣本中。這種方法的問題在于，我們事先并不知道 p 應(yīng)該是什么。在以前的分析中，需要一個固定的樣本大小 s，并且使用固定的抽樣率 p。這意味著最初的元素太少，而隨著記錄的增加又會使元素太多。這個問題就像是一個算法難題，事實上這是多年來技術(shù)面試中常見的問題。一個解決方案是隨著新記錄的到來，遞增地調(diào)整 p。維護(hù)抽樣的一種簡單而優(yōu)雅的方法是采用隨機(jī)標(biāo)記的思想。向每個記錄附加一個隨機(jī)標(biāo)記，并將樣本定義為具有最小標(biāo)記值的 s 記錄。當(dāng)新記錄到達(dá)時，標(biāo)記值決定是否將新記錄添加到樣本中，并刪除舊記錄以保持樣本大小固定在 s。

抽樣方法是如此普遍，應(yīng)用的示例很多，一個簡單的例子是在數(shù)據(jù)庫系統(tǒng)中，為了進(jìn)行查詢規(guī)劃，通常需要保存一個大型關(guān)系的樣本。在決定如何執(zhí)行查詢時，評估不同的策略可以估計每個步驟中可能發(fā)生的數(shù)據(jù)縮減量。另一個例子來自數(shù)據(jù)集成和鏈接領(lǐng)域，其中的一個子問題是測試來自不同表的兩列是否可以與同一組實體相關(guān)。全面比較各個列可能會耗費時間，特別是在希望測試所有列對的兼容性時，比較小的樣本通常足以確定列是否有任何機(jī)會與相同的實體相關(guān)。

抽樣方法如此簡單而通用，那為什么還需要其他方法來總結(jié)數(shù)據(jù)呢?事實證明，抽樣并不能適用于某些問題。任何需要詳細(xì)了解數(shù)據(jù)中各個記錄的問題都不能通過抽樣方法來解決。這樣的問題最終需要記錄所有的信息，并且可以通過高度緊湊的編碼來解決。一個更復(fù)雜的例子是當(dāng)問題涉及到確定數(shù)量基數(shù)的時候，在具有許多不同值的數(shù)據(jù)集中，某種類型的不同值有多少?例如，在一個特定的客戶數(shù)據(jù)集中有多少個不同的姓氏?使用一個樣本基并不能揭示這個信息。最后，一些樣本可以估計的數(shù)量，但是對于這些數(shù)量，還有更好的摘要方法。

對于諸如估計一個特定屬性(如居住城市)的頻率問題，可以建立一個 s 大小的樣本集，保證的誤差是1/s。這是相當(dāng)強(qiáng)大的采樣保證，只有提高了我們投入更多的空間，草圖。本文后面描述的 Count-Min 示意圖具有此屬性。其中一個限制是，必須在設(shè)置草圖之前指定感興趣的屬性，而示例允許您評估查詢中所采樣項目的任何記錄屬性。假設(shè)在100萬個記錄中的1000個樣本中，只有900個姓氏出現(xiàn)在抽樣的名字中。關(guān)于這些名字在其他數(shù)據(jù)集中的流行程度，您能得出什么結(jié)論?完整數(shù)據(jù)集中的幾乎所有其他名稱也都是唯一的。或者，示例中的每個唯一名稱在剩余的數(shù)據(jù)中重復(fù)出現(xiàn)數(shù)十次或數(shù)百次。由于樣本信息的存在，這兩種情況無法區(qū)分，導(dǎo)致了這兩種統(tǒng)計方法的巨大置信區(qū)間。跟蹤有關(guān)基數(shù)的信息，并省略重復(fù)的信息，可以通過諸如 HyperLogLog 之類的技術(shù)進(jìn)行處理，稍后將進(jìn)行處理。

布隆過濾器

布隆過濾器是一種緊湊的數(shù)據(jù)結(jié)構(gòu)，可以作為一組數(shù)據(jù)項的摘要。任何計算機(jī)科學(xué)的數(shù)據(jù)結(jié)構(gòu)類型都有“字典”，例如數(shù)組、鏈表、哈希表和許多平衡樹及其變體。這些結(jié)構(gòu)的共同特點是，都可以回答某個項目是否存儲在結(jié)構(gòu)中。布隆過濾器也可以回答這樣的成員資格問題，而且空間利用率更高。

為了理解這個過濾器，考慮一個簡單成員問題的精確解是有幫助的。假設(shè)希望跟蹤一百萬個可能記錄中的哪一個，并且每個記錄都被貼上了 ID 標(biāo)簽，然后可以保持一個一百萬位的數(shù)組，初始化的0。每次看到記錄 i 時，只需將數(shù)組中的第 i 位設(shè)置為1。對記錄j 的查找查詢相應(yīng)地非常簡單，只需查看位 j 是1還是0。該結(jié)構(gòu)非常緊湊，如果將位數(shù)據(jù)放到內(nèi)存中，125KB 就足夠了。

然而，真正的數(shù)據(jù)很少有這么好的結(jié)構(gòu)。一般來說，可能有一個更大的輸入集，例如客戶的名稱，其中可能的名稱字符串?dāng)?shù)量是巨大的。不過，可以通過借用不同的字典結(jié)構(gòu)來調(diào)整位數(shù)組的方法。假設(shè)位數(shù)組是一個哈希表，將使用哈希函數(shù) h 將輸入空間映射到表的索引范圍。也就是說，給定輸入 i，現(xiàn)在將關(guān)鍵字 i 設(shè)置為1。當(dāng)然，我們會注意哈希沖突。這里顯然有一個權(quán)衡，最初，添加額外的哈希函數(shù)可以減少出現(xiàn)假陽性的機(jī)會，然而，隨著越來越多的哈希函數(shù)被添加，位數(shù)組中的1個值越來越多，因此更有可能發(fā)生沖突。這種權(quán)衡可以通過數(shù)學(xué)方法進(jìn)行分析，通過假設(shè)哈希函數(shù)看起來完全是隨機(jī)的 ，并通過查看不在集合中任意元素存在的幾率來進(jìn)行工作。

如果在一個大小為 m 的布隆過濾器中存儲了 n 個不同的項，并且使用了 k 哈希函數(shù)，那么一個成員資格查詢得到一個假陽性結(jié)果的機(jī)會大約是 exp (k ln (1 exp (kn/m)))。一些簡單的分析表明，通過選擇 k = (m/n) ln 2，這個比率可以最小化，即過濾器中大約一半位為1，一半位為0的情況相對應(yīng)。

為了實現(xiàn)這一點，過濾器中的位數(shù)應(yīng)該是存儲在其中的記錄數(shù)的幾倍。一個常見的設(shè)置是 m = 10n 和 k = 7，這意味著假陽性率低于1% 。請注意，這里沒有魔法可以壓縮超出信息理論限制的數(shù)據(jù)，在這些參數(shù)下，布隆過濾器每個條目使用約10位，并且必須使用與存儲的不同條目數(shù)量成比例的空間。當(dāng)表示整數(shù)值時，這是一個適度的節(jié)省，但是當(dāng)存儲項具有大的描述符(比如 url 等任意字符串)時，這是一個相當(dāng)大的好處。因為，將這些數(shù)據(jù)存儲在傳統(tǒng)的結(jié)構(gòu)中，比如哈希表或平衡搜索樹，每個項目將消耗數(shù)十或數(shù)百個字節(jié)。

當(dāng)一個假陽性的結(jié)果不是在計算中引入一個錯誤，而只是一些額外的工作，并且不對系統(tǒng)的整體性能產(chǎn)生不利影響時，布隆過濾器是最有吸引力的。一個很好的例子來自于瀏覽網(wǎng)頁的場景，如果用戶試圖訪問一個已知的惡意站點時，Web 瀏覽器通常會警告用戶。簡單對比“惡意”URL 數(shù)據(jù)庫檢查 URL 就可以做到這一點，但是需要數(shù)據(jù)庫足夠大，把完整的數(shù)據(jù)庫作為瀏覽器的一部分是很難操作的，尤其是在移動設(shè)備上。相反，數(shù)據(jù)庫的布隆過濾器編碼可以包含在瀏覽器中，每個訪問過的 URL 都可以根據(jù)它進(jìn)行檢查。糟糕的結(jié)果只是瀏覽器可能認(rèn)為一個無辜網(wǎng)站在黑名單上，為了處理這個問題，瀏覽器可以聯(lián)系數(shù)據(jù)庫并檢查列表中是否有完整的 URL，以遠(yuǎn)程數(shù)據(jù)庫查找為代價來消除誤報。布隆過濾器為大多數(shù) URL 提供所有信息，并且對一小部分url產(chǎn)生輕微的延遲。這比在瀏覽器中保存數(shù)據(jù)庫副本的解決方案和對每個 URL 進(jìn)行遠(yuǎn)程查找都要好的多，像 Chrome 和 Firefox 這樣的瀏覽器就采用了這個概念。

布隆過濾器是在1970年作為一種緊湊存儲字典的方式引入的，當(dāng)時的內(nèi)存很珍貴。隨著計算機(jī)內(nèi)存的增長，似乎不再需要它了。然而，隨著網(wǎng)絡(luò)的迅速發(fā)展，已經(jīng)出現(xiàn)了許多布隆過濾器的應(yīng)用，許多大型分布式數(shù)據(jù)庫(Google 的 Bigtable、 Apache 的 Cassandra 和 HBase)都使用布隆過濾器作為分布式數(shù)據(jù)塊的索引。它們使用過濾器來跟蹤數(shù)據(jù)庫的哪些行或列存儲在磁盤上，從而避免對不存在的屬性進(jìn)行磁盤訪問。

Count-min

也許規(guī)范的數(shù)據(jù)匯總問題是最不重要的，一個簡單的計數(shù)器就足夠了，每觀察一次就增加一次。計數(shù)器必須有足夠的位深度，以應(yīng)付所觀察到的事件的大小。當(dāng)存在不同類型的數(shù)據(jù)項時，如果希望計算每個類型的數(shù)量時，自然的方法是為每個項分配一個計數(shù)器。然而，當(dāng)項目類型的數(shù)量增長巨大時，會遇到困難，為每個項目類型分配一個計數(shù)器可能不實用，當(dāng)計數(shù)器的數(shù)量超過內(nèi)存的容量時，遞增相關(guān)計數(shù)器的時間成本可能會變得過高。例如，社交網(wǎng)絡(luò)可能希望跟蹤一條記錄在外部網(wǎng)站顯示的頻率，有如果數(shù)十億個網(wǎng)頁，每個網(wǎng)頁原則上都可以鏈接到一個或多個記錄，因此為每個網(wǎng)頁分配計數(shù)器是不可行的，也是不必要的。尋找一種更緊湊的方式來對項目計數(shù)進(jìn)行編碼是很自然的事情，盡管可能會失去一些精確度。

Count-Min 也是一種數(shù)據(jù)結(jié)構(gòu)，允許進(jìn)行這種權(quán)衡，它在一個小數(shù)組中對大量的記錄類型進(jìn)行編碼。保證大的計數(shù)將被相當(dāng)準(zhǔn)確地保存，而小的計數(shù)可能會有誤差。Count-Min 由一組計數(shù)器和一組哈希函數(shù)組成，這些函數(shù)將數(shù)據(jù)項映射到數(shù)組中。乍一看，很像布隆過濾器，但在細(xì)節(jié)方面存在著顯著的差異。確切地說，數(shù)組被視為一個行序列，每個項目由第一個哈希函數(shù)映射到第一行，由第二個哈希函數(shù)映射到第二行，以此類推，并遞增映射到的計數(shù)器。注意，這與 布隆過濾器不同，后者允許哈希函數(shù)映射到重疊的范圍。

對于給定的一個數(shù)據(jù)項，Count-min允許對其計數(shù)進(jìn)行估計: 檢查第一行中由第一個哈希函數(shù)映射項的計數(shù)器，以及第二行中由第二個哈希函數(shù)映射項的計數(shù)器，依此類推。每一行都有一個計數(shù)器，該計數(shù)器已按該項的每次出現(xiàn)次數(shù)遞增。但是，由于預(yù)期會發(fā)生沖突，計數(shù)器還可能因映射到同一位置的其他項。給定包含所需計數(shù)器和噪聲的計數(shù)器集合，將這些計數(shù)器中的最小值作為估計值。

Count-min也實現(xiàn)了輸入數(shù)據(jù)的緊湊表示，并在精確度上進(jìn)行了權(quán)衡。如果使用布隆過濾器，答案是二進(jìn)制的，所以有可能出現(xiàn)假陽性; 使用 Count-Min ，答案是頻率，所以有可能出現(xiàn)一個被夸大的滅國。Count-Min 最適合處理輕微的頻率膨脹，不適用于可能使用 布隆過濾器的情況，如果一個數(shù)據(jù)項是否存在非常重要，那么 Count-Min 引入的不確定性將掩蓋這種精確程度。但是，count-min 非常適合跟蹤哪些數(shù)據(jù)項超過了給定的流行度閾值。Count-Min 具有更大的壓縮性，它的大小可以被認(rèn)為與輸入大小無關(guān)，而只取決于所期望的精度保證。

自問世以來，Count-Min 已在跟蹤頻率統(tǒng)計數(shù)據(jù)的系統(tǒng)中有了廣泛的應(yīng)用，例如不同群體的內(nèi)容流行程度、不同用戶群體中在線視頻的流行程度，以及通信網(wǎng)絡(luò)中的流行節(jié)點。網(wǎng)絡(luò)流量的摘要分布可以檢測到熱點，為網(wǎng)絡(luò)規(guī)劃的決策提供了信息，也可以用來檢測何時發(fā)生了流行趨勢的變化，作為簡單的異常檢測。

HyperLogLog

如何跟蹤在大量的可能性中有多少不同的項目呢?例如，Web 網(wǎng)站可能希望跟蹤有多少不同的人接觸到了特定的廣告。在這種情況下，不希望對同一個用戶瀏覽進(jìn)行多次計數(shù)。當(dāng)記錄項數(shù)量不太大時，保持一個列表或二進(jìn)制數(shù)組是一個自然的解決方案。當(dāng)可能的項目數(shù)量變得非常大時，這些方法所需的空間與所跟蹤的項目數(shù)量成正比。能指望做得更好嗎?

HyperLogLog 承諾了更強(qiáng)大的功能，成本只需依賴于計算量的對數(shù)。當(dāng)然，也有一些縮放常數(shù)，這意味著所需的空間并不像表示的那么小，但最終的結(jié)果往往只需要幾K字節(jié)的空間，就可以高精度地估計數(shù)量。HyperLogLog的本質(zhì)是使用應(yīng)用于數(shù)據(jù)項標(biāo)識符的哈希函數(shù)來確定如何更新計數(shù)器，以便對重復(fù)項進(jìn)行相同的處理。對每個數(shù)據(jù)項 i 應(yīng)用一個散列函數(shù) g，g 以2j 的概率將數(shù)據(jù)項映射到 j ，例如，在均勻的二進(jìn)制展開式中取前導(dǎo)零位的數(shù)目。然后可以保留一組位標(biāo)識，指示到目前為止已經(jīng)得到的那些j 值。這里只需要一個對數(shù)位數(shù)，因為只需要這么多不同的 j 值。HyperLogLog方法只保留應(yīng)用哈希函數(shù)時看到的最大 j 值，從而進(jìn)一步減少了位數(shù)。這可能與基數(shù)相關(guān)，為了減少這種變化，使用第二個哈希函數(shù)將項分成組，因此同一項總是放在同一組中，并保留關(guān)于每個組中最大哈希的信息。每個組都會產(chǎn)生估計值，這些估計值都被組合起來以獲得總基數(shù)的估計值。方法是計算估計值的平均值，使用調(diào)和平均值來減少這種影響。算法的分析具有一定的技術(shù)性，但該算法已被廣泛采用并在實踐中應(yīng)用，例如Redis。

HyperLogLog 的一個典型示例就是跟蹤在線廣告的收視率。在許多網(wǎng)站和不同的廣告中，每天可能發(fā)生數(shù)以萬億計的觀看事件。廣告商感興趣的是有多少不同的人接觸過這些內(nèi)容。收集和傳輸這些數(shù)據(jù)并不是不可行的，只是相當(dāng)笨拙，特別是如果希望執(zhí)行更高級的查詢(例如，計算有多少獨立訪問者同時看到兩個特定的廣告)。HyperLogLog使得這種查詢可以直接得到答案，而不是通過搜索整個數(shù)據(jù)。近似差異計數(shù)在 web 系統(tǒng)中也被廣泛使用，例如，谷歌的廣告系統(tǒng)提供了不同的計數(shù)，作為日志數(shù)據(jù)分析的原語。

小結(jié)

在處理大型高維數(shù)值數(shù)據(jù)時，通常尋求在保持?jǐn)?shù)據(jù)逼真度的同時降低維數(shù)。假設(shè)數(shù)據(jù)處理和建模的艱苦工作已經(jīng)完成，數(shù)據(jù)可以被建模為一個巨大的矩陣，其中每一行是一個樣本點，每一列編碼為數(shù)據(jù)的一個屬性。一種常用的技術(shù)是應(yīng)用 PCA從數(shù)據(jù)中提取少量的“方向”，沿著每個方向的每一行數(shù)據(jù)會產(chǎn)生不同的數(shù)據(jù)表示形式，這些表示形式可以捕獲數(shù)據(jù)集的大部分變化。其局限性是需要找到協(xié)方差矩陣的特征向量，這對于大型矩陣來說就變得不可持續(xù)。與其尋找“最佳”方向，不如使用(數(shù)量稍大的)隨機(jī)向量。數(shù)據(jù)矩陣的每一行的隨機(jī)投影可以看作是數(shù)據(jù)摘要的一個例子。更直接的是，Count-Min 可以被看作是各種類型的隨機(jī)投影，這是加速高維機(jī)器學(xué)習(xí)方法的基礎(chǔ)，例如哈希核函數(shù)方法。

數(shù)據(jù)摘要的一個目標(biāo)是允許任意復(fù)雜的大量數(shù)據(jù)上快速得到近似結(jié)果。一些核心的數(shù)學(xué)運算可以通過數(shù)據(jù)摘要的思路來解決，例如隨機(jī)數(shù)值線性代數(shù)。一個簡單的例子是矩陣乘法矩陣: 給定兩個大矩陣 A 和 B，找到它們的乘積 AB。一種數(shù)據(jù)摘要方法是為A 的每一行和 B 的每一列建立一個降維的數(shù)據(jù)摘要，提供一個估計。在這個領(lǐng)域中已解決的問題包括了回歸。這輸入是一個高維數(shù)據(jù)集，建模為矩陣 A 和列向量 b， A的每一行都是一個數(shù)據(jù)點，b 的相應(yīng)條目是與該行關(guān)聯(lián)的值, 目標(biāo)是找到最小二乘法的回歸系數(shù) x。這個問題的精確解是可能的，但是時間上的開銷與行的數(shù)量有關(guān)，而在矩陣 A上應(yīng)用數(shù)據(jù)摘要可以解決低維空間的問題。

對于圖，有一些技術(shù)可以概括每個節(jié)點的鄰接信息，從而可以提取連通性和生成樹信息。對于幾何數(shù)據(jù)來說，解決聚類等問題的輸入可以捕獲大量的總體結(jié)構(gòu)信息，通過將聚類合并在一起，也可以保留整體點密度分布的良好特征。

一般地，簡單的方法可以提供準(zhǔn)確的答案，但需要保留完整的信息。而在許多情況下，近似方法可以更快，更節(jié)省空間。布隆過濾器有時被認(rèn)為是“大數(shù)據(jù)分析”必須掌握的核心技術(shù)之一，通常，基于快速數(shù)據(jù)摘要的技術(shù)可以提供不同的折衷。