基于MapReduce的連續(xù)概率Skyline查詢*

單觀敏，董一鴻，何賢芒

寧波大學(xué) 信息科學(xué)與工程學(xué)院，浙江 寧波 315211

基于MapReduce的連續(xù)概率Skyline查詢*

單觀敏，董一鴻+，何賢芒

寧波大學(xué) 信息科學(xué)與工程學(xué)院，浙江 寧波 315211

SHAN Guanmin,DONG Yihong,HE Xianmang.Continuous probabilistic Skyline query based on MapReduce. Journal of Frontiers of Computer Science and Technology,2016,10(2):182-193.

大數(shù)據(jù)對傳統(tǒng)的Skyline研究產(chǎn)生了挑戰(zhàn)，利用并行框架MapReduce計算大數(shù)據(jù)下的Skyline已成為一個研究熱點。研究了不確定移動對象的Skyline查詢問題，提出了一種MapReduce框架下基于事件跟蹤的連續(xù)概率Skyline查詢算法——MR-DTrack（domination-track algorithm based on MapReduce）。首先采用基于角度的劃分方法保證負(fù)載均衡,通過預(yù)計算獲取Skyline集可能變化的時刻,在Reduce階段獲取候選概率Skyline集；然后利用局部過濾點剪枝，減少計算開銷；最后合并計算出全局概率Skyline集。在人工數(shù)據(jù)集和真實數(shù)據(jù)集上的實驗驗證了算法的有效性。

MapReduce；Hadoop；概率Skyline；不確定移動對象

1　引言

應(yīng)用于多目標(biāo)決策之一的Skyline查詢返回不被其他對象“支配”的對象（“支配”指的是對象a在所有屬性上不比對象b“差”且至少在一個屬性上“好”于對象b）。例如，行走中的手機(jī)用戶需要查詢離他最近的旅館，一般用戶會選擇價格便宜，距離最近的旅館。然而現(xiàn)實中由于設(shè)備的誤差或者出于隱私保護(hù)等安全方面的考慮，用戶的位置是不精確的（通常認(rèn)為是一個區(qū)域，如圖1），也就是說用戶到旅館的距離并不是精確的，此時不能簡單判斷兩個點之間的支配關(guān)系。同時，隨著大數(shù)據(jù)的出現(xiàn)，傳統(tǒng)的Skyline查詢已無法很好地處理海量數(shù)據(jù)，這成為一個需要解決的問題。本文主要研究MapReduce框架下查詢點為不確定區(qū)域而其他數(shù)據(jù)點靜止情形下的Skyline查詢問題。為簡化問題，假設(shè)查詢點的運動是勻速直線運動。

Fig.1　Illustration of uncertain moving object圖1　不確定移動對象示例

本文的主要貢獻(xiàn)如下：

（1）研究了大數(shù)據(jù)下移動對象的連續(xù)概率Skyline查詢，通過局部區(qū)域過濾點剪枝機(jī)制提高效率。

（2）提出并實現(xiàn)了基于事件跟蹤更新局部支配數(shù)據(jù)點的MR-DTrack算法（domination-track algorithm based on MapReduce），實現(xiàn)了移動環(huán)境下基于MapReduce的連續(xù)概率Skyline查詢。

（3）通過實驗將本文提出的新算法與基本算法進(jìn)行了比較，實驗結(jié)果顯示了新算法的有效性。

2　研究現(xiàn)狀

Borzsonyi等人[1]首次在數(shù)據(jù)庫社區(qū)提出了Skyline操作，并且提出了塊循環(huán)嵌套算法（block nested loop,BNL）和分治法（divide-and-conquer,D&C）兩種算法。文獻(xiàn)[2]將原始數(shù)據(jù)集編碼成位圖（bitmap），提出了一種基于索引（index）的方法。Kossmann等人[3]基于R-tree索引結(jié)構(gòu)提出了最近鄰算法（nearest neighbor,NN）；Papadias等人[4]改進(jìn)NN算法提出了分支限界法（branch and bound Skyline,BBS）。Balke等人[5]提出了垂直分布數(shù)據(jù)庫中用輪詢方式的基本分布式Skyline算法（basic distributed Skyline,BDS）和改進(jìn)的分布式Skyline算法（improved distributed Skyline,IDS）。Cui等人[6]通過對最小邊界矩形（minimum bounding rectangle,MBR）按“不可比較關(guān)系”進(jìn)行分組，采用傳遞和反饋的方式提出了PaDSkyline（parallel distributed Skyline query processing）算法。

