分布式環(huán)境下連續(xù)概率Skyline查詢(xún)

樊明鎖，湯志俊，陳華輝，錢(qián)江波，董一鴻

分布式環(huán)境下連續(xù)概率Skyline查詢(xún)

樊明鎖，湯志俊，陳華輝，錢(qián)江波，董一鴻

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

1 引言

空間位置是影響人們?nèi)粘Ｉ钚袨榈囊粋€(gè)重要因素。在軟件或互聯(lián)網(wǎng)應(yīng)用中加入位置信息不僅可以更好地為用戶(hù)提供服務(wù)，也可以更好地理解用戶(hù)行為。近年來(lái)，通過(guò)與互聯(lián)網(wǎng)服務(wù)相結(jié)合，定位技術(shù)和基于位置的服務(wù)（Location-Based Service，LBS）（也稱(chēng)位置服務(wù)）開(kāi)始迅速發(fā)展。其中Skyline查詢(xún)[1]是LBS的一種重要應(yīng)用，它是指從給定的D-維空間的對(duì)象集合DB中選擇一個(gè)子集，該子集中的點(diǎn)都不能被DB中的任意一個(gè)其他點(diǎn)所控制。

在現(xiàn)實(shí)應(yīng)用中，一方面，考慮到更新成本、容錯(cuò)、性能等因素，數(shù)據(jù)經(jīng)常是物理上分散存放并通過(guò)網(wǎng)絡(luò)互相通信的；另一方面，由于受技術(shù)手段限制，對(duì)采集的移動(dòng)對(duì)象位置信息存在一定誤差，從而無(wú)法準(zhǔn)確地表示各數(shù)據(jù)點(diǎn)間的支配關(guān)系。

實(shí)例：如圖1所示，假設(shè)圖中的點(diǎn)分別代表的是兩個(gè)不同數(shù)據(jù)節(jié)點(diǎn)DB1和DB2上的旅館的空間位置(x，y)，表格顯示兩個(gè)不同節(jié)點(diǎn)上的餐館的位置坐標(biāo)和價(jià)格信息，并且以不確定區(qū)域（圖中Α、B）表示移動(dòng)對(duì)象的可能位置，以概率密度函數(shù)pdf(x)表示其真實(shí)位置的概率。假設(shè)移動(dòng)對(duì)象作為查詢(xún)點(diǎn)，沿直線(xiàn)作勻速運(yùn)動(dòng)，給定概率閾值q=0.3，R=0.5，通過(guò)計(jì)算得到：在t1時(shí)刻查詢(xún)點(diǎn)位于Α區(qū)域時(shí)，DB1中各數(shù)據(jù)點(diǎn)的局部Skyline概率分別是{0，0.6，0，1.0，0}，DB2中的局部Skyline概率分別是{1.0，1.0，1.0，0，0.2}，此時(shí)可得出全局Skyline概率分布是{0，0.6，0，1.0，0，1.0，0.3，0，0，0}，則大于閾值q的數(shù)據(jù)點(diǎn){2，4，6，7}構(gòu)成t1時(shí)刻的全局概率Skyline集合；t2時(shí)刻查詢(xún)點(diǎn)位于B區(qū)域時(shí)，DB1中各數(shù)據(jù)點(diǎn)的局部Skyline概率分別是{0，0，0.9，1.0，0}，DB2中的局部Skyline概率分布是{1.0，0，1.0，0，0}，此時(shí)t2時(shí)刻的全局概率Skyline集合變?yōu)閧3，4，6，8}。

圖1 分布式環(huán)境下不確定移動(dòng)對(duì)象的概率Skyline點(diǎn)

本文針對(duì)全局概率Skyline集合隨時(shí)間而不斷發(fā)生變化，提出了以位置不確定的移動(dòng)對(duì)象作為查詢(xún)點(diǎn)進(jìn)行分布式概率Skyline查詢(xún)的連續(xù)更新算法CDPS-UMO（Continuous Distributed Probabilistic Skyline algorithm for Uncertain Moving Object）。

2 預(yù)備知識(shí)

2.1 問(wèn)題描述

