基于時(shí)間序列的Global Skyline并行算法

李媛媛, 曲雯毓, 栗志揚(yáng), 季長(zhǎng)清,3, 吳俊峰,4

(1. 大連海事大學(xué)信息科學(xué)技術(shù)學(xué)院, 遼寧 大連 116026; 2. 大連交通大學(xué)軟件學(xué)院,

遼寧 大連 116028; 3. 大連大學(xué)物理科學(xué)與技術(shù)學(xué)院, 遼寧 大連 116622;

4. 大連海洋大學(xué)信息工程學(xué)院, 遼寧 大連 116023)

?

基于時(shí)間序列的Global Skyline并行算法

李媛媛1,2, 曲雯毓1, 栗志揚(yáng)1, 季長(zhǎng)清1,3, 吳俊峰1,4

(1. 大連海事大學(xué)信息科學(xué)技術(shù)學(xué)院, 遼寧 大連 116026; 2. 大連交通大學(xué)軟件學(xué)院,

遼寧 大連 116028; 3. 大連大學(xué)物理科學(xué)與技術(shù)學(xué)院, 遼寧 大連 116622;

4. 大連海洋大學(xué)信息工程學(xué)院, 遼寧 大連 116023)

摘要：Global Skyline 查詢是Skyline查詢的一種變種,它和動(dòng)態(tài)Skyline查詢、反Skyline查詢關(guān)系密切,已被廣泛應(yīng)用于多目標(biāo)決策、網(wǎng)絡(luò)監(jiān)控、數(shù)據(jù)挖掘等方面。隨著數(shù)據(jù)的積累,傳統(tǒng)集中式的Skyline查詢已經(jīng)不能滿足大數(shù)據(jù)的處理要求。為了高效解決大規(guī)模的基于時(shí)間序列的數(shù)據(jù)處理難題,提出了基于MapReduce框架并行的Global Skyline Cell查詢算法。首先,通過(guò)對(duì)實(shí)際應(yīng)用需求進(jìn)行分析,本文提出了基于時(shí)間序列數(shù)據(jù)Skyline查詢的時(shí)間倒排索引模型;并提出了Global Skyline格概念,利用格間的支配關(guān)系進(jìn)行粗粒度高效剪枝,避免了大部分的無(wú)效運(yùn)算;其次查詢點(diǎn)將數(shù)據(jù)空間分割成不同象限,基于各象限進(jìn)行輪詢,實(shí)現(xiàn)了Global Skyline 格的查詢,在此候選結(jié)果中得到Global Skyline點(diǎn),為下一步實(shí)現(xiàn)動(dòng)態(tài)Skyline和反Skyline查詢奠定基礎(chǔ)。最后,我們?cè)贖adoop集群環(huán)境中實(shí)現(xiàn)了該算法。實(shí)驗(yàn)結(jié)果表明,該算法能有效解決基于時(shí)間序列的大規(guī)模數(shù)據(jù)Skyline查詢的時(shí)間和空間矛盾,能夠滿足實(shí)際應(yīng)用需求。

關(guān)鍵詞：Global Skyline查詢;MapReduce;大數(shù)據(jù);時(shí)間序列

0引言

Skyline查詢問(wèn)題又叫Pareto最優(yōu)或極大向量問(wèn)題[1],是從數(shù)據(jù)集中查找感興趣的點(diǎn),這些點(diǎn)不被其他點(diǎn)所支配。Skyline查詢將返回?cái)?shù)據(jù)集的一個(gè)子集,該子集中的點(diǎn)都不能被數(shù)據(jù)集中的任意一個(gè)其他點(diǎn)所支配,滿足這種條件的點(diǎn)稱為Skyline點(diǎn)(Skyline point,SP)。

Skyline查詢被廣泛應(yīng)用于多目標(biāo)決策、商業(yè)計(jì)劃、網(wǎng)絡(luò)監(jiān)控、無(wú)線傳感器網(wǎng)絡(luò)、數(shù)據(jù)挖掘等方面。近年來(lái),Skyline研究受到了廣泛關(guān)注,Skyline算法在集中式數(shù)據(jù)處理[1-4]和分布式數(shù)據(jù)處理[5-14]領(lǐng)域均得到了廣泛深入的研究。隨著傳感器網(wǎng)絡(luò),移動(dòng)互聯(lián)網(wǎng)及物聯(lián)網(wǎng)的不斷發(fā)展,數(shù)據(jù)流處理也成為Skyline計(jì)算的一個(gè)研究熱點(diǎn),并有了一些相關(guān)的研究[15-18]。

本文研究了隨時(shí)間不斷變化的大規(guī)模時(shí)序數(shù)據(jù)的Skyline查詢問(wèn)題,這些數(shù)據(jù)表現(xiàn)為數(shù)值的形式并且在每個(gè)時(shí)間點(diǎn)上均存在一個(gè)值,這個(gè)時(shí)間點(diǎn)指特定的時(shí)間粒度[16]。如網(wǎng)絡(luò)監(jiān)控中檢測(cè)到的各種安全事件按小時(shí)來(lái)記錄,零售業(yè)中各種商品按月銷售量來(lái)記錄。一個(gè)典型的例子是網(wǎng)絡(luò)監(jiān)控中對(duì)網(wǎng)絡(luò)節(jié)點(diǎn)信息的監(jiān)控,每個(gè)被監(jiān)控的節(jié)點(diǎn)實(shí)時(shí)向服務(wù)器發(fā)送被監(jiān)控的數(shù)據(jù),這樣就產(chǎn)生了海量的持續(xù)的數(shù)據(jù)及歷史數(shù)據(jù)記錄。以網(wǎng)絡(luò)安全為目的的監(jiān)控是為了發(fā)現(xiàn)異常和攻擊,而不是為了實(shí)時(shí)記錄網(wǎng)絡(luò)狀態(tài),同時(shí)還可以關(guān)注很多內(nèi)容,例如統(tǒng)計(jì)一段時(shí)間內(nèi)系統(tǒng)漏洞多且受攻擊頻率高的服務(wù)器,以采取針對(duì)性措施。Skyline計(jì)算會(huì)返回符合多標(biāo)準(zhǔn)最優(yōu)化選擇的關(guān)注對(duì)象。