Huang等人[7]研究了查詢點移動情況下的Skyline問題，提出了連續(xù)跟蹤算法CSQ（continuous Skyline query），首先計算出初始時刻的Skyline，計算下一時刻造成Skyline集合變化的事件，使用查找邊界有效減少了不必要的計算。Tian等人[8]研究了數(shù)據(jù)點移動而查詢點不動情況下的Skyline查詢，使用網(wǎng)格劃分空間，算法只需動態(tài)地維護(hù)受影響區(qū)域和Skyline集合。付世昌等人[9]研究了位置不確定移動對象的Skyline查詢，提出了一種不確定移動對象連續(xù)概率Skyline查詢算法（continuous probabilistic Skyline computation algorithm for uncertain movingobject,U-CPSC）。樊明鎖等人[10]研究了分布式環(huán)境下位置不確定移動對象的概率Skyline查詢，提出了CDPS-UMO（continuous distributed probabilistic Skyline algorithm for uncertain moving object）算法。

Vlachou等人[11]從數(shù)據(jù)劃分的角度研究了并行計算Skyline的問題，提出了基于角度的劃分、格劃分、等量劃分和動態(tài)劃分等數(shù)據(jù)劃分方法。Park等人[12]研究了多核架構(gòu)下的并行Skyline計算問題，提出了并行BBS算法和pskyline算法。Kohler等人[13]通過超平面映射劃分的方法并行計算Skyline。張波良等人[14]研究了MapReduce框架下海量數(shù)據(jù)集的Skyline查詢問題，提出了基于MapReduce的塊循環(huán)嵌套算法（MR-BNL）、基于MapReduce的排序過濾算法（MRSFS）和基于MapReduce的位圖算法（MR-Bitmap）。MR-BNL和MR-SFS算法將數(shù)據(jù)按網(wǎng)格劃分計算局部Skyline再合并計算全局Skyline，而MR-Bitmap利用全局位圖計算Skyline。Chen等人[15]提出了將數(shù)據(jù)按角度劃分來計算Skyline的算法（MR-Angle）。丁琳琳等人[16]引入全局過濾的方法，提出了延遲Skyline查詢算法、貪婪Skyline查詢算法和混合Skyline查詢算法。雷婷等人[17]采用空間分區(qū)樹的啟發(fā)式方法提出了基于超球面投影分區(qū)的分布式Skyline算法。Park等人[18]提出使用sky-quadtree和rsky-quadtree分別處理Skyline和反Skyline的計算。Ding等人[19]研究了MapReduce框架下不確定數(shù)據(jù)上的概率Skyline查詢，通過“Filter”和“Refine”兩個階段計算得到最終結(jié)果。

3　相關(guān)概念

定義1（靜態(tài)支配[1]）給定d維靜態(tài)屬性集D中兩個對象 p1、p2，其中 p1.Ai為 p1在第i個靜態(tài)維的坐標(biāo)，不失一般性，假設(shè)對象的屬性值越小越好，若在所有靜態(tài)維度i上有，且對于至少一個靜態(tài)維j上有，則稱p1靜態(tài)支配p2，記作p1?Sp2。

定義2（支配[20]）設(shè)d維靜態(tài)和一維距離屬性集D中兩個對象為p1、p2，p1.Ai為p1在第i個靜態(tài)維的坐標(biāo)，若 p1?Sp2且在距離屬性上有，則稱p1支配p2，記作p1?p2。

定義3（支配概率[9]）設(shè)d維靜態(tài)和一維距離屬性集D中兩個對象為p1、p2，p1支配p2的概率可以表示為：

Fig.2　Varity of query area圖2　查詢區(qū)域位置變化示意圖

從圖2中可以看出，當(dāng)移動對象區(qū)域與p1分處中垂線兩側(cè)時，，p1無法支配 p2，此時P(p1?p2)=0；當(dāng)不確定區(qū)域與中垂線相交時，此時稱 p1部分支配 p2，表示為 p1?Pp2，0＜P (p1?p2)＜1；當(dāng)區(qū)域與 p1同處一側(cè)時，此時P(p1?p2)=1，此時稱p1完全支配p2，標(biāo)記為p1?Fp2。

通常情況下，查詢者并不需要得到所有Skyline集合，只需要返回Skyline概率大于給定閾值λ的集合。

定義4（Skyline概率[9]）給定數(shù)據(jù)集D，對于pi∈D，t時刻其不被D中其他數(shù)據(jù)點支配的概率稱為pi的Skyline概率，用公式表示為：

定義5（局部概率Skyline集[10]） t時刻部分?jǐn)?shù)據(jù)集Di∈D中所有Skyline概率大于給定閾值λ的點的集合稱為 t時刻的局部概率Skyline集合，記為PSKYlocal(t)。

