動機
數據流中的更新數量可能遠超能夠逐條儲存的規模。如果元素全集很大,為每一個可能的元素維持一個精確計數器同樣成本高昂。Count–Min 草圖使用一個由若干共用計數器組成的小陣列。當更新均為非負時,雜湊碰撞只會令估計值增大;而多行互相獨立的計數器使較大的高估變得不太可能發生。
該保證是相對於數據流總權重的加性誤差,並不是對每個罕見元素都成立的相對誤差保證。我們先對一個固定的查詢,以及一個獨立於草圖隨機雜湊而選定的更新流證明結果,然後說明如何對有限個查詢得到同時成立的保證。
定義
設 為有限的元素全集。數據流由若干更新 組成,其中 ,增量 為非負整數。設 為元素 收到的增量總和,並設 為數據流的總權重。計數均為精確的非負整數;零增量無害。
選取寬度 與深度 。對每一行 ,從滿足下列條件的雜湊函數族中隨機選取雜湊函數 :
各行互相獨立。這一碰撞性質可由均勻的兩兩獨立雜湊值推出,但證明只需要每一行內部所顯示的碰撞概率界。我們假定所述函數族可以被抽樣並求值;它的表示方式與計算成本屬於另外的實現要求。
維持計數器 ,初始為零。收到更新 時,在每一行中把 加到 上。對於查詢元素 ,返回
定理
定理 10.2.1
(固定查詢的 Count–Min 保證)
對 與 ,取 與 。對任意固定的非負數據流與固定的查詢 (二者均獨立於雜湊函數),有
定理 10.2.2
(有限個查詢的同時保證)
對於固定的、含 個查詢元素的集合 ,取深度 ,則它們的所有估計值以至少 的概率同時滿足相同的加性誤差界。
證明:單行
證明
(單行的誤差)
固定 與某一行。該行中被查詢的計數器包含對 的全部更新,以及對與 發生碰撞的其他元素的更新。定義非負的碰撞雜訊
於是 。由於增量非負,這一不等式對每一種雜湊結果都成立。對各行取最小值同樣不會產生低估。
由期望的線性性與碰撞概率界,
對不同的 ,其碰撞指示變量不必互相獨立;只需要各自的概率以及線性性即可。若 ,馬爾可夫(Markov)不等式給出
若把嚴格不等號換成非嚴格的閾值,同樣的界仍然成立。若 ,則所有計數器與真實頻率均為零,結論顯然成立,無需在零閾值處應用馬爾可夫不等式。
證明:獨立的行與查詢
證明
(對行與查詢的放大)
對固定的數據流與查詢,第 行的雜訊只取決於該行的雜湊函數。各行互相獨立,因此「各行雜訊超過 」這些事件互相獨立。僅當每一行的雜訊都過大時,最小估計值才會超過 。其概率至多為 。再結合確定性的「不會低估」性質,即證明了固定查詢的界。
對於固定的 個查詢元素,在逐個查詢的計算中把 換成 。所選的深度使每個查詢失敗的概率至多為 。由聯集界,任一查詢失敗的概率至多為 。各查詢的失敗事件可以互相依賴;聯集界並不要求它們之間獨立。
證明透視
概率的兩種用法
各假設用在哪裏:增量非負給出確定性的 ,並使 非負,從而可用馬爾可夫不等式。碰撞界只透過期望的線性性使用,所以 不需要碰撞項之間相互獨立。關鍵一步分兩層:馬爾可夫不等式把均值化為單行的常數失敗概率 ,獨立的各行再把它提升到 次冪。對多個查詢,用聯集界代替獨立性,所以深度只隨 對數增長。若流或查詢是在看到雜湊之後才選定,「流與查詢固定」的前提便不成立,論證不再適用。
例題詳解
例題 10.2.3
(一次碰撞)
設數據流的頻率為 、,且某一行把 與 雜湊到同一個桶。該行中 被查詢的計數器為七,故其碰撞雜訊為三。另一行把二者分開,其計數器為四,兩行計數器的最小值即為精確頻率四。
例題 10.2.4
(零數據流)
若所有增量均為零,則 ,且每個計數器保持為零。每個查詢都返回其真實頻率零。此時無需除以 。
例題 10.2.5
(選取維度)
取 與 ,按所述取法得 ,。對固定的查詢,加性誤差大於 的概率至多為 。這是對固定數據流的最壞情況界,並不是說典型誤差就等於 。
例題 10.2.6
(罕見元素)
若 、 且 ,則該保證容許估計值高達 。相對於 而言這是較小的加性誤差,但對 本身卻是很大的相對誤差。該定理對罕見元素不提供任何乘性保證。
常見錯誤
反例模式
負更新會破壞單側性
設 ,另有一個元素 對與 共用的桶貢獻了 的負更新。該行計數器可能為 ,低於 的真實頻率。取最小值無法修復所聲稱的確定性下界。該定理假設增量非負。
常見錯誤
(把固定輸入的保證用於自適應的流)
概率陳述要求數據流與查詢的選取獨立於隨機雜湊。如果對手能夠檢視草圖,並根據雜湊結果選擇後續更新或查詢,則上述針對固定輸入的計算並不會自動適用。自適應情形的保證需要另外的模型與證明。
常見錯誤
(用平均值代替最小值)
取最小值對放大論證至關重要:只要至少有一行的碰撞雜訊較小,最小值就較小。對計數器取平均則是另一種估計量,需要另行分析。
概念視角代數
草圖是頻率向量的線性像
設 為頻率向量。計數器滿足 ,其中 是 - 矩陣,每個行塊的每一列恰有一個 ,位於桶 。因此兩個數據流合併後的草圖等於它們草圖之和,而 中的第二項正是碰撞雜訊。
空間與更新成本
草圖儲存 個整數計數器。每次更新計算 個雜湊並遞增 個計數器;每次查詢計算 個雜湊並取最小值。在常數時間雜湊與字長計數器運算的假設下,每次更新或查詢需要 時間。如果計數可能超過一個機器字,則必須計入其位長與算術成本。雜湊函數的描述同樣佔用空間,對具體的函數族必須一併計算。
按所給參數取法,,,因此共有 個計數器。這是計數器的個數,並不自動等於相同數量的位元。在非負數據流模型中,每個計數器必須能表示至多 的數值。
具體實現必須使用具有所述概率的碰撞函數族、互相獨立的各行選擇,以及與全集相容的表示方式。由完全獨立的雜湊值構成的理想化表在數學上有效,但可能需要與 成正比的空間。該定理把草圖分析與這一構造成本分開處理。
有限設定下的一個具體碰撞函數族
設全集是有限域 ( 為質數)的子集,並取草圖寬度恰為 。從 中獨立且均勻地選取 ,定義域中的 ,並把其 個值與桶標籤等同起來。對於互異的 ,發生碰撞意味著 。由於域中 ,這恰好在 時發生,概率為 。
事實上,這兩個雜湊值是聯合均勻的。對任意給定的輸出 ,方程 與 有唯一解:,。因此,在等可能的 種 取法中,每個輸出對恰好出現一次。對每一行獨立地選取這兩個域元素,便得到互相獨立的各行函數。
這一構造說明了該假設如何成立,但它並不是一般的壓縮全集方案:它要求把 單射地表示到大小為 的域中,並使用 個桶。特別地,若 ,所得寬度可能過大,以致相比精確計數器並不節省空間。更小寬度的實用函數族需要自行證明所需的碰撞概率界;簡單地把域中的值對一個無關的桶數取模可能引入偏差。
追蹤計數器
考慮寬度為三的兩行草圖。設第一行把 雜湊到桶 ,第二行把它們雜湊到 。依次處理更新 、 與 。第一行計數器變為 ,第二行計數器變為 。查詢 時讀到五與二,返回二,即其精確頻率。查詢 時讀到五與七,返回五,比真實值三高估了二。查詢 時讀到四與七,返回四,即其精確頻率。只要另一行把被查詢的元素與和它碰撞的元素分開,某一行中的碰撞就不一定導致最小值出錯。
這個例子區分了某個具體的雜湊結果與概率保證。該定理並不保證每一種雜湊選擇都給出小誤差;它界定的是:對固定的數據流與查詢,在所述的隨機行選擇之下,出現大誤差的概率。對於這個小例子的寬度與深度,我們並未斷言任何具體的數值失敗概率保證。
馬爾可夫不等式的推導與使用
對非負隨機變量 與 ,逐點不等式 給出 。整理即證明馬爾可夫不等式。這裏由於更新非負, 非負,故該論證適用於碰撞雜訊。總權重為零的特殊情形直接處理,因為此時閾值 為零。
該定理界定的是 。如果估計值恰好等於上邊界,它仍然滿足保證。即使 不是整數,在馬爾可夫不等式中使用非嚴格閾值,也能為嚴格失敗事件給出有效的上界。
對於預先確定的 個查詢,聯集界控制了其中任何一個失敗的事件。該集合可以取為整個有限全集,當 非空時成本是深度取 。這一同時保證在同一個高概率事件上對所有這些元素成立。它並不自動涵蓋在觀察草圖之後改變數據流的、無界的自適應更新序列。
解讀參數的取捨
增大寬度會降低每一行的期望碰撞雜訊;增大深度會降低每一行都出現大碰撞的概率。這兩種效應出現在證明的不同部分。如果不控制單行雜訊而只把深度加倍,並不能由此單獨建立所述閾值;而只加寬單獨一行,也不會產生同樣的指數式置信度放大。
常數 與取整的選擇只是方便的充分取值。只要 ,其他的寬度與深度可以直接依據界 來分析。使用不同的常數可能改變數值上的空間界,但證明結構保持不變。參數公式中的所有對數均為自然對數。
總結
一行計數器等於真實頻率加上非負的碰撞雜訊。碰撞性質界定了期望雜訊,馬爾可夫不等式界定單行的失敗概率,而互相獨立的各行則放大了「至少有一行準確」的概率。聯集界把結果推廣到任意固定的有限查詢集合。
練習
快速檢查
(為甚麼在更新非負時,估計值永遠不會低於真實頻率?)
每一行在真實頻率之上加了甚麼量?
解答 · 答案
每個被查詢的計數器包含對被查詢元素的全部更新,加上來自碰撞元素的非負貢獻。一組都至少為 的數的最小值仍然至少為 。
快速檢查
(若某一行的期望碰撞雜訊至多為 ,當 時,馬爾可夫不等式對雜訊超過 給出甚麼界?)
對碰撞雜訊應用馬爾可夫不等式。
解答 · 答案
至多為 。
快速檢查
(為甚麼在所給出的指數式失敗概率計算中需要各行之間互相獨立?)
各行的失敗概率是如何合併的?
解答 · 答案
證明把「每一行雜訊都過大」的概率相乘。對於固定的數據流與查詢,這一相乘由各行雜湊函數互相獨立來保證;相關的各行可能同時失敗。
快速檢查
(對於 個固定查詢,要使總失敗概率至多為 ,應如何選取每個查詢的失敗概率預算?)
把總失敗預算分配給各查詢。
解答 · 答案
對每個查詢使用至多 的失敗概率。由聯集界,總失敗概率至多為 。