隨著監(jiān)控網(wǎng)絡(luò)數(shù)據(jù)流速度的提高,使得短時(shí)間內(nèi)積累大量歷史數(shù)據(jù)成為可能,同時(shí)網(wǎng)絡(luò)安全監(jiān)控的長(zhǎng)期性和準(zhǔn)確性需求也要求擴(kuò)大數(shù)據(jù)規(guī)模。面對(duì)大規(guī)模歷史數(shù)據(jù)的處理,傳統(tǒng)的單機(jī)集中式處理模式受限于內(nèi)存容量、計(jì)算能力等因素而難以勝任。單機(jī)處理模式以犧牲服務(wù)質(zhì)量來(lái)保證大數(shù)據(jù)的處理,如概要數(shù)據(jù)、準(zhǔn)入控制、QoS降階[17-19]等方法。因此,如何針對(duì)大規(guī)模時(shí)間序列歷史數(shù)據(jù)進(jìn)行Skyline處理成為物聯(lián)網(wǎng)和云計(jì)算領(lǐng)域的新挑戰(zhàn)。文獻(xiàn)[20]提出了區(qū)間Skyline查詢,是從多個(gè)時(shí)序數(shù)據(jù)中發(fā)現(xiàn)所有在指定時(shí)間區(qū)間內(nèi)沒有被其他任何數(shù)據(jù)在量值上支配的時(shí)序數(shù)據(jù),但算法中需要計(jì)算并且保存某段時(shí)間序列中的最大值和最小值,當(dāng)數(shù)據(jù)量非常大時(shí),該方法計(jì)算費(fèi)用過(guò)高。與上述工作不同,本文考慮的是基于時(shí)序數(shù)據(jù)的Global Skyline查詢[5],提出了針對(duì)海量數(shù)據(jù)的查詢。

本文針對(duì)數(shù)據(jù)流上的數(shù)據(jù)的特點(diǎn)及Skyline查詢所面臨的問(wèn)題進(jìn)行了研究。數(shù)據(jù)流處理的數(shù)據(jù)規(guī)模大,一般都是海量的,比如中國(guó)電信主干網(wǎng)絡(luò)每秒能產(chǎn)生幾十GB的數(shù)據(jù);同時(shí)這些海量數(shù)據(jù)都是連續(xù)的,針對(duì)查詢結(jié)果的數(shù)據(jù)增量維護(hù)困難;應(yīng)用在網(wǎng)絡(luò)監(jiān)控及環(huán)境監(jiān)控的Skyline查詢,關(guān)注的是異常情況的發(fā)現(xiàn),比如基于閾值網(wǎng)絡(luò)攻擊檢測(cè),Skyline查詢能夠提供近似結(jié)果查詢的要求。

基于上述原因,本文提出了一種基于時(shí)段度量的時(shí)序數(shù)據(jù)Global Skyline算法,此算法采用一種粗粒度的剪枝方法,目的在于快速排除大量不相關(guān)的數(shù)據(jù),減少參與運(yùn)算的數(shù)據(jù),同時(shí)也可以為動(dòng)態(tài)Skyline和反Skyline計(jì)算提供更小的運(yùn)算集合。為了更有效地管理數(shù)據(jù),本文提出了基于時(shí)間序列數(shù)據(jù)Skyline查詢的時(shí)間倒排索引模型，并在此基礎(chǔ)上提出了Global Skyline格概念,利用格間的支配關(guān)系進(jìn)行粗粒度的剪枝,減少了大部分的無(wú)效數(shù)據(jù)。本文還討論了如何在MapReduce并行環(huán)境下實(shí)現(xiàn)此算法的問(wèn)題,并利用集群強(qiáng)大處理能力快速生成時(shí)間倒排索引的方法。針對(duì)數(shù)據(jù)流數(shù)據(jù)的連續(xù)性,提出了基于時(shí)間片的Skyline查詢,能夠支持?jǐn)?shù)據(jù)的增量維護(hù)。

第1節(jié)對(duì)問(wèn)題進(jìn)行形式化描述,基于已有相關(guān)工作提出了基于時(shí)段度量的時(shí)序數(shù)據(jù)Global Skyline算法;第2節(jié)給出了系統(tǒng)處理模型和時(shí)間倒排索引模型,闡述了其詳細(xì)查詢過(guò)程及具體數(shù)據(jù)結(jié)構(gòu)。第3節(jié)通過(guò)實(shí)驗(yàn)驗(yàn)證上述方法的有效性和高效性;第4節(jié)對(duì)全文進(jìn)行總結(jié)和展望。

1問(wèn)題描述

1.1點(diǎn)支配

d維空間上的對(duì)象集合S={p1,…,pn}中的任意對(duì)象pi,pj∈S,若滿足以下兩個(gè)條件,稱pi支配pj,即pippj:①pi任意一維屬性取值都不比pj差;②至少有一維屬性取值優(yōu)于pj。

1.2靜態(tài)Skyline

給定對(duì)象集合S,S的Skyline是所有不被其他對(duì)象支配的對(duì)象集合SP(S)={pi|?pj∈S,pjppi}。

1.3動(dòng)態(tài)Skyline

給定查詢點(diǎn)q,對(duì)于任意兩個(gè)對(duì)象pi,pj∈S,pi動(dòng)態(tài)支配pj即pipqpj,滿足條件:

(1) ?t∈{1,2,…,d},|pi(t)-q(t)|≤|pj(t)-q(t)|;

(2) ?k∈{1,2,…,d},|pi(k)-q(k)|<|pj(k)-q(k)|。

例如在網(wǎng)絡(luò)安全監(jiān)控應(yīng)用中,可以監(jiān)控主機(jī)安全漏洞數(shù)、入侵頻率、流量信息等指標(biāo)。一臺(tái)對(duì)外提供服務(wù)的網(wǎng)絡(luò)主機(jī)安全漏洞數(shù)量越多,其可能遭受攻擊的類型就越多,入侵頻率就越高。不同攻擊又導(dǎo)致不同的流量變化。若已知某臺(tái)主機(jī)遭受某種攻擊,該主機(jī)的監(jiān)控?cái)?shù)據(jù)作為查詢點(diǎn),我們可以針對(duì)網(wǎng)絡(luò)監(jiān)控?cái)?shù)據(jù)進(jìn)行動(dòng)態(tài)Skyline計(jì)算得到其他疑似被攻擊的主機(jī)。

