在許多計算設置中，相同信息的超載是一個需要關注的問題。例如，跟蹤其網絡應用以識別整個網絡的健康狀況以及現場異?；蛐袨樽兓?。然而，事件發生的規模是巨大的，每個網絡元素每小時可能會發生數以萬計的網絡事件。雖然技術上允許監控事件的規模和粒度在某個數量級內的增加，但是，處理器、內存和磁盤理解這些事件的能力幾乎沒有增加。即使規模很小，信息量也可能過大，無法方便地放在存儲中。

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

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

抽樣

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

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

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

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

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

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

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

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

布隆過濾器

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

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

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

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

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

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

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

Count-min

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

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

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

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

自問世以來，Count-Min 已在跟蹤頻率統計數據的系統中有了廣泛的應用，例如不同群體的內容流行程度、不同用戶群體中在線視頻的流行程度，以及通信網絡中的流行節點。網絡流量的摘要分布可以檢測到熱點，為網絡規劃的決策提供了信息，也可以用來檢測何時發生了流行趨勢的變化，作為簡單的異常檢測。

HyperLogLog

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

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

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

小結

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

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

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

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