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

樊明鎖，湯志俊，陳華輝，錢江波，董一鴻

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

樊明鎖，湯志俊，陳華輝，錢江波，董一鴻

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

1 引言

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

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

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

圖1 分布式環(huán)境下不確定移動對象的概率Skyline點

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

2 預(yù)備知識

2.1 問題描述

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

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

定義3（局部概率Skyline集合）t時刻局部子節(jié)點DBi中所有不被任何其他點支配的點的集合稱為t時刻的局部概率Skyline集合，記為Lip-Sky(t)。

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

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

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

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

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

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

圖2 Skyline概率實例

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

2.3 基本算法（naive）

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

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

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

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

3.1 排序方法

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

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

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

3.2 反饋機(jī)制

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

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

3.3 算法實現(xiàn)

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

3.3.1 Initial_LiP Skyline算法

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

3.3.2 StaticSkyline算法

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

3.3.3 Feedback算法

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

算法4 Feedback

3.3.4 CDPS-UMO基本框架

CDPS-UMO算法的基本思想是提前計算不確定移動對象移動過程中，可能引起局部概率Skyline集合變動的events，通過對這些event的跟蹤計算從而不斷更新局部概率Skyline集合，與此之后采用有效的反饋策略不斷地快速更新全局概率Skyline集合。基本框架描述如下：

3.3.5 算法性能分析

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

4 實驗分析

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

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

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

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

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

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

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

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

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

4.3 分布節(jié)點m對算法影響

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

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

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

圖7 分布節(jié)點在圓形-均勻分布模型中對通信開銷的影響

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

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

圖9 分布節(jié)點在不同模型中對通信開銷的影響

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

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

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

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

5 相關(guān)工作

圖12 運(yùn)動速度在圓形-均勻分布模型中對通信開銷的影響

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

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

6 總結(jié)與展望

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

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

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

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.

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

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

2012-11-20

2013-01-22

1002-8331（2013）15-0123-07