圖1以網(wǎng)絡(luò)監(jiān)控為例說(shuō)明了靜態(tài)Skyline和動(dòng)態(tài)Skyline的不同。圖中的數(shù)據(jù)點(diǎn)為網(wǎng)絡(luò)中的主機(jī),x, y坐標(biāo)分別表示該主機(jī)被監(jiān)控的相關(guān)指標(biāo)。圖1(a)為靜態(tài)Skyline查詢的例子,返回安全隱患最大的主機(jī)(p7, p6, p8)。圖1(b)則為動(dòng)態(tài)Skyline查詢,q為遭受攻擊的主機(jī),動(dòng)態(tài)Skyline計(jì)算返回疑似遭受攻擊的主機(jī)候選集(p7, p3, p6)。

1.4Global Skyline

給定查詢點(diǎn)q,d維空間上的對(duì)象集合S中任意兩個(gè)對(duì)象pi,pj∈S,對(duì)象pi關(guān)于查詢點(diǎn)q全局支配pj滿足下面條件:

圖1　網(wǎng)絡(luò)監(jiān)控示例

(1) ?t∈{1,2,…,d},(pi(t)-q(t))(pj(t)-q(t))>0;

(2) ?t∈{1,2,…,d},|pi(t)-q(t)|≤|pj(t)-q(t)|;

(3) ?k∈{1,2,…,d},|pi(k)-q(k)|<|pj(k)-q(k)|。

GlobalSkyline是Skyline查詢的一種變種,考慮的是在有查詢點(diǎn)情況下的Skyline計(jì)算,比靜態(tài)Skyline計(jì)算復(fù)雜。同時(shí)與動(dòng)態(tài)Skyline和反Skyline計(jì)算關(guān)系密切。它返回所有不被其他對(duì)象全局支配的對(duì)象集合。給定一個(gè)查詢點(diǎn),查詢點(diǎn)把d維數(shù)據(jù)空間分割成2d個(gè)子象限。GlobalSkyline需要查詢得到所有子象限(2d個(gè)子象限)的全局Skyline點(diǎn)。本文分析的是基于時(shí)間序列的歷史數(shù)據(jù),關(guān)于時(shí)間片的定義如下。

1.5時(shí)間片

定義了一個(gè)時(shí)間范圍[i,j](i≤j),t[i:j]=t[i],t[i+1],…,t[j](i≤j)表示時(shí)間片。如果k∈[i:j]即i≤k≤j。對(duì)于兩個(gè)時(shí)間片[i1:j1]和[i2:j2],當(dāng)i1≥i2且j1≤j2,[i1:j1]?[i2:j2]。

有了時(shí)間片定義,可以推導(dǎo)出時(shí)間片上的支配關(guān)系:給定一個(gè)時(shí)間片[i:j]和對(duì)象集合S,滿足條件,若?k∈[i:j],pi[k]≤pj[k];并且?l∈[i:j],pi[l]

于是,給定一個(gè)對(duì)象集合S和一個(gè)時(shí)間片[i:j],該時(shí)間片上的Skyline如下:

(1)

2基于時(shí)間倒排索引的GlobalSkyline并行算法

本文針對(duì)大規(guī)模歷史數(shù)據(jù)提出的Global Skyline并行算法流程,如圖2所示,系統(tǒng)主要由時(shí)間劃分模塊、生成索引模塊、查詢模塊組成。所有模塊都運(yùn)行在Hadoop云平臺(tái)上,利用分布式集群的強(qiáng)大計(jì)算能力能很好地解決大數(shù)據(jù)的處理要求。

首先,數(shù)據(jù)由成千上萬(wàn)個(gè)監(jiān)控節(jié)點(diǎn)產(chǎn)生,這些節(jié)點(diǎn)可以是環(huán)境監(jiān)控中的傳感器,也可以是網(wǎng)絡(luò)節(jié)點(diǎn)中的主機(jī),它們都有一個(gè)共同的特點(diǎn),以一定時(shí)間間隔通過(guò)網(wǎng)絡(luò)向服務(wù)器發(fā)送收集到的數(shù)據(jù)。隨著時(shí)間推移,服務(wù)器的磁盤陣列中形成了大規(guī)模的歷史數(shù)據(jù)可用于分析計(jì)算。

時(shí)間劃分模塊就是利用MapReduce框架并行讀取這些歷史數(shù)據(jù),并按一定的時(shí)間間隔將大數(shù)據(jù)集分而治之,形成以小時(shí)、天、月或年為間隔的小數(shù)據(jù)集。這樣方便后續(xù)的計(jì)算和針對(duì)實(shí)際不同應(yīng)用需要的各種時(shí)段統(tǒng)計(jì),MapReduce也正適合這種大規(guī)模數(shù)據(jù)的處理。

圖2　系統(tǒng)模型

生成索引模塊是為了加快查找速度,減少大量無(wú)效運(yùn)算而生成的倒排索引。將各個(gè)時(shí)間段內(nèi)數(shù)據(jù)分別生成時(shí)間倒排索引以備后續(xù)計(jì)算。這個(gè)預(yù)處理過(guò)程雖然耗時(shí),但一旦索引事先生成,基于時(shí)間倒排索引的后續(xù)計(jì)算可以大大加快查詢的速度。

查詢模塊接受管理節(jié)點(diǎn)的查詢請(qǐng)求,一旦查詢點(diǎn)q到來(lái),查詢模塊將q映射到時(shí)間倒排索引中,使用Skyline格進(jìn)行粗粒度的減枝,減少了大部分無(wú)效數(shù)據(jù)。利用各象限進(jìn)行輪詢,得到Global Skyline結(jié)果集,針對(duì)這一結(jié)果集作進(jìn)一步的動(dòng)態(tài)Skyline或反Skyline查詢,并將結(jié)果返回給管理節(jié)點(diǎn)。至此,查詢計(jì)算完成。