定義6（全局概率Skyline集[10]） t時刻數(shù)據(jù)集D中所有Skyline概率大于給定閾值λ的點的集合稱為全局動態(tài)Skyline集，簡稱全局Skyline集，記為PSKYglobal(t)。

本文使用的符號如表1所示。

Table 1　Symbol table表1　符號表

4　基于MapReduce的支配跟蹤算法

MapReduce框架下連續(xù)概率Skyline查詢的基本算法過程如下：首先在Map階段將數(shù)據(jù)集根據(jù)文獻(xiàn)超球面坐標(biāo)進(jìn)行角度劃分；然后Reduce階段分別計算各區(qū)域內(nèi)的概率Skyline集，刪除Skyline概率小于閾值λ的數(shù)據(jù)點；最后使用一個MapReduce合并各個區(qū)域的概率Skyline集，計算全局的概率Skyline集?；舅惴ǖ娜毕菰谟诿看斡嬎愣夹枰匦卤容^數(shù)據(jù)點和計算局部的概率Skyline集，造成重復(fù)計算，因此所需的時間開銷很大。顯然計算過程中，影響某個數(shù)據(jù)點Skyline概率的數(shù)據(jù)點也不是大量變化，因此如果能事先計算某個點影響概率Skyline集合以及其他數(shù)據(jù)點影響該數(shù)據(jù)點的Skyline概率的時間，就能在一定程度上減少重復(fù)計算，從而減少計算開銷。因此本文提出了基于MapReduce的支配跟蹤算法MR-DTrack。

考慮到計算的負(fù)載平衡問題，本文算法采用了基于角度劃分[11,15]的方法，即將每個數(shù)據(jù)點的笛卡爾坐標(biāo)轉(zhuǎn)化為球坐標(biāo)，根據(jù)球坐標(biāo)將數(shù)據(jù)集均勻劃分為若干區(qū)域，笛卡爾坐標(biāo)計算公式如下：

MR-DTrack算法主要分為兩個階段：預(yù)處理和跟蹤計算。

4.1預(yù)處理

假設(shè)在二維空間內(nèi)勻速直線運動的查詢點q的初始時刻位置坐標(biāo)為(x0,y0)，速度為(vx,vy)，數(shù)據(jù)點p的坐標(biāo)為(xp,yp)，那么數(shù)據(jù)點p到查詢點q的歐式距離函數(shù)可以表示為[9]：

因為本文的查詢點假設(shè)為一個不確定區(qū)域，所以每個數(shù)據(jù)點到查詢區(qū)域均有最小距離函數(shù)和最大距離函數(shù)。對于兩個數(shù)據(jù)點來說，某個數(shù)據(jù)點的最小距離函數(shù)和另一數(shù)據(jù)點的最大距離函數(shù)之間總共可以形成兩個交點，假設(shè)tbegin為較早的時刻，而tend為較晚的時刻。其他數(shù)據(jù)點對p支配關(guān)系變化有兩種情形：若 u?Sp，當(dāng) t＜tbegin時，有 dist(x,u,t)＜dist(x,p,t)，此時u?Fp，當(dāng)tbegin≤t≤tend時，u?Pp，當(dāng)t＞tend時，因為dist(x,u,t)＞dist(x,p,t)，所以此時u無法支配p，將此類事件稱為“DTU”；若u?Sp，當(dāng)t＜tbegin時，有 dist(x,u,t)＞dist(x,p,t)，此時u不支配p，當(dāng)tbegin≤t≤tend時，u?Pp，當(dāng)t＞tend時，由于dist(x,u,t)＜dist(x,p,t)，則u?Fp，此時p不是概率Skyline點，將這種情形稱為“UTD”。

本文將非概率Skyline數(shù)據(jù)點不被其他數(shù)據(jù)點完全支配的時刻定義為tin，同樣定義概率Skyline數(shù)據(jù)點被其他數(shù)據(jù)點完全支配的時刻為tout。對于數(shù)據(jù)點p而言，其與其他數(shù)據(jù)點產(chǎn)生“DTU”的最晚時間即為所求的tin，因為在這個時間之前至少存在一個數(shù)據(jù)點支配p，也就是之前p不可能是概率Skyline點，其他數(shù)據(jù)點對于p的Skyline概率無影響。類似地，p發(fā)生“UTD”的最早時間即為tout，tout之后p不可能是概率Skyline點，其他數(shù)據(jù)點對于p的Skyline概率無影響。因此可以利用tin和tout時刻提前剪枝掉對p的Skyline概率無影響的一些事件。

