數(shù)據(jù)流概要數(shù)據(jù)的合并性研究分析

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

關鍵詞：數(shù)據(jù)流；概要；合并性

1 引言

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

2 數(shù)據(jù)概要的合并性

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

3 概要合并的應用

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

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

4 合并算法描述

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

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

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

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

5 結(jié)束語

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