接下來(lái)本文將重點(diǎn)介紹此流程中的關(guān)鍵處理技術(shù)及重要數(shù)據(jù)結(jié)構(gòu)。

2.1時(shí)間劃分模塊

在很多應(yīng)用中需要分析大量的時(shí)序數(shù)據(jù),比如網(wǎng)絡(luò)監(jiān)控、股票行情等。以二維屬性為例,加上時(shí)間就是三維空間,每個(gè)數(shù)據(jù)點(diǎn)p的當(dāng)前狀態(tài)可以表示為,id為數(shù)據(jù)點(diǎn)的標(biāo)識(shí),x和y為數(shù)據(jù)點(diǎn)的屬性值,t為數(shù)據(jù)點(diǎn)的時(shí)間屬性值,如圖3所示。我們把連續(xù)的時(shí)間序列分割成若干時(shí)間片段,然后對(duì)每個(gè)時(shí)間片段的數(shù)據(jù)進(jìn)行Skyline查詢。

圖3　時(shí)間劃分模型

給定一個(gè)對(duì)象集合S,每個(gè)數(shù)據(jù)點(diǎn)p的時(shí)間屬性值(t)在一個(gè)有界的區(qū)間[Tmin,Tmax],構(gòu)造一個(gè)均勻的劃分{t0,…,tB},ti的定義如下:

(2)

由公式(2)形成一個(gè)含有B個(gè)時(shí)間片元素的集合{b0,…,bB-1},其中，每個(gè)時(shí)間片bi=[ti,ti+1),固定長(zhǎng)度為l。每個(gè)數(shù)據(jù)點(diǎn)的時(shí)間屬性為t映射到時(shí)間片bs(t)∈B,其中s(t)的定義如式(3)所示,其中不同粒度的區(qū)間l的值要根據(jù)實(shí)際應(yīng)用情況而定。

(3)

2.2索引數(shù)據(jù)結(jié)構(gòu)及流程

本文設(shè)計(jì)了一種基于時(shí)間序列的倒排索引數(shù)據(jù)結(jié)構(gòu),如圖4所示，以二維空間為例,每個(gè)點(diǎn)的數(shù)據(jù)可表示為。先根據(jù)時(shí)間片將大數(shù)據(jù)集分成不同的組,也就是較小數(shù)據(jù)集,存儲(chǔ)數(shù)據(jù)結(jié)構(gòu)為。其中tid為時(shí)間片段key值;ti,ti+1分別代表這一時(shí)間序列數(shù)據(jù)集中的時(shí)間最小、最大值;grid采用hashmap結(jié)構(gòu)的網(wǎng)格索引,用于存儲(chǔ)具體的數(shù)據(jù)信息。

圖4　基于時(shí)間序列的倒排索引結(jié)構(gòu)

(4)

以二維數(shù)據(jù)為例,帶時(shí)間維的數(shù)據(jù)點(diǎn)都可表示為P,t已被劃分,在同一時(shí)間片內(nèi)的數(shù)據(jù)點(diǎn)可以表示為P。P可以通過(guò)公式(4)映射到對(duì)應(yīng)網(wǎng)格當(dāng)中去。

圖5　網(wǎng)格倒排索引生成過(guò)程

以上時(shí)間劃分和生成索引兩過(guò)程利用MapReduce處理可以合并,用一個(gè)MapReduce流程完成,整個(gè)過(guò)程如圖6所示。

圖6　MapReduce生成索引流程

時(shí)間片個(gè)數(shù)B設(shè)置為n,網(wǎng)格寬度δ1=δ2=15,同時(shí)啟動(dòng)多個(gè)Map對(duì)歷史大數(shù)據(jù)進(jìn)行讀取,每個(gè)Map讀取不同的HDFS數(shù)據(jù)片生成這樣的數(shù)據(jù)對(duì),此處的key為時(shí)間索引,value為hashmap數(shù)據(jù)結(jié)構(gòu),里面存儲(chǔ)著根據(jù)劃分得到的相應(yīng)數(shù)據(jù)點(diǎn)。每個(gè)Map得到如圖6所示的中間數(shù)據(jù),也就是代表部分?jǐn)?shù)據(jù)的子索引,并且自動(dòng)根據(jù)key完成排序。為了保證數(shù)據(jù)完整性和一致性,最后調(diào)用一個(gè)Reduce完成索引的歸并生成。時(shí)間倒排索引的生成是一個(gè)預(yù)處理過(guò)程,預(yù)先生成可供后續(xù)查詢使用并且不占用查詢時(shí)間,是一種有效的數(shù)據(jù)管理模式。同時(shí)MapReduce對(duì)大數(shù)據(jù)并行處理的能力也能很好的完成此項(xiàng)工作。從圖5也能看出,將來(lái)的查詢遍歷原始數(shù)據(jù)遠(yuǎn)遠(yuǎn)沒有遍歷倒排索引快。

2.3GlobalSkyline格的計(jì)算

Skyline查詢的開銷和數(shù)據(jù)集大小有直接關(guān)系,尤其是對(duì)于海量數(shù)據(jù)它們的支配關(guān)系判斷也是一筆很大的開銷。為了解決這一問(wèn)題,我們提出了Skyline格概念,如圖7所示。查詢點(diǎn)q被映射到相應(yīng)的Skyline網(wǎng)格C6當(dāng)中,整個(gè)網(wǎng)格區(qū)域就被分成了影響區(qū)域和被支配區(qū)域。非空的格C1,C2,C3,C5,C7,C9,C10,C11都為其影響區(qū)域,被支配區(qū)域是指被受影響區(qū)域支配的區(qū)域,如在第二象限中的C4格。

圖7　Global Skyline查詢與減枝

2.3.1單元格支配

給定查詢點(diǎn)q,d維空間上單元格集合C中任意兩個(gè)單元格ci,cj,用單元格的左下角點(diǎn)ei,ej坐標(biāo)表示單元格,若滿足條件:?k∈{1,2,…,d},|ei(k)-q(k)|<|ej(k)-q(k)|則格ci關(guān)于q支配格cj即cipqcj。