算法1是預(yù)處理的偽代碼，基本思路是：Map階段將數(shù)據(jù)集按角度劃分?jǐn)?shù)據(jù)集。Reduce階段首先計算出兩個數(shù)據(jù)點之間的靜態(tài)支配關(guān)系和支配關(guān)系，然后根據(jù)距離計算公式計算出兩個相交時間tbegin和tend，根據(jù)相交時刻的事件類型將相應(yīng)事件插入到事件列表EQi，同時更新最晚DTU的時刻tin和最早UTD的時刻tout，如果Sk?PPj，則將Sk加入到Pj所在的支配列表存放候選概率Skyline點以及其被部分支配的數(shù)據(jù)點）中。接著使用tin和tout對事件列表EQi的事件進(jìn)行更新。最后與其他點比較后，需要對EQi進(jìn)行升序排序。循環(huán)地對每個數(shù)據(jù)點進(jìn)行處理。

算法1 DTrackPreprocess

4.2跟蹤計算

顯然，對于 u?Sp，如果 P(u?p)＞1-λ，則Psky(p)＜λ。由于Reduce可能需要處理多個區(qū)域的數(shù)據(jù)集，本文采用了基于過濾點傳遞剪枝的方式來剪枝掉一些不可能成為概率Skyline的數(shù)據(jù)點。首先Reduce階段的一個Slave節(jié)點計算出某個區(qū)域的概率Skyline集合后，選出f值（靜態(tài)支配度[10]，即靜態(tài)支配其他數(shù)據(jù)點的數(shù)目）最小的概率Skyline點作為下一個區(qū)域的過濾點。然后在計算出下一個區(qū)域的局部概率Skyline時使用過濾點剪枝掉被過濾點支配的概率大于1-λ的數(shù)據(jù)點，最后計算出新過濾點。

事件跟蹤更新的基本過程如下：Reduce階段取出小于當(dāng)前時刻tcurrent的事件，并且更新支配列表PDOMlocali(t)，其中更新過程包括刪除無法支配的數(shù)據(jù)點，插入部分支配的數(shù)據(jù)點和刪除被完全支配的點等。然后根據(jù)支配列表PDOMlocali(t)計算出候選概率Skyline點的Skyline概率，如果Skyline概率不小于λ，則將其加入到局部概率Skyline集中。接著使用上述提出的過濾點剪枝方法剪枝掉不可能成為概率Skyline的數(shù)據(jù)點。最后使用一個MapReduce過程合并計算出全局概率Skyline集。

算法2 DTrackProcess

完整的MR-Track算法（即算法3）先使用算法1預(yù)計算出數(shù)據(jù)點兩兩之間的支配關(guān)系發(fā)生變化的事件，再通過算法2更新計算每個時刻的局部概率Skyline集合，從而計算出全局概率Skyline。

算法3 MR-DTrackAlgorithm

4.3時間復(fù)雜度

預(yù)處理階段，假設(shè)第i個Map分割到的數(shù)據(jù)點數(shù)量為ri（假設(shè)共有d個Map），計算球坐標(biāo)、計算所屬區(qū)域號和輸出所需時間為ta，Map階段計算所需時間為max(ri×ta)。本文假設(shè)Shuffle將數(shù)據(jù)集分為u個區(qū)域，第j個區(qū)域的數(shù)據(jù)點數(shù)量為nj，判斷支配關(guān)系，計算相交時刻，更新tin和tout等可以在tb時間內(nèi)完成，插入支配列表可在td時間內(nèi)完成，輸出的支配列表最多為。快速排序最多需要(2nj)2。因此預(yù)處理階段的時間復(fù)雜度為，近似為O(N2)。

跟蹤處理的Event Job中，假設(shè)第k個Map分割到的數(shù)據(jù)點數(shù)量為lk（假設(shè)共有e個Map），輸出可在tc內(nèi)完成，則Map階段所需時間為max(lk×tc)。因為按靜態(tài)屬性劃分區(qū)域，所以第j個區(qū)域的局部數(shù)據(jù)點全集數(shù)量始終不變?yōu)閚j。而事件隊列中的事件最多為，每次更新可在tupdate內(nèi)完成，所以更新局部Skyline最多需要，使用過濾點剪枝最多需要nj，選出過濾點最多需要nj，輸出最多需要nj。因此最差情況下查詢處理的時間復(fù)雜度為，近似為O(N2)。

在Merging Job中，假設(shè)第k個Map分割到的數(shù)據(jù)點數(shù)量為lk（假設(shè)共有e個Map），則Map階段所需時間為max(lk)。Reduce階段的最差時間復(fù)雜度為O(N2)，因此合并階段的時間復(fù)雜度近似為O(N2)。