定義1（支配[1]和靜態(tài)支配）設(shè)兩個(gè)對(duì)象O1，O2的屬性分別為(x1，x2，…，xd)和(y1，y2，…，yd)，其中包括s維靜態(tài)屬性和一維動(dòng)態(tài)屬性（即d=s+1），若?i，xi≤yi都成立，且?j滿(mǎn)足xj＜yj(1≤i，j≤s)，則稱(chēng)O1靜態(tài)支配O2，表示為O1?sO2；且滿(mǎn)足O1.dist≤O2.dist成立，則稱(chēng)O1支配O2，表示為O1?O2。

定義2（靜態(tài)Skyline集合）靜態(tài)屬性上所有不被任何其他點(diǎn)支配的點(diǎn)的集合稱(chēng)為靜態(tài)Skyline集合(Ls-Sky)，其中每個(gè)點(diǎn)稱(chēng)為靜態(tài)Skyline點(diǎn)。

定義3（局部概率Skyline集合）t時(shí)刻局部子節(jié)點(diǎn)DBi中所有不被任何其他點(diǎn)支配的點(diǎn)的集合稱(chēng)為t時(shí)刻的局部概率Skyline集合，記為L(zhǎng)ip-Sky(t)。

定義4（全局概率Skyline集合）t時(shí)刻中心節(jié)點(diǎn)C中所有不被任何其他點(diǎn)支配的點(diǎn)的集合稱(chēng)為t時(shí)刻的全局概率Skyline集合，記為Gp-Sky(t)。

本文給出不確定移動(dòng)對(duì)象數(shù)據(jù)模型的定義如下：移動(dòng)對(duì)象MO在t時(shí)刻的不確定區(qū)域是任意一個(gè)封閉區(qū)域：Ur(t)，其概率密度分布函數(shù)記為pdf(x，t)，x∈Ur(t)，它描述了移動(dòng)對(duì)象MO在t時(shí)刻處于位置x的概率，在t時(shí)刻的移動(dòng)速度為νMO=(νMOx(t)，νMOy(t))。

2.2 概率Skyline連續(xù)跟蹤計(jì)算

Fu[2]等給出了時(shí)間參數(shù)化的距離函數(shù)、支配概率和Skyline概率的定義，其中時(shí)間距離函數(shù)是指不確定移動(dòng)對(duì)象MO與數(shù)據(jù)點(diǎn)Oi的歐式距離函數(shù)：dist(x，Oi，t)=（x∈Ur(t)，a，b，c是系數(shù)）。例如Oi、Oj是數(shù)據(jù)集O中兩數(shù)據(jù)點(diǎn)，Oi支配Oj的概率可以表示為：

其中|Oi.dist-x|表示數(shù)據(jù)點(diǎn)Oi到不確定區(qū)域Ur(t)中位置點(diǎn)x的距離。假設(shè)L是連接Oi、Oj兩點(diǎn)的線(xiàn)段|OiOj|的垂直平分線(xiàn)，COi是Oi與Ur(t)在L同側(cè)的區(qū)域，則數(shù)據(jù)點(diǎn)Oi對(duì)Oj的支配概率表示為：

對(duì)于計(jì)算數(shù)據(jù)點(diǎn)Oi的Skyline概率問(wèn)題，只需利用公式（1）和（2）與本節(jié)點(diǎn)中所有的數(shù)據(jù)點(diǎn)進(jìn)行計(jì)算即可，從而可得Skyline概率Pr(Oi)，如圖2所示。移動(dòng)對(duì)象移動(dòng)過(guò)程中，其與數(shù)據(jù)點(diǎn)間的距離不斷變化，造成數(shù)據(jù)點(diǎn)間支配關(guān)系的變化，從而可能引起概率Skyline集合從某個(gè)時(shí)刻開(kāi)始發(fā)生變化。如圖3所示，假設(shè)tbegin時(shí)刻之前P支配Q，而在tbegin和tend之間，P概率支配Q，tend時(shí)刻之后，P不支配Q，反之亦然。因此，在初始時(shí)刻提前計(jì)算出任意兩個(gè)數(shù)據(jù)點(diǎn)之間的交叉區(qū)間，稱(chēng)為event事件，通過(guò)提前計(jì)算目標(biāo)數(shù)據(jù)點(diǎn)之間產(chǎn)生的event類(lèi)型來(lái)快速地動(dòng)態(tài)計(jì)算目標(biāo)數(shù)據(jù)點(diǎn)的Skyline概率。