由單元格支配定義,我們可以類推出全局格支配公式,給定查詢點(diǎn)q,d維空間上單元格集合C中任意兩個(gè)單元格ci,cj,ei,ej坐標(biāo)表示單元格。若滿足條件:

①?k∈{1,2,…,d},(ei(k)-q(k))(ej(k)-q(k))>0;

②?k∈{1,2,…,d},|ei(k)-q(k)|<|ej(k)-q(k)|。

則格ci關(guān)于q全局支配cj,即ci?qcj。

2.3.2GlobalSkyline格

給定格集合C,C的全局Skyline是所有不被其他格全局支配的格集合GSC(C)={ci|┐?cj∈C,cj?qci}。

算法1 GlobalSkyline格算法輸入:n維的數(shù)據(jù)集S,查詢點(diǎn)q,中間結(jié)果集C輸出:查詢結(jié)果集R1:初始化原數(shù)據(jù)集S=?,C=?2:初始化結(jié)果集R=?3:FOR(everypointpi∈S)DO4: 按時(shí)間屬性,分割數(shù)據(jù)點(diǎn)pi為時(shí)間序列5: 由公式gdx=pi.xd/δd,映射pi到相應(yīng)的網(wǎng)格6: 插入pi到集合C中7:ENDFOR8:生成數(shù)據(jù)對(duì)并插入Gridt結(jié)構(gòu)中9:根據(jù)查詢點(diǎn)q計(jì)算并返回其所在的Gridt10:查詢點(diǎn)q為中心點(diǎn)將網(wǎng)格分割成2n個(gè)基本象限Gridi11:FOR(i=1to2n)DO12: FOR(Gridinotend)DO13: IF(網(wǎng)格ckey1被ckey2支配)14: THEN15: 移除網(wǎng)格ckey116: ENDFOR17: FOR(everypointsinGridi)DO18: 傳遞給reduce函數(shù)19: ENDFOR20:返回結(jié)果集R

命題 1如果一個(gè)點(diǎn)p不在GlobalSkyline格中,那么它一定不是GlobalSkyline點(diǎn)。

證明如果點(diǎn)p∈S且p?GSC(q),則p點(diǎn)一定落入被支配區(qū)域。則存在某個(gè)非空網(wǎng)格ci支配該點(diǎn)所在區(qū)域。ci中一定存在點(diǎn)關(guān)于q支配點(diǎn)p,則點(diǎn)p一定不是GlobalSkyline點(diǎn)。

證畢

推論 1任意一個(gè)GlobalSkyline點(diǎn),它一定在某個(gè)GlobalSkyline格里。

綜上所述,數(shù)據(jù)空間被劃分為影響區(qū)域和支配區(qū)域。全局Skyline格所在的區(qū)域?yàn)橛绊憛^(qū)域,如圖7所示的圓形區(qū)域,在生成全局Skyline格過(guò)程中,被支配的區(qū)域如圖7所示的正方形陰影部分。我們利用過(guò)濾掉被支配的單元格方法進(jìn)行粗略剪枝。

對(duì)于影響區(qū)域的查找,我們采用的是2n個(gè)象限輪詢法(n為數(shù)據(jù)集維數(shù)),通過(guò)逐步擴(kuò)展的方法,無(wú)需遍歷全部數(shù)據(jù)便能獲得影響區(qū)域及格中的數(shù)據(jù)點(diǎn)。相對(duì)于原始數(shù)據(jù)的全遍歷,數(shù)量甚微的Skyline格的遍歷大大減少了計(jì)算開銷。實(shí)驗(yàn)結(jié)果也表明,通過(guò)此方法海量歷史數(shù)據(jù)的Skyline查找效率大大提高。算法流程如算法1所示。

由推論1可知,上述算法返回GlobalSkyline格中的數(shù)據(jù)點(diǎn)一定在GlobalSkyline結(jié)果集中,也就是GlobalSkyline格是GlobalSkyline的侯選集,接著掃描算法1得到的結(jié)果侯選集,進(jìn)行支配關(guān)系比較,最終得到GlobalSkyline結(jié)果。

3實(shí)驗(yàn)評(píng)測(cè)

在本節(jié)中,我們介紹了實(shí)驗(yàn)集群環(huán)境及測(cè)試數(shù)據(jù)情況,本文中所提到的方法采用Java語(yǔ)言編寫,均在Hadoop平臺(tái)下實(shí)現(xiàn)。

3.1實(shí)驗(yàn)配置

所有實(shí)驗(yàn)均在Hadoop集群中實(shí)現(xiàn)運(yùn)行,該集群由 12臺(tái)節(jié)點(diǎn)所組成。每個(gè)節(jié)點(diǎn)硬件配置相同:DualcoreAMDOpteron2212 2.00GHzCPU,80GBSCSI硬盤, 2GB內(nèi)存,Intel82551 10/100Mbps以太網(wǎng)網(wǎng)卡。每個(gè)節(jié)點(diǎn)操作系統(tǒng)均為Ubuntu10.10server64位操作系統(tǒng),安裝的Hadoop版本號(hào)為Hadoop0.20.2。所有節(jié)點(diǎn)以100M局域網(wǎng)相連接,一臺(tái)運(yùn)行有JobTracker和NameNode的節(jié)點(diǎn)作為master節(jié)點(diǎn),剩下其他節(jié)點(diǎn)均為slave節(jié)點(diǎn)。HDFS文件系統(tǒng)的chunksize設(shè)置為64MB。

所有實(shí)驗(yàn)均基于以下兩類數(shù)據(jù)集合進(jìn)行:

(1) 真實(shí)數(shù)據(jù)集:利用sniffer工具對(duì)某數(shù)據(jù)中心進(jìn)行一段時(shí)間的監(jiān)控抓包統(tǒng)計(jì),得到197 895條網(wǎng)絡(luò)監(jiān)控?cái)?shù)據(jù)。這些數(shù)據(jù)流包含正常流量和非正常的受攻擊流量,不同時(shí)段內(nèi)的數(shù)據(jù)量及流速度都具有隨機(jī)性。它真實(shí)地反映了網(wǎng)絡(luò)監(jiān)控?cái)?shù)據(jù)流的特征,但數(shù)據(jù)量難以達(dá)到海量特征。

