李媛媛, 曲雯毓, 栗志揚, 季長清,3, 吳俊峰,4

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

遼寧 大連 116028; 3. 大連大學物理科學與技術學院, 遼寧 大連 116622;

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

?

基于時間序列的Global Skyline并行算法

李媛媛1,2, 曲雯毓1, 栗志揚1, 季長清1,3, 吳俊峰1,4

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

遼寧 大連 116028; 3. 大連大學物理科學與技術學院, 遼寧 大連 116622;

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

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

關鍵詞：Global Skyline查詢;MapReduce;大數據;時間序列

0引言

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

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

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

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

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

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

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

1問題描述

1.1點支配

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

1.2靜態(tài)Skyline

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

1.3動態(tài)Skyline

給定查詢點q,對于任意兩個對象pi,pj∈S,pi動態(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)|。

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

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

1.4Global Skyline

給定查詢點q,d維空間上的對象集合S中任意兩個對象pi,pj∈S,對象pi關于查詢點q全局支配pj滿足下面條件:

圖1　網絡監(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查詢的一種變種,考慮的是在有查詢點情況下的Skyline計算,比靜態(tài)Skyline計算復雜。同時與動態(tài)Skyline和反Skyline計算關系密切。它返回所有不被其他對象全局支配的對象集合。給定一個查詢點,查詢點把d維數據空間分割成2d個子象限。GlobalSkyline需要查詢得到所有子象限(2d個子象限)的全局Skyline點。本文分析的是基于時間序列的歷史數據,關于時間片的定義如下。

1.5時間片

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

有了時間片定義,可以推導出時間片上的支配關系:給定一個時間片[i:j]和對象集合S,滿足條件,若?k∈[i:j],pi[k]≤pj[k];并且?l∈[i:j],pi[l]

于是,給定一個對象集合S和一個時間片[i:j],該時間片上的Skyline如下:

(1)

2基于時間倒排索引的GlobalSkyline并行算法

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

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

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

圖2　系統(tǒng)模型

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

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

接下來本文將重點介紹此流程中的關鍵處理技術及重要數據結構。

2.1時間劃分模塊

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

圖3　時間劃分模型

給定一個對象集合S,每個數據點p的時間屬性值(t)在一個有界的區(qū)間[Tmin,Tmax],構造一個均勻的劃分{t0,…,tB},ti的定義如下:

(2)

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

(3)

2.2索引數據結構及流程

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

圖4　基于時間序列的倒排索引結構

(4)

以二維數據為例,帶時間維的數據點都可表示為P,t已被劃分,在同一時間片內的數據點可以表示為P。P可以通過公式(4)映射到對應網格當中去。

圖5　網格倒排索引生成過程

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

圖6　MapReduce生成索引流程

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

2.3GlobalSkyline格的計算

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

圖7　Global Skyline查詢與減枝

2.3.1單元格支配

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

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

①?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關于q全局支配cj,即ci?qcj。

2.3.2GlobalSkyline格

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

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

命題 1如果一個點p不在GlobalSkyline格中,那么它一定不是GlobalSkyline點。

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

證畢

推論 1任意一個GlobalSkyline點,它一定在某個GlobalSkyline格里。

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

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

由推論1可知,上述算法返回GlobalSkyline格中的數據點一定在GlobalSkyline結果集中,也就是GlobalSkyline格是GlobalSkyline的侯選集,接著掃描算法1得到的結果侯選集,進行支配關系比較,最終得到GlobalSkyline結果。

3實驗評測

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

3.1實驗配置

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

所有實驗均基于以下兩類數據集合進行:

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

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

圖8　模擬數據的3種數據分布

3.2實驗結果

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

圖9　剪枝與網格大小關系

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

圖10　網格生成時間與網格大小關系

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

表1　在模擬數據集下的運行時間　s

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

圖11　不同數據分布下算法的運行時間

圖12展示了算法運行時間。當實驗數據記錄條數固定為40 000萬條時,網格大小設置為1,B的值最小為2,最大為10變換。隨著B的值增大,時間片間隔變小,數據分組越多,每組當中的數據越少,算法的運行時間相應的變少。

圖12　算法的運行時間和B值關系

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

圖13　算法比較

圖14展示了模擬數據在不同數據分布下HDFS的I/O開銷,這里的I/O開銷是所有過程I/O的總和,包括建立索引階段。實驗的數據記錄條數,最小10 000萬條,最大40 000萬條。網格大小設置為1,B的值為1。如圖14所示,相同數據記錄的條件下,均勻分布的HDFS I/O開銷最小,正相關次之,反相關數據開銷最大。正相關數據和反相關數據I/O開銷差距不大,但都比均勻分布大很多。這是因為均勻分布剪枝階段的I/O開銷相對小的多。

圖14　不同數據分布的HDFS I/O

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

圖15　不同機器數下的加速比

4結論

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

參考文獻：

[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.(張麗,鄒鵬,賈焰,等.數據流上連續(xù)動態(tài)Skyline查詢研究[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.(田李,王樂,李愛平,等. 滑動窗口數據流上多極值查詢資源共享策略研究[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-),女,講師,博士研究生,主要研究方向為云計算、大數據信息檢索。

E-mail:lyy1135@dlmu.edu.cn

曲雯毓(1972-),女,教授,博士,主要研究方向為云計算、計算機網絡、信息檢索。

E-mail:wenyu@dlmu.edu.cn

栗志揚(1982-),男,副教授,博士,主要研究方向為圖像檢索、計算幾何。

E-mail:lizy@dlmu.edu.cn

季長清(1980-),男,副教授,博士研究生,主要研究方向為云計算、空間數據檢索。

E-mail:jcqgood@gmail.com

吳俊峰(1983-),男,講師,博士研究生,主要研究方向為圖像檢索。

E-mail:wujunfeng0411@gmail.com

網絡優(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

作者簡介：

中圖分類號：TP 311

文獻標志碼：A

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

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

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