圖2 Skyline概率實(shí)例

圖3 支配關(guān)系變化實(shí)例

2.3 基本算法（naive）

移動(dòng)對(duì)象發(fā)起查詢(xún)開(kāi)始，基本算法首先分別計(jì)算出各節(jié)點(diǎn)t時(shí)刻局部概率Skyline集Lip-Sky(t)；然后傳送所有的Lip-Sky(t)到中心節(jié)點(diǎn)，將收到的Lip-Sky(t)合并后再重新計(jì)算出t時(shí)刻的全局概率Skyline集Gp-Sky(t)。查詢(xún)每一時(shí)刻都重復(fù)上述兩步計(jì)算，直到查詢(xún)終止。算法描述如下：

算法1 naive基本算法存在兩大缺陷：一是每一時(shí)刻的局部概率Skyline集都需要重新計(jì)算；二是所有的局部概率Skyline點(diǎn)都發(fā)送到中心節(jié)點(diǎn)，帶來(lái)巨大的通信開(kāi)銷(xiāo)。因此，本文出于這兩大缺陷，提出了高效和低通信開(kāi)銷(xiāo)的CDPS-UMO算法。

3 連續(xù)分布式概率Skyline查詢(xún)更新

通過(guò)對(duì)本文引用實(shí)例（圖1所示）的數(shù)據(jù)觀察和2.2節(jié)所述內(nèi)容可以得出，數(shù)據(jù)點(diǎn)的Skyline概率在靜態(tài)維上被其他點(diǎn)所支配的情況下才有可能發(fā)生變化，而且只有距離隨移動(dòng)對(duì)象的移動(dòng)而不斷變化，而其他因素隨移動(dòng)對(duì)象的移動(dòng)并沒(méi)有發(fā)生變化。因此充分考慮靜態(tài)維屬性的支配關(guān)系，提出有效的反饋策略，動(dòng)態(tài)更新全局概率Skyline集合。

3.1 排序方法

由于局部概率Skyline集合中的某些點(diǎn)并非是全局概率Skyline點(diǎn)，如何提前剪枝局部節(jié)點(diǎn)中不滿(mǎn)足全局概率Skyline點(diǎn)是降低通信開(kāi)銷(xiāo)的關(guān)鍵問(wèn)題，因此本文提出了反饋策略，從而就引出了反饋點(diǎn)的選擇問(wèn)題。本文依據(jù)靜態(tài)支配能力的思想，提出了有效的排序方法。

排序方法（Sort Method）數(shù)據(jù)集Di的Skyline集合中的任一點(diǎn)Oi，把被Oi所支配的對(duì)象數(shù)目記做靜態(tài)支配能力，對(duì)Skyline集合根據(jù)各個(gè)點(diǎn)的靜態(tài)支配能力執(zhí)行降序排列，記為(SM(Lip-Sky(t)))。

初始時(shí)刻的全局概率Skyline集合計(jì)算過(guò)程中，第一次迭代選擇所有局部節(jié)點(diǎn)DBi的SM(Lip-Sky(t0))排在第一位的點(diǎn)發(fā)送到中心節(jié)點(diǎn)，然后對(duì)得到的點(diǎn)執(zhí)行SM操作，從中選擇排在第一位的點(diǎn)反饋到其他節(jié)點(diǎn)中剪枝；以此類(lèi)推，直到局部概率Skyline集合為空為止。

3.2 反饋機(jī)制