(2) 模擬數(shù)據(jù)集:生成3種分布的海量數(shù)據(jù)如圖7所示。第1種是均勻分布的數(shù)據(jù)如圖8(a)所示,數(shù)據(jù)集里的對(duì)象各維屬性相互獨(dú)立;第2種是正相關(guān)數(shù)據(jù)如圖8(b)所示,數(shù)據(jù)集里的對(duì)象各維屬性值成正比例增長(zhǎng);第3種是反相關(guān)數(shù)據(jù)如圖8(c)所示,數(shù)據(jù)集里的對(duì)象各維屬性值成反比例增長(zhǎng)。3種數(shù)據(jù)均產(chǎn)生40 000萬(wàn)條歷史數(shù)據(jù)記錄,以100 000/s持續(xù)到達(dá)模擬數(shù)據(jù)流場(chǎng)景。

圖8　模擬數(shù)據(jù)的3種數(shù)據(jù)分布

3.2實(shí)驗(yàn)結(jié)果

圖9展示了剪枝策略的效果,實(shí)驗(yàn)中采用真實(shí)數(shù)據(jù)集,數(shù)據(jù)記錄總條數(shù)n=197 895時(shí),剪枝后剩下數(shù)據(jù)記錄條數(shù)隨網(wǎng)格大小的變化情況。當(dāng)網(wǎng)格大小設(shè)為5,剪枝后的記錄數(shù)為38 303,僅為原來(lái)數(shù)據(jù)量的1/5。如圖9所示網(wǎng)格設(shè)置越小,剪枝效果越明顯。因真實(shí)的網(wǎng)絡(luò)監(jiān)控?cái)?shù)據(jù)分布比較密集,而且數(shù)據(jù)規(guī)模較小且分布集中,網(wǎng)格大小對(duì)剪枝效果并不十分明顯。

圖9　剪枝與網(wǎng)格大小關(guān)系

圖10展示了模擬數(shù)據(jù)集3種不同數(shù)據(jù)分布下網(wǎng)格索引的生成時(shí)間。實(shí)驗(yàn)采用模擬數(shù)據(jù)集,數(shù)據(jù)集大小為40 000萬(wàn)條數(shù)據(jù)。生成網(wǎng)格的時(shí)間隨著網(wǎng)格大小的增大而增長(zhǎng)。網(wǎng)格大小設(shè)置一樣的情況下,均勻分布數(shù)據(jù)生成網(wǎng)格索引時(shí)間最短,因?yàn)閿?shù)據(jù)散狀分布在各個(gè)網(wǎng)格中;正相關(guān)分布的數(shù)據(jù)次之,反相關(guān)數(shù)據(jù)耗時(shí)最長(zhǎng),這和數(shù)據(jù)過(guò)于集中在部分網(wǎng)格,并且I/O開銷大有關(guān)。這一點(diǎn)在后面的HDFSI/O開銷實(shí)驗(yàn)中也有體現(xiàn)。

圖10　網(wǎng)格生成時(shí)間與網(wǎng)格大小關(guān)系

表1總結(jié)了不同數(shù)據(jù)量情況下算法的運(yùn)行時(shí)間。實(shí)驗(yàn)采用均勻分布模擬數(shù)據(jù)集,數(shù)據(jù)記錄條數(shù)最小10 000萬(wàn)條(1.28GB),最大40 000(5.12GB)萬(wàn)條。網(wǎng)格大小設(shè)置為1,時(shí)間定義公式中B的值設(shè)置為2,分為{b0,b1}兩個(gè)時(shí)間片。算法運(yùn)行時(shí)間由3部分組成:生成倒排網(wǎng)格索引時(shí)間(timeofbuildinggridindex,TBGI);Global格剪枝時(shí)間(timeofpruningusingglobalskylinecell,TPG);GlobalSkyline查詢時(shí)間(timeofglobalskylinequery,TGSQ)。隨著數(shù)據(jù)量的增加,總的運(yùn)行時(shí)間大幅度增加。在每個(gè)數(shù)據(jù)集內(nèi)前兩個(gè)階段即網(wǎng)格索引生成時(shí)間與剪枝時(shí)間及查詢時(shí)間比所占比例較大,這恰好說(shuō)明,對(duì)于大數(shù)據(jù)量Skyline算法處理建立索引的必要性。生成倒排網(wǎng)格索引屬于預(yù)處理階段,預(yù)先生成以提供后續(xù)查詢,并不占用真正查詢時(shí)間,Hadoop正適合此類數(shù)據(jù)的處理。通過(guò)這一階段的預(yù)處理,能大大提高查詢效率。

表1　在模擬數(shù)據(jù)集下的運(yùn)行時(shí)間　s

圖11是實(shí)驗(yàn)采用模擬數(shù)據(jù)集3種不同數(shù)據(jù)分布,數(shù)據(jù)集記錄數(shù)從10 000~40 000萬(wàn)條數(shù)據(jù)變化,網(wǎng)格大小為1,B的值仍設(shè)置為2情況下,算法中執(zhí)行時(shí)間即表1中后兩項(xiàng)和的對(duì)比。隨著數(shù)據(jù)量的增長(zhǎng),查詢時(shí)間也隨著增長(zhǎng)。相同數(shù)據(jù)量的情況下,反相關(guān)分布的數(shù)據(jù)執(zhí)行時(shí)間最長(zhǎng),正相關(guān)分布次之,均勻分布查詢時(shí)間最短。這是因?yàn)榫鶆蚍植嫉臄?shù)據(jù)剪枝的效果最好,并且I/O開銷也小。

圖11　不同數(shù)據(jù)分布下算法的運(yùn)行時(shí)間

圖12展示了算法運(yùn)行時(shí)間。當(dāng)實(shí)驗(yàn)數(shù)據(jù)記錄條數(shù)固定為40 000萬(wàn)條時(shí),網(wǎng)格大小設(shè)置為1,B的值最小為2,最大為10變換。隨著B的值增大,時(shí)間片間隔變小,數(shù)據(jù)分組越多,每組當(dāng)中的數(shù)據(jù)越少,算法的運(yùn)行時(shí)間相應(yīng)的變少。