5　實驗評估

實驗在4臺PC機(jī)組成的集群上進(jìn)行，其中1臺作為Master節(jié)點，其余3臺作為Slave節(jié)點。PC具體配置如下：CPU為Intel Core i3 3.4 GHz，內(nèi)存為4 GB，操作系統(tǒng)為CentOS 6.3，Hadoop版本為1.0.3，JDK版本為1.6。

實驗采用了人工合成數(shù)據(jù)集和真實數(shù)據(jù)集。利用文獻(xiàn)[1]的生成工具生成3種人工數(shù)據(jù)集，每種數(shù)據(jù)集默認(rèn)包含1×106個對象，其中靜態(tài)維度為3維，每一維屬性的取值范圍為(0,1 000]的雙精度浮點數(shù)，3種數(shù)據(jù)集分別服從獨立、正相關(guān)和反相關(guān)3種分布，對象的位置屬性隨機(jī)生成。真實數(shù)據(jù)集的地理位置屬性采用北美地區(qū)33 696個人口稠密地點和文化地標(biāo)，靜態(tài)屬性為6維獨立分布數(shù)據(jù)。

對文獻(xiàn)[15]中的MR-Angle算法稍作修改，即在計算局部Skyline階段和合并局部概率Skyline計算階段計算概率Skyline集合，將其命名為MR-Basic算法。實驗假設(shè)不確定區(qū)域為均勻分布的圓（半徑r=9），閾值λ=0.3，通過調(diào)整數(shù)據(jù)規(guī)模N、靜態(tài)維度d、Slave節(jié)點數(shù)n等參數(shù)設(shè)置來考察MR-Basic算法和本文MR-DTrack算法在這3種數(shù)據(jù)集上的平均響應(yīng)時間（10次查詢的平均時間）和MapReduce過程中輸入輸出的元組數(shù)之和，從而驗證算法的有效性。

5.1人工數(shù)據(jù)集

5.1.1數(shù)據(jù)規(guī)模對算法的影響

本次實驗主要通過調(diào)整數(shù)據(jù)規(guī)模N的大小考察數(shù)據(jù)規(guī)模N對算法的影響，其他參數(shù)設(shè)置如下：節(jié)點數(shù)n=4，靜態(tài)維度d=3，移動區(qū)域速度=(6,10)，球坐標(biāo)的每一維劃分4部分（d維數(shù)據(jù)空間可分為4d部分）。圖3顯示了均勻分布圓模型下數(shù)據(jù)規(guī)模對算法的響應(yīng)時間的影響。從實驗結(jié)果中可見，隨著數(shù)據(jù)規(guī)模的增加，3種數(shù)據(jù)集上的響應(yīng)時間都出現(xiàn)了增長，其中反相關(guān)增長速度最快。這是因為反相關(guān)數(shù)據(jù)集中數(shù)據(jù)點成為Skyline的可能性要大于其他兩種數(shù)據(jù)集，而對于正相關(guān)而言，成為Skyline的數(shù)據(jù)點顯然少于其他兩種數(shù)據(jù)集。圖4顯示了響應(yīng)時間和輸入輸出元組數(shù)上MR-DTrack算法要好于MR-Basic算法。

圖5是不同分布模型下數(shù)據(jù)規(guī)模對算法元組數(shù)的影響，Circle-Uniform表示均勻分布圓模型，Circle-Gaussian表示高斯分布圓模型，Ellipse-Uniform表示均勻分布橢圓模型，Ellipse-Gaussian表示高斯分布橢圓模型。圖5顯示出3種數(shù)據(jù)分布（獨立、正相關(guān)、反相關(guān)）在4種查詢點區(qū)域模型下隨著數(shù)據(jù)規(guī)模的擴(kuò)大，元組數(shù)也隨之增加，因為數(shù)據(jù)規(guī)模擴(kuò)大，Skyline集也隨之增大。在同一數(shù)據(jù)規(guī)模下，均勻分布模型的元組個數(shù)稍少于高斯分布，因為高斯分布的模型中心密度大，計算出的概率Skyline集合被閾值裁減的個數(shù)少。

Fig.3　Effect of dataset size for response time in uniform distribution circle model圖3　均勻分布圓模型中數(shù)據(jù)規(guī)模對響應(yīng)時間的影響

5.1.2靜態(tài)維度對算法的影響

Fig.4　Effect of dataset size for tuple number in uniform distribution circle model圖4　均勻分布圓模型中數(shù)據(jù)規(guī)模對元組數(shù)的影響

Fig.5　Effect of dataset size for MR-DTrack tuple number in different distribution models圖5　不同分布模型中數(shù)據(jù)規(guī)模對MR-DTrack算法元組數(shù)的影響