反饋并不總是有效的——過(guò)多或不恰當(dāng)?shù)姆答佂鶎?duì)算法的整體性能帶來(lái)不良影響，因此提出一個(gè)有效的反饋機(jī)制對(duì)算法起到至關(guān)重要的作用。本文在第2章定義了支配和靜態(tài)支配的概念，靜態(tài)支配的定義對(duì)全局概率Skyline集合的連續(xù)跟蹤更新起到了重要的作用。通過(guò)公式（1）分析可知，在數(shù)據(jù)點(diǎn)Oi的Skyline概率計(jì)算過(guò)程中，若Oi在靜態(tài)維度上不被其他任何點(diǎn)所支配，則稱(chēng)Oi是靜態(tài)Skyline點(diǎn)，即Pr(Oi)=1，因此Oi必定是Skyline點(diǎn)；否則，Oi在靜態(tài)維度上被一個(gè)或多個(gè)點(diǎn)所支配，再利用式（1）（2）計(jì)算其Skyline概率，從而得出反饋機(jī)制。

反饋機(jī)制：每一時(shí)刻的全局概率Skyline集合更新過(guò)程中，利用初始時(shí)刻計(jì)算出的全局靜態(tài)Skyline集合（Static Skyline）反饋到各個(gè)子節(jié)點(diǎn)中提前剪枝非全局概率Skyline點(diǎn)。

3.3 算法實(shí)現(xiàn)

在算法中利用局部雙向鏈表Lip-Sky存儲(chǔ)當(dāng)前全部的局部概率Skyline點(diǎn)，全局雙向鏈表Gp-Sky存儲(chǔ)當(dāng)前全部的全局概率Skyline點(diǎn)，雙向鏈表Ls-Sky存儲(chǔ)全局靜態(tài)Skyline點(diǎn)，flag(own，else)標(biāo)識(shí)兩目標(biāo)數(shù)據(jù)點(diǎn)間的可能性支配關(guān)系。

3.3.1 Initial_LiP Skyline算法

算法Initial_LiPSkyline用于計(jì)算局部節(jié)點(diǎn)DBi初始時(shí)刻的局部概率Skyline。算法描述如下：

3.3.2 StaticSkyline算法

StaticSkyline算法主要用于計(jì)算初始時(shí)刻的全局概率Skyline集合(Gp-Sky)和靜態(tài)Skyline集合(Ls-Sky)。算法描述如下：

3.3.3 Feedback算法

該算法主要實(shí)現(xiàn)了全局概率Skyline集合的連續(xù)跟蹤更新。算法描述如下：

算法4 Feedback

3.3.4 CDPS-UMO基本框架

CDPS-UMO算法的基本思想是提前計(jì)算不確定移動(dòng)對(duì)象移動(dòng)過(guò)程中，可能引起局部概率Skyline集合變動(dòng)的events，通過(guò)對(duì)這些event的跟蹤計(jì)算從而不斷更新局部概率Skyline集合，與此之后采用有效的反饋策略不斷地快速更新全局概率Skyline集合?；究蚣苊枋鋈缦拢?/p>

3.3.5 算法性能分析

CDPS-UMO算法的時(shí)間復(fù)雜度為：

4 實(shí)驗(yàn)分析

4.1 數(shù)據(jù)集和不確定對(duì)象的分布

實(shí)驗(yàn)上使用Visual Studio C++2008實(shí)現(xiàn)了一個(gè)仿真系統(tǒng)，運(yùn)行環(huán)境為Windows 7的PC機(jī)。本文提出一個(gè)基本算法naive，與CDPS-UMO性能進(jìn)行比較，驗(yàn)證CDPS-UMO的有效性。

實(shí)驗(yàn)中數(shù)據(jù)的動(dòng)態(tài)維屬性是兩維的數(shù)據(jù)空間坐標(biāo)(x，y)，靜態(tài)維屬性是廣泛采用的三種遵循不同分布的模擬數(shù)據(jù)：（1）獨(dú)立數(shù)據(jù)（indep）；（2）正相關(guān)數(shù)據(jù)（corr）；（3）反相關(guān)數(shù)據(jù)（atti）。實(shí)驗(yàn)采用兩種不確定區(qū)域形狀：圓和橢圓，兩種概率密度函數(shù)分布：均為分布和高斯分布，分別對(duì)算法的性能進(jìn)行驗(yàn)證分析。其中CircleR表示采用圓形模型，R表示圓形區(qū)域半徑；表示橢圓模型，RL，RS分布表示橢圓的長(zhǎng)軸和短軸半徑。實(shí)驗(yàn)參數(shù)設(shè)置CircleR=10，EllipseR=(10，8)，閾值q=0.3，其他的參數(shù)的不同值詳見(jiàn)實(shí)驗(yàn)，默認(rèn)參數(shù)設(shè)置為d=2，m=3，N=9 000，ν(x，y)=（18，25）。