圖12　算法的運(yùn)行時(shí)間和B值關(guān)系

圖13展示了不同數(shù)據(jù)量情況下兩種算法的運(yùn)行時(shí)間對(duì)比,其中本文基于MapReduce框架并行的帶Global Skyline格(GSC-MR)算法的運(yùn)行時(shí)間包含了表1中的3部分時(shí)間和(包含了網(wǎng)格索引的建立時(shí)間);對(duì)比算法為同等實(shí)驗(yàn)平臺(tái)下的傳統(tǒng)不帶Global Skyline格計(jì)算過(guò)程的查詢即直接計(jì)算Global Skyline點(diǎn)。實(shí)驗(yàn)采用均勻分布模擬數(shù)據(jù)集,數(shù)據(jù)記錄條數(shù)最小10 000萬(wàn)條,最大40 000萬(wàn)條。網(wǎng)格大小設(shè)置為1,時(shí)間定義公式中B的值設(shè)置為2。如圖13所示,當(dāng)數(shù)據(jù)量較小的情況下,GSC-MR算法優(yōu)勢(shì)并不明顯,這是因?yàn)轭A(yù)處理時(shí)間比例較大。隨著數(shù)據(jù)量的增長(zhǎng)GSC-MR算法的優(yōu)勢(shì)就越明顯。

圖13　算法比較

圖14展示了模擬數(shù)據(jù)在不同數(shù)據(jù)分布下HDFS的I/O開銷,這里的I/O開銷是所有過(guò)程I/O的總和,包括建立索引階段。實(shí)驗(yàn)的數(shù)據(jù)記錄條數(shù),最小10 000萬(wàn)條,最大40 000萬(wàn)條。網(wǎng)格大小設(shè)置為1,B的值為1。如圖14所示,相同數(shù)據(jù)記錄的條件下,均勻分布的HDFS I/O開銷最小,正相關(guān)次之,反相關(guān)數(shù)據(jù)開銷最大。正相關(guān)數(shù)據(jù)和反相關(guān)數(shù)據(jù)I/O開銷差距不大,但都比均勻分布大很多。這是因?yàn)榫鶆蚍植技糁﹄A段的I/O開銷相對(duì)小的多。

圖14　不同數(shù)據(jù)分布的HDFS I/O

圖15總結(jié)了不同并行機(jī)器數(shù)下算法的運(yùn)行時(shí)間的加速比。實(shí)驗(yàn)中并行的節(jié)點(diǎn)數(shù)由2增至12臺(tái),采用均勻分布模擬數(shù)據(jù)集,數(shù)據(jù)記錄條數(shù)分別為20 000萬(wàn)條(2.56 GB)和40 000萬(wàn)條(5.12 GB)。網(wǎng)格大小設(shè)置為1,時(shí)間定義公式中B的值設(shè)置為2。算法運(yùn)行時(shí)間為總運(yùn)行時(shí)間,包括生成倒排網(wǎng)格索引時(shí)間,Global格剪枝時(shí)間和Global Skyline查詢時(shí)間總和。隨著并行機(jī)器數(shù)的增加,算法的運(yùn)行時(shí)間的加速比也增長(zhǎng),并且數(shù)據(jù)規(guī)模越大,算法的加速趨勢(shì)越明顯。

圖15　不同機(jī)器數(shù)下的加速比

4結(jié)論

本文研究了基于時(shí)序數(shù)據(jù)離線Global Skyline 查詢,將連續(xù)的時(shí)間分割成時(shí)間片,針對(duì)每個(gè)時(shí)間片,利用MapReduce進(jìn)行并行Skyline查詢。該查詢算法針對(duì)海量數(shù)據(jù),進(jìn)行網(wǎng)格索引,利用格支配關(guān)系進(jìn)行剪枝。本文針對(duì)的是大規(guī)模歷史數(shù)據(jù)的處理,數(shù)據(jù)的實(shí)時(shí)計(jì)算將成為新的挑戰(zhàn)?，F(xiàn)有批處理方式的編程框架MapReduce難以滿足實(shí)時(shí)要求,文獻(xiàn)[20]提出了了實(shí)時(shí)性研究方法,下一步工作希望改進(jìn)MapReduce框架以提高大規(guī)模數(shù)據(jù)流處理的實(shí)時(shí)效率。

參考文獻(xiàn)：

[1] B?rzs?nyi S, Kossmann D, Stocker K. The Skyline operator[C]∥Proc.ofthe17thInternationalConferenceonDataEngineering, 2001: 421-430.

[2] Chomicki J, Godfrey P, Gryz J. Skyline with presorting[C]∥Proc.oftheInternationalConferenceonDataEngineering, 2003: 717-816.

[3] Huang Y K, Chang C H, Lee C. Continuous distance-based Skyline queries in road networks[J].InformationSystems, 2012, 37(7): 611-633.

[4] Lin X, Zhang Y, Zhang W, et al. Stochastic Skyline operator[C]∥Proc.ofthe27thInternationalConferenceonDataEngineering, 2011: 721-732.

[5] Dellis E, Seeger B. Efficient Computation of reverse Skyline queries[C]∥Proc.ofthe33rdInternationalConferenceonVeryLargeDataBases, 2007: 291-302.

[6] Hose K, Vlachou A. A survey of Skyline processing in highly distributed environments[J].TheInternationalJournalonVeryLargeDataBases, 2012, 21(3): 359-384.

[7] Afrati F N, Koutris P, Suciu D, et al. Parallel Skyline queries[C]∥Proc.ofthe15thInternationalConferenceonDatabaseTheory,ACM, 2012: 274-284.

[8] Vlachou A, Doulkeridis C, N?rv?g K. Distributed top-kquery processing by exploiting Skyline summaries[J].DistributedandParallelDatabases, 2012, 30(3/4): 239-271.

[9] K?hler H, Yang J, Zhou X. Efficient parallel Skyline processing using hyperplane projections[C]∥Proc.oftheACMSIGMODInternationalConferenceonManagementofdata, 2011: 85-96.