Fig.6　Effect of static dimensionality for response time in uniform distribution circle model圖6　均勻分布圓模型中靜態(tài)維度對響應(yīng)時間的影響

本實驗通過調(diào)整靜態(tài)維度d的大小以考察靜態(tài)維度對算法的影響，其他參數(shù)不變。圖6顯示隨著維度的增加，響應(yīng)時間也隨之增加，但獨立數(shù)據(jù)集和負(fù)相關(guān)數(shù)據(jù)集上隨維度增加快，因為元組間不支配的可能性增大，導(dǎo)致Reduce階段合并計算量增加。圖7顯示輸入輸出元組數(shù)隨著維度增加而增長，MRDTrack算法產(chǎn)生的元組數(shù)明顯少于MR-Basic算法。圖8是MR-DTrack算法在不同分布模型下隨著維度的增加元組數(shù)的變化。維度增加后，不被支配的點集增大較快，在實驗中明顯顯示出這點。同樣維度下，兩種均勻分布模型的元組個數(shù)少于高斯分布，因為高斯分布的模型計算出的概率Skyline集合被閾值裁減的個數(shù)少。

5.1.3Slave節(jié)點數(shù)對算法的影響

本次實驗通過設(shè)置不同的Slave節(jié)點數(shù)考察計算節(jié)點數(shù)對算法的影響。圖9顯示算法響應(yīng)時間隨Slave節(jié)點數(shù)的增加而減小，因為節(jié)點數(shù)較少的情況下Hadoop無法很好滿足計算所需的內(nèi)存開銷，而隨著節(jié)點數(shù)的增加，能較好處理數(shù)據(jù)，這時算法只受Hadoop框架的影響。

Fig.7　Effect of static dimensionality for tuple number in uniform distribution circle model圖7　均勻分布圓模型中靜態(tài)維度對元組數(shù)的影響

Fig.8　Effect of static dimensionality for MR-DTrack tuple number in different distribution models圖8　不同分布模型中靜態(tài)維度對MR-DTrack算法元組數(shù)的影響

Fig.9　Effect of Slave node number for running time in uniform distribution circle model圖9　均勻分布圓模型中Slave節(jié)點數(shù)對響應(yīng)時間的影響

5.2真實數(shù)據(jù)集

5.2.1Slave節(jié)點數(shù)對算法的影響

本實驗在北美地區(qū)33 696個人口稠密地點和文化地標(biāo)的真實數(shù)據(jù)集上進(jìn)行（http://www.chorochro-nos.org）。圖10顯示隨節(jié)點數(shù)的增加算法響應(yīng)時間減小。圖11顯示出節(jié)點數(shù)對元組數(shù)影響不大，說明不被支配的總對象數(shù)不受節(jié)點數(shù)的影響。

5.2.2移動速度對算法的影響

本實驗主要考察移動速度對算法的影響。從圖12可以看出，隨著移動速度的增加，導(dǎo)致算法響應(yīng)時間出現(xiàn)一定程度的下降，元組數(shù)也同樣稍有下降。

Fig.10　Effect of Slave node number for running time in uniform distribution circle model圖10　均勻分布圓模型中Slave節(jié)點數(shù)對響應(yīng)時間的影響

Fig.11　Effect of Slave node number for MR-DTrack tuple number in different distribution models圖11　不同分布模型中Slave節(jié)點數(shù)對MR-DTrack算法元組數(shù)的影響

Fig.12　Effect of velocity for running time and tuple number in uniform distribution circle model圖12　均勻分布圓模型中移動速度對響應(yīng)時間和元組數(shù)的影響

6　總結(jié)

本文研究了查詢點為移動的不確定區(qū)域時的Skyline計算問題，通過預(yù)處理提前計算出數(shù)據(jù)點支配關(guān)系發(fā)生變化的時刻，更新每個節(jié)點的局部Skyline集，減少了計算時間，又通過局部過濾點剪枝的方法減少合并的元組數(shù)，提高了算法效率。實驗結(jié)果證明了算法的有效性。

References:

[1]Borzsonyi S,Kossmann D,Stocker K.The Skyline operator [C]//Proceedings of the 17th International Conference on Data Engineering,Heidelberg,Apr 2-6,2001.Piscataway, USA:IEEE,2001:421-430.

[2]Tan K L,Eng P K,Ooi B C.Efficient progressive skyline computation[C]//Proceedings of the 27th International Conference on Very Large Data Bases,Roma,Italy,Sep 11-14, 2001.San Fransisco,USA:Morgan Kaufmann,2001:301-310.