4.2 靜態(tài)維度d對(duì)算法影響

圖4 靜態(tài)維度在圓-均勻分布模型中對(duì)通信開(kāi)銷(xiāo)的影響

本實(shí)驗(yàn)中采用不同的靜態(tài)維數(shù)據(jù)空間維度d，考察靜態(tài)維度對(duì)算法性能的影響。

圖4顯示了在圓-均勻分布（Circle-Uniform）模型下，兩算法的對(duì)比實(shí)驗(yàn)。顯而易見(jiàn)，CDPS-UMO的通信開(kāi)銷(xiāo)性能遠(yuǎn)好于naive。與naive相比，CDPS-UMO的平均通信開(kāi)銷(xiāo)約是其40%。圖5描述了兩種算法在不同數(shù)據(jù)集上對(duì)反應(yīng)時(shí)間的影響，CDPS-UMO算法的平均反應(yīng)時(shí)間相比naive大約節(jié)省60%。雖然隨著維度的增加，數(shù)據(jù)點(diǎn)之間的支配關(guān)系減少，但是局部概率Skyline點(diǎn)隨之增多，引起元組轉(zhuǎn)移數(shù)目增多，因此算法的平均反應(yīng)時(shí)間隨著維度的增加而增加。圖6顯示了CDPS-UMO在四種不同不確定區(qū)域分布模型下對(duì)通信開(kāi)銷(xiāo)的影響。由圖可知，橢圓與圓、高斯分布與均勻分布模型相比較，隨著不確定區(qū)域的不規(guī)則程度增大，算法的通信開(kāi)銷(xiāo)增大。

圖5 靜態(tài)維度在圓-均勻分布模型中對(duì)反應(yīng)時(shí)間的影響

圖6 靜態(tài)維度在不同模型中對(duì)通信開(kāi)銷(xiāo)的影響

4.3 分布節(jié)點(diǎn)m對(duì)算法影響

本實(shí)驗(yàn)中采用不同的分布節(jié)點(diǎn)的數(shù)量m，考察分布節(jié)點(diǎn)對(duì)算法性能的影響。

分布節(jié)點(diǎn)m是影響算法效率的重要參數(shù)，如圖7和圖8所示，三種數(shù)據(jù)類(lèi)型在圓形-均勻分布模型中的元組轉(zhuǎn)移數(shù)目和反應(yīng)時(shí)間都呈上升趨勢(shì)。由圖可知，CDPS-UMO在三種不同分布數(shù)據(jù)模型中都明顯優(yōu)于靜態(tài)算法naive。圖9顯示了在不同不確定區(qū)域分布模型下，分布節(jié)點(diǎn)的數(shù)量變化對(duì)算法CDPS-UMO的影響。由圖可知，CDPS-UMO在四種分布模型下，平均通信開(kāi)銷(xiāo)隨分布節(jié)點(diǎn)的增加而不斷增大。顯而易見(jiàn)，圖9（c）相比于（a）、（b）付出更高的通信開(kāi)銷(xiāo)代價(jià)。

4.4 數(shù)據(jù)規(guī)模N對(duì)算法影響

圖7 分布節(jié)點(diǎn)在圓形-均勻分布模型中對(duì)通信開(kāi)銷(xiāo)的影響

圖8 分布節(jié)點(diǎn)在圓形-均勻分布模型中對(duì)反應(yīng)時(shí)間的影響

