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

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

1 引言

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

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

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

3 概要合并的應(yīng)用

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

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

4 合并算法描述

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

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

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

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

5 結(jié)束語

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