[3]Kossmann D,Ramsak F,Rost S.Shooting stars in the sky: an online algorithm for skyline queries[C]//Proceedings of the 28th International Conference on Very Large Data Bases, Hong Kong,China,Aug 20-23,2002.San Fransisco,USA: Morgan Kaufmann,2002:275-286.

[4]Papadias D,Tao Yufei,Fu G,et al.An optimal and progressive algorithm for skyline queries[C]//Proceedings of the2003 ACM SIGMOD International Conference on Management of Data,San Diego,USA,Jun 9-12,2003.New York, USA:ACM,2003:467-478.

[5]Balke W T,Güntzer U,Zheng J X.Efficient distributed skylining for Web information systems[C]//LNCS 2992:Proceedings of the 9th International Conference on Extending Database Technology,Heraklion,Greece,Mar 14-18,2004. Berlin,Heidelberg:Springer,2004:256-273.

[6]Cui Bin,Lu Hua,Xu Quanqing,et al.Parallel distributed processing of constrained skyline queries by filtering[C]// Proceedings of the 24th IEEE International Conference on Data Engineering,Cancun,Mexico,Apr 7-12,2008.Piscataway,USA:IEEE,2008:546-555.

[7]Huang Zhiyong,Lu Hua,Ooi B C,et al.Continuous skyline queries for moving objects[J].IEEE Transactions on Knowledge and Data Engineering,2006,18(12):1645-1658.

[8]Tian Li,Wang Le,Zou Peng,et al.Continuous monitoring of skyline query over highly dynamic moving objects[C]// Proceedings of the 6th ACM International Workshop on Data Engineering for Wireless and Mobile Access,Beijing,China, Jun 10,2007.New York,USA:ACM,2007:59-66.

[9]Fu Shichang,Dong Yinhong,Tang Yanlin,et al.Continuous probabilistic Skyline queries for moving ojbects with uncertainty based on event[J].Acta Automatica Sinica,2011,37 (7):836-848.

[10]Fan Mingsuo,Tang Zhijun,Chen Huahui,et al.Continuous probabilistic Skyline queries under distributed environment [J].Computer Engineering and Applications,2013,49(15): 123-129.

[11]Vlachou A,Doulkeridis C,Kotidis Y.Angle-based space partitioning for efficient parallel skyline computation[C]// Proceedings of the 2008 ACM SIGMOD International Conference on Management of Data,Vancouver,Canada,Jun 9-12,2008.New York,USA:ACM,2008:227-238.

[12]Park S,Kim T,Park J,et al.Parallel skyline computation on multicore architectures[C]//Proceedings of the 25th IEEE International Conference on Date Engineering,Shanghai, China,Mar 29,2009.Piscataway,USA:IEEE,2009:760-771.

[13]K?hler H,Yang Jing,Zhou Xiaofang.Efficient parallel skyline processing using hyperplane projections[C]//Proceedings of the 2011 ACM SIGMOD International Conference on Management of Data,Athens,Greece,Jun 12-16,2011.New York,USA:ACM,2011:85-96.

[14]Zhang Boliang,Zhou Shuigeng,Guan Jihong.Skyline computation under MapReduce framework[J].Journal of Frontiers of Computer Science and Technology,2011,5(5):385-397.

[15]Chen Liang,Hwang Kai,Wu Jian.MapReduce Skyline query processing with a new angular partitioning approach[C]// Proceedings of the 26th IEEE International Parallel and Distributed Processing Symposium Workshops&PhD Forum, Shanghai,China,May 21-25,2012.Piscataway,USA:IEEE, 2012:2262-2270.

[16]Ding Linlin,Xin Junchang,Wang Guoren,et al.Efficient Skyline query processing of massive data based on Map-Reduce[J].Chinese Journal of Computers,2011,34(10): 1785-1796.

[17]Lei Ting,Wang Tao,Qu Wu,et al.Distributed Skyline processing based on hypersphere projection partitioning on cloud environments[J].Computer Science,2013,40(6): 164-171.

[18]Park Y,Min J K,Shim K.Parallel computation of Skyline and reverse Skyline queries using MapReduce[J].Proceedings of the VLDB Endowment,2013,6(14):2002-2013.

[19]Ding Linlin,Wang Guoren,Xin Junchang,et al.Efficient probabilistic Skyline query processing in MapReduce[C]// Proceedings of the 2013 IEEE International Congress on Big Data,Santa Clara,USA,Jun 27-Jul 2,2013.Piscataway,USA:IEEE,2013:203-210.