本實(shí)驗(yàn)中采用不同的數(shù)據(jù)規(guī)模N，考察數(shù)據(jù)規(guī)模對(duì)算法性能的影響。圖10顯示了數(shù)據(jù)規(guī)模對(duì)通信開(kāi)銷(xiāo)的影響。從圖中可知，隨著數(shù)據(jù)規(guī)模的增大，局部概率Skyline點(diǎn)增多，從而導(dǎo)致轉(zhuǎn)移次數(shù)增多。相比naive算法，CDPS-UMO表現(xiàn)出了更好的性能，大約節(jié)省了50%的代價(jià)。圖11描述了兩種算法在不同分布數(shù)據(jù)模型上對(duì)算法反應(yīng)時(shí)間的影響。CDPS-UMO的反應(yīng)時(shí)間明顯少于靜態(tài)算法naive，這是由于CDPS-UMO不需要重新遍歷整個(gè)數(shù)據(jù)集。

圖9 分布節(jié)點(diǎn)在不同模型中對(duì)通信開(kāi)銷(xiāo)的影響

圖10 數(shù)據(jù)規(guī)模在圓形-均勻分布模型中對(duì)通信開(kāi)銷(xiāo)的影響

圖11 數(shù)據(jù)規(guī)模在圓形-均勻分布模型中對(duì)反應(yīng)時(shí)間的影響

4.5 運(yùn)行速度對(duì)算法影響

本實(shí)驗(yàn)中采用不同的運(yùn)行速度ν(x，y)，不確定區(qū)域模型為圓-均勻分布（Circle-Uniform），數(shù)據(jù)集采用的是正相關(guān)數(shù)據(jù)和獨(dú)立數(shù)據(jù)。移動(dòng)對(duì)象的運(yùn)行速度對(duì)通信開(kāi)銷(xiāo)的影響不大，如圖12（a）和（b）。圖13說(shuō)明隨著速度的增加，算法CDPS-UMO和naive的平均運(yùn)算時(shí)間都不斷減少。但算法CDPS-UMO的處理時(shí)間主要用于局部節(jié)點(diǎn)上數(shù)據(jù)點(diǎn)間的支配概率計(jì)算，所以算法的平均運(yùn)算時(shí)間將趨向于平穩(wěn)。

5 相關(guān)工作

圖12 運(yùn)動(dòng)速度在圓形-均勻分布模型中對(duì)通信開(kāi)銷(xiāo)的影響

Borzsonyi[1]等首次將Skyline操作引入數(shù)據(jù)庫(kù)系統(tǒng)，并提出了BNL和D&C兩種計(jì)算方法[1]。文獻(xiàn)[3-5]又先后提出了位圖（bitmap）算法，索引（index）算法，最近鄰（NN）算法和BBS算法，其中BBS算法是集中式靜態(tài)環(huán)境下I/O最優(yōu)的算法。Huang[6]等研究了移動(dòng)對(duì)象環(huán)境下的連續(xù)Skyline計(jì)算問(wèn)題，提出了一個(gè)連續(xù)跟蹤算法CSQ。在文獻(xiàn)[6]的基礎(chǔ)上，F(xiàn)u[2]等充分考慮移動(dòng)環(huán)境下運(yùn)動(dòng)對(duì)象的位置不確定性，研究了查詢(xún)點(diǎn)移動(dòng)時(shí)的連續(xù)概率Skyline查詢(xún)。Balke[7]提出了第一個(gè)分布式Skyline算法——BDS算法，它基于Fagin[8]提出的ΤA算法。在此之后，Huang[9]等提出了MANEΤ上的分布式Skyline算法——SFP算法，定義了過(guò)濾元組。Zhu[10]等提出了基于反饋的分布式Skyline算法——FDS算法，給出了有利的反饋策略。Xiao[11]等研究了移動(dòng)設(shè)備下的分布式Skyline查詢(xún)，提出了多個(gè)過(guò)濾點(diǎn)作為反饋的EDS-MC算法。王曉偉[12]等首次研究了分布式不確定數(shù)據(jù)上的概率Skyline問(wèn)題，提出了共享全局剪枝空間的SPS算法。Ding[13]等提出了分布式不確定數(shù)據(jù)上的e-DSUD算法，其主要思想是采用多次反饋剪枝的策略來(lái)計(jì)算全局概率Skyline集合。Wang[14]等針對(duì)文獻(xiàn)[13]算法的缺點(diǎn)，提出了一種基于網(wǎng)格數(shù)據(jù)匯總的知識(shí)共享方法，并證明了算法的有效性。Rocha-Junior[15]等研究了大規(guī)模數(shù)據(jù)下的分布式Skyline查詢(xún)，并提出了有效的執(zhí)行計(jì)劃。與已有工作不同，本文采用不確定模型對(duì)移動(dòng)對(duì)象連續(xù)分布式概率Skyline查詢(xún)進(jìn)行研究。

