舊事件何時失效
累積總數回答的是「至今出現多少事件」,卻不能回答「過去一小時出現多少事件」。如果我們已丟棄每個事件的時間,就不能在它過期時準確扣除。保存視窗內每一個位元可得到精確答案,但長度為 的視窗需要 位元。當可接受受控的相對誤差時,摘要可以節省空間。
定義 17.1.1
(有效視窗與真實計數)
輸入是在整數時刻到達的二元數據流 。固定整數 和 。處理完時刻 後,有效視窗由正整數時刻 組成,其真實計數為 。若 ,稱時刻 的 1 在時刻 已過期。
即使輸入為零,時間仍向前推進。以下保證對每條數據流都成立,無須隨機輸入、雜湊或獨立性假設。
桶與更新程序
定義 17.1.2
(桶摘要)
一個桶表示按時間排列的 1 事件中連續的一段;這些事件的時間不必連續。桶儲存其大小(2 的冪)和其中最新的 1 的時間戳。桶摘要是一列桶:由舊至新,它們把尚未完全丟棄的 1 分成不重疊的段,而且桶大小不遞增。
一個桶可以同時包含已過期與有效的 1,但只有最舊的保留桶可能跨越視窗邊界。
時刻 的位元到達後,按次序執行:
- 丟棄最新時間戳不大於 的每個桶,因為其中所有事件已過期。
- 若 ,在末尾加入大小為 1、時間戳為 的桶;若為零則不加入。
- 當某個大小的桶超過 個時,選擇其中最小的大小,合併該大小中最舊的兩個桶。新桶大小加倍,時間戳取原先較新的時間戳。重複直至每種大小最多有 個桶。
相同大小的桶在不遞增次序中排成連續的一段,因此選出的兩個桶相鄰。用其聯集取代二者後,時間次序及大小不遞增的性質仍然成立。每次合併減少一個桶,故迴圈終止。更新時先丟棄完全過期的桶;跨邊界的桶仍有有效事件,必須保留。
查詢時,加總最舊桶以外所有桶的大小;若最舊桶大小為 1,額外加 1,否則額外加它大小的一半。記結果為 ;沒有桶時輸出零。每個比最舊桶新的桶都完全在視窗內:它最舊的事件也比最舊保留桶中最新的事件更晚,而後者仍然有效。
定理 17.1.3
(確定性誤差與空間界)
對每條二元數據流及每個時刻 ,上述估計滿足
若 ,估計精確為零。最多儲存 個桶。若運行至有限時刻 ,以絕對時間戳儲存各桶所需空間為 位元。
證明
(同伴質量,然後誤差與空間)
同伴質量。 大小 的桶,是在大小 的桶至少有 個時,合併其中最舊的兩個而成。建立時,它後面至少還有 個同樣大小的桶,共含至少 個 1。其後合併只改變分組,不會消除這些事件;只要該桶仍是最舊的保留桶,它最新的 1 仍有效,所有更晚的這些事件亦必然有效。因此無論後來如何分組,真實計數至少包含這些較新的事件。
誤差。 若沒有保留桶,所有曾儲存的 1 均已過期;先前丟棄的桶在丟棄時亦已完全過期,所以 。若最舊桶大小為 1,其唯一事件有效,其他桶也全部有效,因此估計精確。否則設其大小為 ,其中 個 1 有效。最新事件有效,所以 。其他桶均被精確計數,故絕對誤差為 。上面的同伴論證給出 ,故 ,從而得到相對誤差界。
空間。 若最舊桶大小 ,它後面的同伴都在長度為 的視窗內,因此 ,亦即 。其餘桶不比它大,故所有桶的大小均不超過 。大小是由 1 起的 2 的冪,可能種類最多為 ,每種最多有 個桶,證得桶數界。有限運行至 時,絕對時間戳需要 位元,已儲存桶的大小亦可用同階位元表示。此結論不計外部輸入儲存,也不聲稱每次更新的最壞時間是常數。
證明透視
合併規則為最舊桶的不確定性買單
估計中唯一的不確定之處,是最舊桶有多少個 1 仍有效;較新的桶都被精確計數。所以證明只需要一條不等式:以最舊大小 給真實計數一個下界,而合併規則正好提供它。規則有兩處被用到。只在某大小超過 個時才合併,保證建立時仍剩 個同大小的桶。合併的是最舊的兩個,保證這些剩下的桶較新,所以只要合併所得的桶仍被保留,它們就仍然有效。過期條件透過最新時間戳進入:保留的桶有一個有效的最新事件,這給出 ,並把同伴留在視窗內。空間界把同一不等式與視窗長度比較,得 ;誤差與記憶體都由同一個計數事實控制。
第一個例子在一段短輸入上追蹤更新規則,其中包括一次過期。
例題 17.1.4
(過期與半桶估計)
取 、,連續輸入六個 1。時刻 1、2、3 過後,時間 1 和 2 的單例桶合併,狀態是 ;每對數字表示(大小,最新時間戳)。時刻 4 的狀態是 。時刻 5 合併最舊的兩個單例,得到 。時刻 6 的截止點為 ,故丟棄最新時間戳為 2 的桶,得到 。估計為 ,但時刻 3 至 6 的真實計數為 4;誤差 1 小於一般界 。這個例子中最舊保留桶恰巧全在視窗內,但單憑其最新時間戳無法知道這點。
例題 17.1.5
(連鎖合併及其同伴)
取 、,連續輸入七個 1。如上,時刻 5 後的狀態是 ,時刻 6 加入 。時刻 7 的截止點為 ,沒有桶過期。加入 後有三個單例,於是 合併為 。此時大小 2 有三個桶 ,最舊兩個合併為 。最終狀態為 。桶 建立時有 個較新的大小 2 同伴,即 ,其質量為 。估計為 ,真實計數為 ;誤差 不超過 ,亦不超過 。
例題 17.1.6
(邊界情況:所有 1 都過期)
取 、,輸入 。時刻 2 後的狀態是 。時刻 3 的截止點為 ,丟棄 ,剩下 ;估計 等於 。時刻 4 的截止點為 , 亦被丟棄。摘要為空,輸出零,正等於 ,符合定理要求。兩個零沒有建立任何桶,卻各自使截止點前進。
反例模式
最新時間戳不能告訴我們邊界如何切分
取 、,比較到時刻 6 的歷史 和 。兩者摘要都是 :第一條數據流的大小 2 桶包含時刻 3、4,第二條則包含時刻 2、4。但視窗計數分別是 3 和 2,所以同一摘要不能同時給出兩者的精確答案。把每個保留桶全部計入會高估第二個歷史。
常見錯誤
(只在 1 到達時才執行過期步驟)
零不建立桶,但仍推進時間,而過期取決於時間。若實作只在 時丟棄桶,上面邊界情況的例子在時刻 4 後仍保留 兩個桶,回答 而不是 。丟棄步驟必須在每個時刻都執行。
如何使用這個界
增加 可改善已證明的相對誤差界,但會增加儲存量。若要求 的相對誤差,取 便足以保證誤差不超過 ;這是充分選擇,並非最優性的證明。方法估計的是 1 的個數,並非任意帶符號或加權數值的總和。它把到達次序當成事件時間;遲到事件和刪除任意過往事件需要另一套約定。重複到達會被計算兩次;若不同摘要的事件重疊,也不能直接把估計相加。
此界有意保守:即使最舊桶完全在視窗內,只要其大小大於 1,我們仍只計一半。額外儲存最舊時間戳可辨認部分完全有效的桶,但一般仍不能確定有多少內部事件跨過邊界。
常見錯誤
(把半桶估計讀成對切分的斷言)
半桶估計是使用現有資訊所得的保證,並非假設實際恰有一半事件過期。在第一個例子中,最舊桶完全有效,卻被計為 而不是 。保證針對的是所有具相同摘要的歷史中的最壞情況。
練習與解答
快速檢查
(取 、,輸入 。列出時刻 4 的桶與估計。)
加入新桶前先檢查截止點 。
解答 · 答案
時刻 3 的狀態為 。時刻 4 的截止點為 1,沒有桶過期;加入 後得到 。估計為 ,真實計數也是 3。
快速檢查
(取 、,輸入 。求時刻 6 的狀態和計數。)
零仍會移動截止點。
解答 · 答案
時刻 5 的截止點為 2,丟棄 ,剩下 。時刻 6 的截止點為 3,丟棄 ,剩下 ;估計及真實計數均為 1。零不建立桶,但仍使截止點前進。
快速檢查
(若要保證相對誤差不超過 ,當 時,給出可用的 和桶數界。)
用 及定理中的桶數界。
解答 · 答案
取 ,因為 。由 ,定理給出最多 個桶。這只是上界,並非聲稱所有桶可同時出現。
快速檢查
(若最新時間戳等於 的桶仍被保留,為何違反上述更新規則?將其全部計入可能有何問題?)
與視窗定義中的嚴格不等式比較。
解答 · 答案
有效時間滿足嚴格不等式 ,該桶所有事件均已過期;全部計入會包含舊事件。例如 時,時刻 1 的唯一一個 1 在時刻 2 已不應計入。
快速檢查
(若實作改為合併兩個最新的同大小桶,哪一步證明失效?)
看同伴相對於合併所得桶的位置。
解答 · 答案
合併後未必有 個同大小桶在新桶之後。較舊的同伴可能在新桶仍有效時過期,所以不能再推出有效的較新事件數量下界。這只說明需要另一個證明,並未確定替代算法的實際誤差。