[20]Xiao Yingyuan,Lu K,Deng Huafeng.Location-dependent Skyline query processing in mobile databases[C]//Proceedings of the 7th Web Information Systems and Applications Conference,Hohhot,China,Aug 20-22,2010.Piscataway,USA: IEEE,2010:3-8.

附中文參考文獻(xiàn)：

[9]付世昌,董一鴻,唐燕琳,等.基于事件的位置不確定移動對象連續(xù)概率Skyline查詢[J].自動化學(xué)報,2011,37(7): 836-848.

[10]樊明鎖,湯志俊,陳華輝,等.分布式環(huán)境下連續(xù)概率Skyline查詢[J].計算機(jī)工程與應(yīng)用,2013,49(15):123-129.

[14]張波良,周水庚,關(guān)佶紅.MapReduce框架下的Skyline計算[J].計算機(jī)科學(xué)與探索,2011,5(5):385-397.

[16]丁琳琳,信俊昌,王國仁,等.基于Map-Reduce的海量數(shù)據(jù)高效Skyline查詢處理[J].計算機(jī)學(xué)報,2011,34(10): 1785-1796.

[17]雷婷,王濤,曲武,等.云環(huán)境下基于超球面投影分區(qū)的Skyline計算[J].計算機(jī)科學(xué),2013,40(6):164-171.

單觀敏（1987—），男，浙江紹興人，2014年于寧波大學(xué)獲得碩士學(xué)位，主要研究領(lǐng)域為數(shù)據(jù)挖掘。

董一鴻（1969—），男，浙江寧波人，2007年于浙江大學(xué)計算機(jī)科學(xué)與技術(shù)專業(yè)獲得博士學(xué)位，現(xiàn)為寧波大學(xué)教授，主要研究領(lǐng)域為大數(shù)據(jù)，數(shù)據(jù)挖掘，人工智能等。發(fā)表學(xué)術(shù)論文50余篇，主持參加國家自然科學(xué)基金、浙江省自然科學(xué)基金等項目。

何賢芒（1982—），男，浙江臺州人，2011年于復(fù)旦大學(xué)計算機(jī)科學(xué)與技術(shù)專業(yè)獲得博士學(xué)位，現(xiàn)為寧波大學(xué)講師，主要研究領(lǐng)域為大數(shù)據(jù)，數(shù)據(jù)挖掘，隱私保護(hù)等。發(fā)表學(xué)術(shù)論文20多篇，參加國家自然科學(xué)基金等項目。

Continuous Probabilistic Skyline Query Based on MapReduce*

SHAN Guanmin,DONG Yihong+,HE Xianmang
Faculty of Electrical Engineering and Computer Science,Ningbo University,Ningbo,Zhejiang 315211,China
+Corresponding author:E-mail:dongyihong@nbu.edu.cn

As big data has been a challenge to traditional Skyline research,computing Skyline using parallel framework of MapReduce is now a research hotspot.This paper studies a Skyline query of an uncertain moving object and proposes a continuous probabilistic Skyline query algorithm based on event tracking,named MR-DTrack(dominationtrack algorithm based on MapReduce).Firstly,partitioning method based on angular is adopted to make workload balance,a pre-computation is used to get the time when the Skyline sets change possibly,and the candidate probabilistic Skyline sets can be got in the Reduce stage.Then local filter points are used to prune in order to reduce computing costs.Finally,the global probabilistic Skyline set is computed by combining the candidate skyline sets.Experiments over artificial and real data sets prove the efficiency and effective of the new algorithm.

MapReduce;Hadoop;probabilistic Skyline;uncertain moving object

2015-05,Accepted 2015-07.

SHAN Guanmin was born in 1987.He the M.S.degree from Ningbo University in 2014.His research interest is date mining.

DONG Yihong was born in 1969.He the Ph.D.degree in computer science and technology from Zhejiang University in 2007.Now he is a professor at Ningbo University.His research interests include big data,data mining and artificial intelligence,etc.

HE Xianmang was born in 1982.He the Ph.D.degree in computer science and technology from Fudan University in 2011.Now he is a lecturer at Ningbo University.His research interests include big data,data mining and privacy preserving,etc.

10.3778/j.issn.1673-9418.1506006

*The Natural Science Foundation of Zhejiang Province under Grant No.LY16F020003(浙江省自然科學(xué)基金);the National Natural Science Foundation of China under Grant No.61202007(國家自然科學(xué)基金);the Key Courses Construction for Graduate of Ningbo University under Grant No.ZDKC2012006(寧波大學(xué)研究生重點課程建設(shè)).

CNKI網(wǎng)絡(luò)優(yōu)先出版：2015-07-03,http://www.cnki.net/kcms/detail/11.5602.TP.20150703.1558.002.html

A

TP391