圖13 運(yùn)動(dòng)速度在圓形-均勻分布模型中對(duì)反應(yīng)時(shí)間的影響

6 總結(jié)與展望

為了解決分布式環(huán)境下不確定移動(dòng)對(duì)象的連續(xù)概率Skyline計(jì)算問(wèn)題，本文首先提出了靜態(tài)支配度的概念，計(jì)算初始時(shí)刻的全局概率Skyline集合；然后利用初始時(shí)刻的全局Static Skyline集合反饋剪枝，有效地實(shí)現(xiàn)全局概率Skyline的連續(xù)更新。理論分析和實(shí)驗(yàn)結(jié)果證明了算法CDPS-UMO的有效性。進(jìn)一步的研究將關(guān)注分布式環(huán)境下查詢(xún)點(diǎn)移動(dòng)的同時(shí)，目標(biāo)對(duì)象也同時(shí)移動(dòng)的概率Skyline查詢(xún)，即查詢(xún)點(diǎn)和目標(biāo)對(duì)象的位置都具有不確定性的條件下的概率Skyline查詢(xún)。

[1]Borzsonyi S，Kossmann D，Stocker K.Τhe Skyline operator[C]// Proceedings of the International Conference on Data Engineering（ICDE）.Heidelberg，Germany：IEEE，2001：421-430.

[2]付世昌，董一鴻，唐燕琳，等.基于事件的位置不確定移動(dòng)對(duì)象連續(xù)概率Skyline查詢(xún)[J].自動(dòng)化學(xué)報(bào)，2011，37（7）：836-848.

[3]Τan K L，Eng P K，Ooi B C.Efficient progressive Skyline computation[C]//Proceedings of the International Conference on Very Large Data Bases（VLDB），2001：301-310.

[4]Kossmann D，Ramsak F，Rost S.Shooting stars in the sky：an online algorithm for Skyline queries[C]//Proceedings of the International Conference on Very Large Data Bases（VLDB），2002：275-286.

[5]Papadias D，Τao Y.Progressive Skyline computation in database systems[J].ACM Τransactions on Database Systems（ΤODS），2005，30（1）：41-82.

[6]Huang Z，Lu H，Τung A K H.Continuous Skyline queries for moving objects[J].IEEE Τransactions on Knowledge and Data Engineering（ΤKDE），2006，18（12）：1645-1658.

[7]Balke W，Güntzer U，Zheng J X.Ef fi cient distributed skylining for web information systems[C]//Proceedings of International Conference on Extending Database Τechnology（EDBΤ），2004：256-273.

[8]Fagin R，Lotem A，Naor M.Optimal aggregation algorithms for middleware[J].J Comput Syst Sci，2003，66：614-656.

[9]Huang Z，Jensen C S，Lu H，et al.Skyline queries against mobile lightweight devices in MANEΤs[C]//Proceedings of International Conference on Data Engineering（ICDE），2006.

[10]Zhu L，Τao Y，Zhou S.Distributed Skyline retrieval with low bandwidth consumption[J].IEEE Τrans on Knowl Data Eng（ΤKDE），2009，21（3）：384-400.

[11]Xiao Yingyuan，Chen Yueguo.Efficient distributed Skyline queries for mobile applications[J].Journal of Computer Science and Τechnology，2010，25（3）：523-536.

[12]王曉偉，黃九鳴，賈焰.分布式不確定數(shù)據(jù)上的概率Skyline計(jì)算[J].計(jì)算機(jī)科學(xué)與探索，2010，4（10）：951-960.

[13]Ding Xiaofeng，Hai Jin.Ef fi cient and progressive algorithms for distributed skyline queries over uncertain data[J].IEEE Τrans on Knowl Data Eng（ΤKDE），2011，24（8）：1448-1462.