[10] Zhang B L, Zhou S G,Guan J H. Adapting Skyline computation to the mapreduce framework: algorithms and experiments[C]∥Proc.oftheDatabaseSystemsforAdvancedApplications,2011:403-414.

[11] Vlachou A, Doulkeridis C, Kotidis Y. Angle based space partitioning for efficient parallel Skyline computation[C]∥Proc.oftheACMSIGMODInternationalConference, 2008: 227-238.

[12] Chen L, Hwang K, Wu J. Mapreduce Skyline query processing with a new angular partitioning approach[C]∥Proc.oftheIEEEInternationalSymposiumonParallelandDistributedProcessing,WorkshopsandPhdForum, 2012:2262-2270.

[13] Ding L, Wang G, Xin J, et al. ComMapReduce: an improvement of mapreduce with lightweight communication mechanisms[J].LectureNotesinComputerScience, 2012, 88(1): 224-247

[14] Park Y, Min J K, Shim K. Parallel computation of Skyline and reverse Skyline queries using mapreduce[C]∥Proc.oftheInternationalConferenceonVeryLargeDataBases, 2013:2002-2013.

[15] Zhang W, Lin X, Zhang Y, et al. Probabilistic Skyline operator over sliding windows[J].InformationSystems, 2013, 38(8): 1212-1233.

[16] Jin C, Yi K, Chen L, et al. Sliding-window top-k queries on uncertain streams[J].TheVLDBJournal, 2010, 19(3): 411-435.

[17] Zhang L, Zou P, Jia Y,et.al. Continuous dynamic Skyline queries over data stream[J].JournalofComputerResearchandDevelopment, 2011,48(1):77-85.(張麗,鄒鵬,賈焰,等.數(shù)據(jù)流上連續(xù)動(dòng)態(tài)Skyline查詢研究[J].計(jì)算機(jī)研究與發(fā)展,2011,48(1):77-85.)

[18] Tian L, Wang L, Li A P, et al. Resource sharing in continuous extreme values monitoring on sliding windows[J].JournalofComputerResearchandDevelopment, 2008,45(3):548-556.(田李,王樂,李愛平,等. 滑動(dòng)窗口數(shù)據(jù)流上多極值查詢資源共享策略研究[J]. 計(jì)算機(jī)研究與發(fā)展, 2008,45(3):548-556.)

[19] Li Z, Peng Z, Yan J, et al. Continuous dynamic Skyline queries over data stream[J].JournalofComputerResearchandDevelopment, 2011, 48(1): 77-85.

[20] Jiang B, Pei J. Online interval Skyline queries on time series[C]∥Proc.oftheInternationalConferenceonDataEngineering, 2009: 1036-1047.

李媛媛(1980-),女,講師,博士研究生,主要研究方向?yàn)樵朴?jì)算、大數(shù)據(jù)信息檢索。

E-mail:lyy1135@dlmu.edu.cn

曲雯毓(1972-),女,教授,博士,主要研究方向?yàn)樵朴?jì)算、計(jì)算機(jī)網(wǎng)絡(luò)、信息檢索。

E-mail:wenyu@dlmu.edu.cn

栗志揚(yáng)(1982-),男,副教授,博士,主要研究方向?yàn)閳D像檢索、計(jì)算幾何。

E-mail:lizy@dlmu.edu.cn

季長(zhǎng)清(1980-),男,副教授,博士研究生,主要研究方向?yàn)樵朴?jì)算、空間數(shù)據(jù)檢索。

E-mail:jcqgood@gmail.com

吳俊峰(1983-),男,講師,博士研究生,主要研究方向?yàn)閳D像檢索。

E-mail:wujunfeng0411@gmail.com

網(wǎng)絡(luò)優(yōu)先出版地址：http://www.cnki.net/kcms/detail/11.2422.TN.20150706.1606.009.html

Parallel algorithm of Global Skyline on time series

LI Yuan-yuan1,2, QU Wen-yu1, LI Zhi-yang1, JI Chang-qing1,3, WU Jun-feng1,4

(1.CollegeofInformationScienceandTechnology,DalianMaritimeUniversity,Dalian116026,China;

2.CollegeofSoftwaretechnology,DailianJiaotongUniversity,Dalian116028,China; 3.Collegeof

PhysicalScienceandTechnology,DalianUniversity,Dalian116622,China; 4.Collegeof

InformationEngineering,DalianOceanUniversity,Dalian116023,China)

Abstract:Global Skyline query is a variant of the Skyline query which has been used for multiple objective decision making, business planning, network monitoring and data mining etc. The result set of Global Skyline query is close to the ones of dynamic Skyline query and reverse Skyline query. With the number of historical data increases, Skyline query on centralized system is not competent for big data and Skyline query for large-scale data on time series is a challenge. A parallel algorithm of Global Skyline on time series is proposed. Firstly, we present a inverted index based on data on time series. Secondly, we provide the concept of Global Skyline cell which can eliminate the dominated cells according to the cell dominance relationship. The coarse grained pruning strategy can help to avoid a lot of meaningless computation. The query point divides the data space into the four quadrants, Global Skyline query can be executed in eachquadrant circularly. Lastly through extensive experiments with both real-world and synthetic datasets, we show that our algorithm is much more efficient for big data on time series.

Keywords:Global Skyline query; MapReduce; big data; time series

作者簡(jiǎn)介：

中圖分類號(hào)：TP 311

文獻(xiàn)標(biāo)志碼：A

DOI:10.3969/j.issn.1001-506X.2016.01.33

基金項(xiàng)目：國(guó)家自然科學(xué)基金(61173165，61300187，61370198，61370199，U1433124)；中央高?；究蒲袠I(yè)務(wù)費(fèi)專項(xiàng)資金(31322013044，31322013029，3132014325，3132013335)；遼寧省教育廳科學(xué)研究一般項(xiàng)目(L2015092，L2014492，L2014283，L2014191)；江蘇省未來(lái)網(wǎng)絡(luò)創(chuàng)新研究院未來(lái)網(wǎng)絡(luò)前瞻性研究項(xiàng)目資助課題

收稿日期：2014-12-03；修回日期：2015-05-03；網(wǎng)絡(luò)優(yōu)先出版日期：2015-07-06。