數據流概要數據的合并性研究分析

摘 要：本文研究了數據流概要數據的合并性，合并性就是給出兩個數據集上的兩個數據概要，存在一種方法可以將兩個概要合并成兩個數據集并集上的單一概要信息，同時不增加概要的大小或其近似誤差，并可應用于數據流的近似處理查詢。

關鍵詞：數據流；概要；合并性

1 引言

數據概要對于大規模數據集查詢是一個重要的手段，尤其是數據分布在網絡中或是動態變化的，依據全部數據進行計算是無法實行的。在這種情況下，計算數據集D上的一個簡潔的概要是可行的，且其保留了它的重要屬性，同時可以使用概要來回答查詢，而且占用資源少得多。由于概要具有更小的尺寸，還可以近似的回答查詢，同時在概要的大小和近似誤差之間存在一個權衡。目前各種各樣的概要都被提出，像heavy hitters、分位數概要、柱狀圖、各種略圖和草圖的統計概要，像ε-近似和ε-內核的幾何概要，像distance oracles的圖形概要。注意對于不同類型的概要，誤差參數ε總有不同的解釋。

2 數據概要的合并性

合并性就是指給出兩個數據集上的兩個數據概要，存在一種方法可以將兩個概要合并成兩個數據集并集上的單一概要信息，同時不增加概要的大小或其近似誤差。這個性質意味著數據概要也可以像Sum和Max聚合函數那樣的代數運算一樣可以通過某種方法合并。幾類數據概要可以通過構造直接合并，最明顯的就是略圖，其是具有線性功能的數據集，但是其他的像heavy hitters和分位數一些基本的概要不能被合并。具體來說，對于ε-近似heavy hitters來說，存在一個大小為o（1/ε）的確定的合并概要；對于ε-近似分位數來說，存在一個大小為 的具有受限制的合并性質的確定概要和大小為 具有完全合并性質的隨機概要。這個成果也可以應用到幾何概要中，例如ε-近似和ε-內核。

3 概要合并的應用

⑴分布式計算。合并操作是由MUD（大規模無序分布）模型計算所引起，其描述了大規模分布式編程范例像MapReduce和Sawzall。在這種模型中，輸入數據被分解成任意塊，其中的每個塊可能由不同的機器來處理。每塊數據第一次由本地函數處理，輸出信息，然后所有的這些在任意形式下使用聚合函數兩兩組合，最終產生一個總體信息。最后應用后期處理步驟，這實際上相當于合并性的概念，其中每臺機器建立一個共享輸入的概要，聚合函數就是合并操作，后期處理步驟相當于形成關于概要的查詢。主要結論就是任何定義在所有輸入上的計算對稱函數的確定性流算法都可以由MUD算法來模擬，但這個結論并不適用于不確定性函數，即函數可能由許多正確的輸出。許多概要計算的流行算法都是不確定性的，所以這個結論并不適用于所有案例。

⑵網絡聚合。在傳感器網上的節點組織成一個路由樹，根在基站。每個傳感器都有一些數據且數據聚合的目標是為了計算所有數據的概要。幾乎所有的數據聚合算法都遵循一個自底向上的方法：從葉子開始，聚合傳送到根。當一個節點收到來自它的孩子的概要，它將會把它們合并成自己的概要，并將結果傳送到它的父親。根據傳感器的物理分布，路由樹可能是任意形狀。如果概要的大小不依賴于|D|，那么這將形成負載均衡，沿著每個分支的通信是相同的，而不是將更多的負載放在靠近根部的邊上。

4 合并算法描述

出于以上及其他方面的應用，本文提出了有效的合并算法。其中用是S（）來表示一個概要方法，涉及D和誤差參數ε，s（）可能由許多有效輸出（即根據處理D的順序，它可能返回不同有效ε-概要），即s（）可能是一對多的映射。用S（D，ε）來表示數據集D的任意有效概要，且具有由這些方法產生的誤差ε，同時用k（n，ε）表示包含N個項目的數據集D的任意S（D，ε）的最大尺寸。

如果存在一個算法A，它能從任意兩個輸入概要S（D1，ε）和S（D2，ε）產生一個概要S（D1 D1，ε），那么就說S（）是可以合并的。

通過算法A合并產生概要的大小至多是k（|D1|+|D2|，ε）。如果k（n，ε）不依賴于n，就可以通過k（ε）來表示，那么S（D1，ε）和S（D2，ε）中的每一個的大小和由A產生的概要的大小至多是k（ε）。在某種意義上說，合并算法A可能代表概要S（D，ε）或可能儲存一些額外的信息（如加快合并過程的一個數據結構），還將用S（D，ε）標識概要的一些表示，還包含額外信息的維持。

如果限制輸入，以使|D2|=1，即每次總是合并單一項，然后恢復流模式。S（D，ε）就是通過流算法維持的概要，算法A針對每個新到達的對象進行概要更新。因此，合并性比流具有更強的嚴格要求，概要的大小應該至少是一樣大。

5 結束語

一些數據概要可以被合并。例如，所有D上具有線性函數的略圖都可以直接合并，主要包括F2 AMS略圖，Count-Min略圖，略圖，還有許多其他的。能維持最大值或top-k值的概要也可以直接合并，尤其是估算不同元素數量的概要。然而，幾個基于其他技術的概要不能被合并或具有不令人滿意的界限。