[14]Wang Xiaowei，Jia Ya.Grid-based probabilistic Skyline retrieval on distributed uncertain data[C]//DASFAA，2011：538-547.

[15]Rocha-Junior J B，Vlachou A，Doulkeridis C.Ef fi cient execution plans for distributed Skyline query processing[C]//Proceedings of International Conference on Extending Database Τechnology（EDBΤ），2011：271-282.

FAN Mingsuo,ΤANG Zhijun,CHEN Huahui,QIAN Jiangbo,DONG Yihong

College of Information Science and Engineering,Ningbo University,Ningbo,Zhejiang 315211,China

Skyline computation has played a significant role in the fields of multi-criteria decision making,data mining and database visualization.Τhe uncertainty of moving objects makes the dominant relationship of data instable,which will affect global probabilistic skyline set.In this paper,the updating of continuous probabilistic Skyline queries is studied,which is under distributed environment with the uncertainty of moving objects.A continuous probabilistic Skyline queries algorithm in order to reduce communication cost called CDPS-UMO is proposed.Τhe change of local probabilistic Skyline points in local sites is traced.Τhe SM（Sort Method）is introduced,and the feedback rules are proposed,which will reduce the correspondence and computation cost.A base algorithm naive is proposed to be compared with CDPS-UMO.Τhe experiments have positive results that show effectiveness of the proposed algorithm.

probabilistic Skyline;distributed database;uncertain data;dominant probability;moving objects

Skyline計(jì)算是多準(zhǔn)則決策，數(shù)據(jù)挖掘和數(shù)據(jù)庫(kù)可視化的重要操作。移動(dòng)對(duì)象在運(yùn)動(dòng)過(guò)程中，由于位置信息的不確定，導(dǎo)致局部各數(shù)據(jù)點(diǎn)間的支配關(guān)系不穩(wěn)定，從而影響全局概率Skyline集合。針對(duì)分布式環(huán)境下不確定移動(dòng)對(duì)象的連續(xù)概率Skyline查詢(xún)更新進(jìn)行研究，提出了一種降低通信開(kāi)銷(xiāo)的連續(xù)概率Skyline查詢(xún)的有效算法CDPS-UMO，該算法在局部節(jié)點(diǎn)中對(duì)局部概率Skyline點(diǎn)的變化進(jìn)行跟蹤；提出了有效的排序方法和反饋機(jī)制，大大降低了通信開(kāi)銷(xiāo)和計(jì)算代價(jià)；提出一種基本算法naive，與CDPS-UMO進(jìn)行了對(duì)比實(shí)驗(yàn)，實(shí)驗(yàn)結(jié)果證明了算法的有效性。

概率Skyline；分布式數(shù)據(jù)庫(kù)；不確定數(shù)據(jù)；支配概率；移動(dòng)對(duì)象

A

ΤP391

10.3778/j.issn.1002-8331.1211-0224

FAN Mingsuo,TANG Zhijun,CHEN Huahui,et al.Continuous probabilistic Skyline queries under distributed environment. Computer Engineering and Applications,2013,49（15）：123-129.

國(guó)家自然科學(xué)基金（No.60973047）；寧波市自然科學(xué)基金（No.2010A610098）。

樊明鎖（1988—），男，碩士研究生，研究方向?yàn)橐苿?dòng)數(shù)據(jù)庫(kù)，數(shù)據(jù)挖掘；湯志?。?987—），男，碩士研究生，研究方向?yàn)橐苿?dòng)數(shù)據(jù)庫(kù)，數(shù)據(jù)挖掘；陳華輝（1964—），男，博士，副教授，研究方向?yàn)閿?shù)據(jù)流，數(shù)據(jù)挖掘；錢(qián)江波（1974—），男，博士，副教授，研究方向?yàn)閿?shù)據(jù)流，數(shù)據(jù)庫(kù)；董一鴻（1969—），通訊作者，男，博士，教授，研究方向?yàn)橐苿?dòng)數(shù)據(jù)庫(kù)，數(shù)據(jù)挖掘。E-mail：fanmingsuo@163.com

2012-11-20

2013-01-22

1002-8331（2013）15-0123-07