障礙空間中基于R+樹的空間Skyline查詢方法*

李 松，李 爽，張麗平，郝曉紅

哈爾濱理工大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，哈爾濱 150080

障礙空間中基于R+樹的空間Skyline查詢方法*

李 松+，李 爽，張麗平，郝曉紅

哈爾濱理工大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，哈爾濱 150080

為了解決已有研究成果無法有效解決障礙空間中的空間Skyline查詢問題，提出了障礙物環(huán)境下基于R+樹的空間Skyline查詢方法——SOS算法。該算法采用了兩個過程：過濾過程和精煉過程。過濾過程主要是利用R+樹的快速定位特性有效地剪枝掉大量被支配的數(shù)據(jù)點(diǎn)，縮小查詢范圍，提高算法效率。精煉過程主要根據(jù)障礙距離以及數(shù)據(jù)點(diǎn)與查詢點(diǎn)間的拓?fù)潢P(guān)系對候選集中數(shù)據(jù)點(diǎn)進(jìn)行二次篩選，最終得到Skyline集合。進(jìn)一步給出新增點(diǎn)的ADD_SOS算法和刪除點(diǎn)的DEN_SOS算法。理論研究和實(shí)驗(yàn)結(jié)果表明，該算法在處理障礙空間中的空間Skyline查詢問題時具有優(yōu)勢。

R+樹；空間Skyline查詢；障礙空間；障礙距離

1 引言

由于“空間數(shù)據(jù)爆炸但知識貧乏”的現(xiàn)象，利用空間數(shù)據(jù)挖掘和知識發(fā)現(xiàn)（spatial data mining and knowledge discovery，SDMKD）從空間數(shù)據(jù)庫中挖掘事先未知卻潛在有用的空間模式變得十分重要[1]。其中空間數(shù)據(jù)庫中的各種查詢方法為空間數(shù)據(jù)分析和空間知識發(fā)現(xiàn)等提供了有力支持?？臻g數(shù)據(jù)庫查詢包括點(diǎn)查詢、窗口查詢[2]、區(qū)域查詢[3]、最近鄰查詢[4-5]、聚類查詢和空間Skyline查詢[6]等。而在這些查詢中，空間Skyline查詢作為一種用戶偏好查詢，應(yīng)用極其廣泛。

Skyline查詢在市場分析、決策制定、數(shù)據(jù)挖掘、知識發(fā)現(xiàn)、數(shù)據(jù)檢索和計(jì)量經(jīng)濟(jì)學(xué)等方面有著廣泛的應(yīng)用。例如，金融商務(wù)需要搜集大量數(shù)據(jù)，并分析這些數(shù)據(jù)，發(fā)現(xiàn)其模式和特征，同時可能發(fā)現(xiàn)個體、消費(fèi)群體或組織的金融和商業(yè)興趣，并可推測整個市場的變化走勢。此類知識發(fā)現(xiàn)過程正是Skyline查詢應(yīng)用的范圍，以保證最大的利潤和最小的風(fēng)險，對賬戶進(jìn)行分析，進(jìn)行信用評估。近年來，Skyline查詢進(jìn)一步發(fā)展到反Skyline查詢、k支配Skyline查詢[7]、概率Skyline查詢[8]、Top-kSkyline查詢[9]、空間Skyline查詢[10-11]等。

Skyline查詢是查找不被其他數(shù)據(jù)對象支配的數(shù)據(jù)集合，這里的支配可理解為優(yōu)于。傳統(tǒng)的Skyline查詢主要考慮非空間屬性。例如，幾個在城市不同位置的人打算聚餐，那么在選擇飯店時就要考慮飯店的價格、風(fēng)評等，這些因素就是非空間屬性。但是有些情況最重要的考量是空間屬性，而這種情況是傳統(tǒng)的Skyline查詢無法解決的，這時就需要空間Skyline查詢。空間Skyline查詢是空間數(shù)據(jù)庫中重要的查詢之一。

對于空間Skyline查詢，文獻(xiàn)[12]采用Voronoi圖與R樹相結(jié)合的方法處理數(shù)據(jù)。文獻(xiàn)[13]研究基于方向的空間 Skyline（direction-based spatial Skyline，DSS）查詢。文獻(xiàn)[14]提出了計(jì)算一般空間Skyline查詢的方法，利用全最近鄰（all nearest neighbor，ANN）的方法計(jì)算面向?qū)ο蟮牟樵儯迷隽孔罱彛╥ncremental nearest neighbors，INN）的方法計(jì)算面向設(shè)施的查詢。

以上的查詢均是在理想的歐式空間中，但是在現(xiàn)實(shí)生活中不可避免地會有一些地理?xiàng)l件的限制。例如當(dāng)確定兩個城市之前的距離時，若中間有山存在且不能從山內(nèi)部穿過，則不能按兩點(diǎn)間直線來計(jì)算距離，這樣會導(dǎo)致極大的誤差，應(yīng)該確保既繞過這座山又是最短距離，因此兩個對象的最小距離必須考慮障礙物的因素。對于障礙空間中的查詢，文獻(xiàn)[15]提出了一種障礙空間中的最近鄰查詢方法，通過基于線段的最大障礙距離的查詢處理方法和優(yōu)化的匿名區(qū)域查詢處理方法得到實(shí)際的障礙最近鄰。文獻(xiàn)[16]提出了一種障礙空間中基于Voronoi圖的聚類算法。在障礙空間中，現(xiàn)有的空間查詢研究只涉及到范圍查詢、最近鄰查詢和聚類查詢等，并沒有涉及障礙空間的Skyline查詢問題。障礙空間中的空間Skyline查詢問題是一個新的需要解決的問題。

為了解決障礙空間中的空間Skyline查詢問題，基于R+樹，本文提出了SOS查詢方法。該方法可以解決在知識發(fā)現(xiàn)中的實(shí)踐問題，包括在通訊媒體方面解決線路故障，在國防軍事中地理數(shù)據(jù)分析時處理障礙物。SOS查詢方法包括兩個過程：過濾過程和精煉過程。

2 基礎(chǔ)定義與定理

在障礙空間中設(shè)數(shù)據(jù)點(diǎn)集P={p1,p2,…,pn},查詢點(diǎn)q，障礙集O={o1,o2,…,on},i=1,2,…,n。

文獻(xiàn)[17]給出了q到空間對象的距離，文獻(xiàn)[18]給出了點(diǎn)與點(diǎn)的可視性的概念，文獻(xiàn)[19]給出了障礙距離的概念。

定義1[17]（Mindist距離）n維歐式空間E(n)中的點(diǎn)q到同一空間內(nèi)某矩形E的最小距離Mindist，表示為Mindist(E,q)：

定義2（支配）給定數(shù)據(jù)點(diǎn)集P和查詢點(diǎn)q，點(diǎn)p∈P，如果滿足以下條件：對于任意一個p′∈P，存在q，使得dist(p,q)＜dist(p′,q)，則p支配p′，記作p?p′。

基于文獻(xiàn)[10]給出的空間Skyline查詢的定義，本文進(jìn)一步提出障礙空間Skyline查詢的定義，如定義3所示。

定義3（障礙空間Skyline查詢）在障礙空間中，給定一組查詢點(diǎn)集Q={q1,q2,…,qm}和數(shù)據(jù)點(diǎn)集P={p1,p2,…,pn},障礙空間Skyline查詢即返回在障礙空間中在一系列派生的屬性上不被P中其他數(shù)據(jù)點(diǎn)支配的點(diǎn)的集合。

3 障礙空間中基于R+樹的Skyline查詢方法

本文提出的障礙空間中基于R+樹的Skyline查詢方法（SOS算法）主要分為兩部分，即過濾過程和精煉過程。首先通過剪枝并結(jié)合索引結(jié)構(gòu)過濾掉大量受支配的數(shù)據(jù)點(diǎn)，然后通過精煉得到最終的Skyline集合。

3.1 過濾過程

過濾過程主要是充分利用空間索引結(jié)構(gòu)以排除大量不滿足查詢條件的數(shù)據(jù)點(diǎn)來縮小查詢范圍。

定理1設(shè)一最小外包矩形E1，查詢點(diǎn)q，當(dāng)計(jì)算E1與q之間的Mindist(E1,q)時，若E1與q之間有障礙物，且障礙物是另一最小外包矩形E2，則E1被剪枝。

證明若E1與q之間存在E2，則在不考慮障礙物的情況下，計(jì)算Mindist(E1,q)時不考慮E2，在這種情況下計(jì)算Mindist的結(jié)果為Mindist(E1,q)＞Mindist(E2,q)，而當(dāng)考慮障礙物的情況時，計(jì)算Mindist(E1,q)時就要繞過障礙物，使E1與q的距離加大，則有Mindist(E1,q)＞Mindist(E2,q)，故定理得證。 □

引理1[17]已知查詢點(diǎn)q和最小外包矩形E，外包矩形E中空間對象的集合為P={pi,1≤i≤m},則對于任意p∈P,Mindist(E,q)≤||p,q||。

定理2已知查詢點(diǎn)q，最小外包矩形E和E′，外包矩形E中空間對象的集合為P={pi,1≤i≤m}，如果?p∈P，若Mindist(E,qi)≤Mindist(E′,qi)，則被剪枝。

證明空間Skyline問題可描述為 ?p′∈P,p′≠p，對于查詢點(diǎn)q，若D(p,q)≤D(p′,q)，則p?p′。此刻的D為兩點(diǎn)間的歐式距離。根據(jù)引理1可知，對于任意p∈P,Mindist(E,q)≤||p,q||，因此當(dāng)Mindist(E,qi)≤Mindist(E′,qi)，有E?E′。 □

本節(jié)提出的過濾算法的主要思想是：通過定理1、定理2兩個剪枝策略，剪枝掉大量被支配的數(shù)據(jù)點(diǎn)，獲得候選集CandidateSet。這一過程首先根據(jù)給定的數(shù)據(jù)點(diǎn)集P建立R+樹，得到相應(yīng)的MBR（mininum bounding rectangle），然后處理各個MBR。根據(jù)定理1，如果有MBR，其與查詢點(diǎn)之間有障礙物且障礙物是另一個MBR，則此MBR被剪枝。根據(jù)定理2對各個MBR的Mindist(Ei,q)進(jìn)行判斷，剪枝掉被支配的MBR，剩下的未被剪枝的MBR中的數(shù)據(jù)點(diǎn)構(gòu)成更精確的候選集。

基于以上討論給出過濾算法，如算法1所示。

算法1SOS_filter(P,q,O)

該算法首先建立R+樹，獲得相應(yīng)的MBR，然后處理各個MBR。根據(jù)定理1判斷如果存在一個MBR，其與查詢點(diǎn)q之間有障礙物且此障礙物為另一個MBR，則此MBR被剪枝。再根據(jù)定理2判斷各個MBR與q之間的Mindist(Ei,q)，如果有MBR與q之間的Mindist不小于其他MBR與q之間的距離，則滿足此條件的MBR被剪枝。

3.2 精煉過程

精煉過程主要是針對過濾過程得到的候選集進(jìn)行精煉，得到最終的Skyline集合。

定理3以查詢點(diǎn)q為圓心，dist(q,pi)為半徑做圓Circle(q,pi)，若在圓內(nèi)有數(shù)據(jù)點(diǎn)，則pi被剪枝。

證明若以查詢點(diǎn)q為圓心，dist(q,pi)為半徑做圓Circle(q,pi)，在圓內(nèi)有其他數(shù)據(jù)點(diǎn)如pj，而pi在dist(q,pi)上，則可以判斷pj到q的距離小于pi到q的距離，即dist(q,pj)＜dist(q,pi)，則根據(jù)定理2可知pj?pi，故pi被剪枝，定理得證。 □

如圖1所示，根據(jù)過濾過程得到候選集{p7,p8,p9,p13,p14,p15,p16,p17,p18,p22,p23,p24,p25,p26}，根據(jù)定理3，首先判斷p15有沒有支配的數(shù)據(jù)點(diǎn)，分別以q1、q2、q3為圓心，以dist(qi,p15)為半徑做圓，則Circle(qi,p15)內(nèi)部有數(shù)據(jù)點(diǎn)p9、p16、p22、p24，p7、p8、p13、p14、p17、p18、p23、p25、p26在Circle(qi,p15)圓外，從而說明p15支配p7、p8、p13、p14、p17、p18、p23、p25、p26，則p7、p8、p13、p14、p17、p18、p23、p25、p26被剪枝。進(jìn)一步判斷p22是否有支配的數(shù)據(jù)點(diǎn)，分別以q1、q2、q3為圓心，以dist(qi,p22)為半徑做圓，則在剩下的數(shù)據(jù)點(diǎn)中p16和p24在Circle(qi,p22)圓外，其余數(shù)據(jù)點(diǎn)在Circle(qi,p22)內(nèi)部，從而說明p22支配p16和p24，則p16和p24被剪枝。以此類推再判斷p9的支配關(guān)系，沒有得出與它有支配關(guān)系的數(shù)據(jù)點(diǎn)。得到最終的Skyline集合為{p9,p15,p22}。

Fig.1 Example of theorem 3圖1 基于定理3的示例

本節(jié)提出的精煉算法的主要思想是：通過定理3剪枝掉被支配的數(shù)據(jù)點(diǎn)，得到最終的Skyline集合。根據(jù)數(shù)據(jù)點(diǎn)pi與查詢點(diǎn)q之間是否有障礙物分為兩種情況處理。當(dāng)pi與q之間沒有障礙物時，也即pi與q是可視的，則以q為圓心，pi和q之間的歐氏距離為半徑做圓。根據(jù)定理3，若圓內(nèi)有其他數(shù)據(jù)點(diǎn)，則pi被剪枝，若沒有則將pi加入到SkylineSet中。當(dāng)pi與q之間有障礙物時，即pi和q是不可視的，則以q為圓心，pi與q之間的障礙距離為半徑做圓，同樣判斷圓內(nèi)是否有其他數(shù)據(jù)點(diǎn)，若有則pi被剪枝，若沒有則將pi加入SkylineSet中，最終得到Skyline集合。

基于以上討論給出精煉算法，如算法2所示。

算法2 SOS_prune(CandidateSet,q,O)

該算法首先判斷候選集中的數(shù)據(jù)點(diǎn)pi對查詢點(diǎn)q是否是可視的。若可視，則以q為圓心，pi和q的歐氏距離為半徑做支配判定圓；若不可視，則以q為圓心，pi和q的障礙距離為半徑做支配判定圓。圓內(nèi)的數(shù)據(jù)點(diǎn)到q的距離一定小于圓上的數(shù)據(jù)點(diǎn)到q的距離，若圓內(nèi)有其他數(shù)據(jù)點(diǎn)，則此圓上的數(shù)據(jù)點(diǎn)pi一定被支配，故pi被剪枝。

3.3 障礙空間中新增點(diǎn)對Skyline查詢影響

通常，數(shù)據(jù)點(diǎn)集的數(shù)量不是固定不變的，數(shù)據(jù)點(diǎn)集的增加會對原來的查詢結(jié)果產(chǎn)生影響。為了方便查詢處理，本節(jié)給出每次動態(tài)增加一個數(shù)據(jù)點(diǎn)的Skyline查詢處理方法。如果增加多個數(shù)據(jù)點(diǎn)，R+樹要進(jìn)行局部重構(gòu)。

如圖2所示，原數(shù)據(jù)點(diǎn)集P={p1,p2,…,p18},p′為新增點(diǎn)。在增加p′之前，P關(guān)于q的Skyline集合為{p15,p16}。增加數(shù)據(jù)點(diǎn)p′之后，p′與 {p15,p16}進(jìn)行支配檢驗(yàn)，則確定p′與{p15,p16}無支配關(guān)系。故新增數(shù)據(jù)點(diǎn)p′之后，Skyline集合為 {p15,p16,p′}。

Fig.2 Example of dynamically increasing data set圖2 數(shù)據(jù)點(diǎn)集動態(tài)增加的示例

根據(jù)新增數(shù)據(jù)點(diǎn)所在的位置，分兩種情況討論：一種情況是新增數(shù)據(jù)點(diǎn)對SOS查詢結(jié)果沒有影響，另一種是有影響。根據(jù)定理3，以查詢點(diǎn)q為圓心，dist(q,pi)為半徑做圓Circle(q,dist(q,pi))，若在圓內(nèi)有數(shù)據(jù)點(diǎn)，則pi被剪枝。如果只針對一個數(shù)據(jù)點(diǎn)，而查詢點(diǎn)有多個，那么pi的被支配區(qū)域就是幾個Circle(qj,dist(qj,pi))的交集，記為而為與pi無支配關(guān)系區(qū)域，為pi的支配區(qū)域，即在此區(qū)域的數(shù)據(jù)點(diǎn)都被pi支配。當(dāng)p′∈，則p′在pi的被支配區(qū)域，p′支配pi，則pi被剪枝，p′被添加到Skyline集合中。當(dāng)p′∈，則p′與pi無支配關(guān)系，p′被添加到Skyline集合中。當(dāng)p′∈，則p′被pi支配，p′被剪枝，故p′對查詢結(jié)果無影響。則整個Skyline集合的3個區(qū)域分別是：為Skyline集合的被支配區(qū)域；為Skyline集合的無支配關(guān)系區(qū)域；為Skyline集合的支配區(qū)域。

根據(jù)以上兩種情況的討論得出判定規(guī)則1。

判定規(guī)則1給定數(shù)據(jù)點(diǎn)集P={p1,p2,…,pn}和查詢點(diǎn)集Q={q1,q2,…,qm}，設(shè)新增點(diǎn)為p′，若，則p′對SOS查詢結(jié)果無影響；若，則需對SOS查詢結(jié)果集與p′再進(jìn)行支配判斷。

根據(jù)判定規(guī)則1，本節(jié)提出的障礙空間中新增點(diǎn)的SOS算法的主要思想是：首先創(chuàng)建一個新集合P′，此集合由數(shù)據(jù)點(diǎn)集P和新增數(shù)據(jù)點(diǎn)組成。再調(diào)用SOS_filter算法和SOS_prune算法得到P關(guān)于q的Skyline集合SkylineSet。以q為圓心，pi與q的距離為半徑做pi的支配判定圓，根據(jù)判定規(guī)則1，若新增數(shù)據(jù)點(diǎn)在SkylineSet中所有數(shù)據(jù)點(diǎn)的支配判定圓并集的內(nèi)部，則繼續(xù)判斷；若新增數(shù)據(jù)點(diǎn)在某個或多個數(shù)據(jù)點(diǎn)被支配區(qū)域，則對SkylineSet集合做添加新增點(diǎn)并剪枝被支配的數(shù)據(jù)點(diǎn)的操作，否則就直接添加新增點(diǎn)。若新增數(shù)據(jù)點(diǎn)在SkylineSet中所有數(shù)據(jù)點(diǎn)的支配判定圓并集之外，則返回原Skyline集合。

基于以上討論，進(jìn)一步給出算法3。

算法3ADD_SOS(Q,P,O,p′)

該算法首先調(diào)用SOS_filter算法和SOS_prune算法，前面已經(jīng)證明這兩個算法的正確性。然后做SkylineSet中每個pi的支配判定圓，判斷新增數(shù)據(jù)點(diǎn)的位置。若新增點(diǎn)在一個或多個支配判定圓內(nèi)部，則對新增點(diǎn)以及SkylineSet中的數(shù)據(jù)點(diǎn)重新進(jìn)行支配判斷。若新增點(diǎn)不在支配判定圓并集內(nèi)部，則新增數(shù)據(jù)點(diǎn)對Skyline集合無影響，返回原Skyline集合。

3.4 障礙空間中刪除點(diǎn)對Skyline查詢影響

當(dāng)數(shù)據(jù)點(diǎn)減少時同樣會對原來的查詢結(jié)果產(chǎn)生影響。如圖2所示，原數(shù)據(jù)集為P={p1,p2,…,p18,p′},p′為被刪除的數(shù)據(jù)點(diǎn)。在刪除p′之前，數(shù)據(jù)點(diǎn)集的Skyline集合為 {p15,p16,p′}。當(dāng)刪除了數(shù)據(jù)點(diǎn)p′之后，數(shù)據(jù)點(diǎn)集的Skyline集合變成{p15,p16}，由此可見，數(shù)據(jù)集的減少會對查詢結(jié)果造成影響。

根據(jù)刪除的數(shù)據(jù)點(diǎn)所在的位置，分兩種情況討論：一種情況是刪除點(diǎn)對SOS查詢結(jié)果有影響；另一種是沒有影響。設(shè)刪除的數(shù)據(jù)點(diǎn)為p′，當(dāng)p′∈時，因?yàn)樵诰珶掃^程中根據(jù)定理3會對支配判定圓區(qū)域以外的數(shù)據(jù)點(diǎn)進(jìn)行剪枝，此時p′會一同被剪枝，所以p′對SOS查詢結(jié)果無影響。當(dāng)p′∈SkylineSet時，p′被刪除，有些之前只被p′支配的數(shù)據(jù)點(diǎn)則有可能成為Skyline點(diǎn)，這時需要重新調(diào)用過濾算法和精煉算法計(jì)算新數(shù)據(jù)點(diǎn)集的Skyline集合。故此時刪除p′對查詢結(jié)果有影響。

基于以上討論進(jìn)一步給出判定規(guī)則2和判定規(guī)則3。

判定規(guī)則2設(shè)減少的數(shù)據(jù)點(diǎn)為p′，若，則對SOS查詢沒有影響；若p′∈SkylineSet，則需將數(shù)據(jù)點(diǎn)集更新為P-p′后再進(jìn)行查詢。

判定規(guī)則3數(shù)據(jù)點(diǎn)集減少情況下SOS查詢結(jié)果一定是原數(shù)據(jù)集的SOS查詢結(jié)果集的子集。

根據(jù)判定規(guī)則2和判定規(guī)則3，本節(jié)提出的障礙空間中刪除點(diǎn)的SOS算法的主要思想為：建立一個新集合P′，由數(shù)據(jù)點(diǎn)集P去掉刪除點(diǎn)得到的集合。首先調(diào)用SOS_filter算法和SOS_prune算法得到原數(shù)據(jù)點(diǎn)集P關(guān)于Q的Skyline集合SkylineSet。根據(jù)判定規(guī)則2，刪除點(diǎn)所在的位置分兩種情況：若刪除點(diǎn)在Skyline集合SkylineSet中，那么重新調(diào)用SOS_filter算法和SOS_prune算法計(jì)算新數(shù)據(jù)點(diǎn)集P′關(guān)于Q的Skyline集合NewSkylineSet，并返回；另一種情況是刪除點(diǎn)不在Skyline集合SkylineSet中，則返回原Skyline集合SkylineSet。

基于以上討論，進(jìn)一步給出算法4。

算法4DEN_SOS(Q,P,O,p′)

該算法首先調(diào)用SOS_filter算法和SOS_prune算法。然后判斷刪除點(diǎn)的位置。若刪除點(diǎn)不在SkylineSet集合中，直接返回SkylineSet。若刪除點(diǎn)在SkylineSet集合中，需重新計(jì)算數(shù)據(jù)集P′關(guān)于Q的Skyline集合NewSkylineSet，并返回NewSkylineSet。

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

下面通過實(shí)驗(yàn)對本文算法進(jìn)行性能評估，驗(yàn)證算法的性能效率。首先從數(shù)據(jù)集大小及障礙物個數(shù)方面對算法性能進(jìn)行分析，然后從不同數(shù)據(jù)分布上對算法進(jìn)行驗(yàn)證：正相關(guān)、獨(dú)立分布。由于已有的研究成果無法直接處理障礙空間中空間Skyline查詢問題，本文首先對文獻(xiàn)[10]提出的B2S2（branch-and-bound spatial skyline）算法采取增加障礙物的方式形成對比算法，本文將這種增加障礙物的B2S2算法稱作OB2S2算法；然后對文獻(xiàn)[11]提出的LBC（lower bound constraint）算法也采取增加障礙物的方式形成對比算法，本文將這種增加障礙物的LBC算法稱作OLBC算法。

實(shí)驗(yàn)平臺配置：Pentium 4核，2.216 GHz CPU，8 GB內(nèi)存。本文使用的數(shù)據(jù)集是來自美國加利福尼亞州空間信息的真實(shí)數(shù)據(jù)，并對數(shù)據(jù)集進(jìn)行了適當(dāng)?shù)恼{(diào)整（http://konect.uni-koblenz.de/networks/roadNet-CA）。

實(shí)驗(yàn)通過在不同數(shù)據(jù)分布情況下對比數(shù)據(jù)集大小及障礙物個數(shù)對響應(yīng)時間的影響來比較SOS算法和OB2S2算法以及OLBC算法的性能。實(shí)驗(yàn)證明，在障礙空間中，本文提出的SOS算法比OB2S2以及OLBC算法在響應(yīng)時間上處理具有不同障礙物個數(shù)及不同數(shù)據(jù)集大小時效果更優(yōu)。

如圖3所示，首先分析數(shù)據(jù)集大小對執(zhí)行時間的影響，實(shí)驗(yàn)采用真實(shí)數(shù)據(jù)集，障礙物的數(shù)量為30 000。圖3給出了3個算法的執(zhí)行時間隨著數(shù)據(jù)集大小變化的對比結(jié)果。從圖3中可以看出，無論是正相關(guān)還是獨(dú)立分布，SOS算法、OB2S2算法以及OLBC算法的執(zhí)行時間都是隨著數(shù)據(jù)集的不斷變大而呈上升趨勢。圖3中（a）、（b）相比，獨(dú)立分布時3個算法執(zhí)行時間的差距較大。主要原因是SOS算法以R+樹作為索引結(jié)構(gòu)，相比較OB2S2算法用R樹以及OLBC算法使用B+樹的效率都更高，減少了查詢覆蓋率。而OB2S2算法和OLBC算法分別是將B2S2算法和LBC算法放在障礙空間中，在處理障礙物時都要浪費(fèi)時間。因此障礙空間中SOS算法在解決Skyline問題的執(zhí)行時間要小于OB2S2算法和OLBC算法。

Fig.3 Effects of data set size on execution time圖3 數(shù)據(jù)集大小對執(zhí)行時間的影響

Fig.4 Effects of obstacle number on execution time圖4 障礙物個數(shù)對執(zhí)行時間的影響

Fig.5 Effects of data set size on I/O times圖5 數(shù)據(jù)集大小對I/O次數(shù)的影響

圖4給出了在正相關(guān)、獨(dú)立分布的數(shù)據(jù)分布情況下障礙物個數(shù)對執(zhí)行時間的影響，數(shù)據(jù)集規(guī)模為900 000。圖4給出了3個算法在不同數(shù)據(jù)分布情況下執(zhí)行時間隨障礙物個數(shù)變化的對比結(jié)果。從圖4中可以看出，3個算法在不同數(shù)據(jù)分布情況下都隨著障礙物個數(shù)的增大，算法的執(zhí)行時間也不斷升高。隨著障礙物個數(shù)的增加，相較于SOS算法，OB2S2算法和OLBC算法的增長率越來越大，而且3個算法執(zhí)行時間差也越來越大。主要原因?yàn)镾OS算法是根據(jù)障礙空間及障礙物與數(shù)據(jù)點(diǎn)查詢點(diǎn)間特點(diǎn)提出相應(yīng)有效的剪枝方法，故在障礙空間中求解Skyline集合的效率較高。

圖5給出了在正相關(guān)、獨(dú)立分布的情況下數(shù)據(jù)集大小對I/O次數(shù)的影響，障礙物數(shù)量為30 000。從圖5中可以看出，3個算法在不同數(shù)據(jù)分布情況下隨著數(shù)據(jù)集的不斷增大，算法的I/O次數(shù)呈上升趨勢。并且相比于兩種數(shù)據(jù)分布情況，獨(dú)立分布時3個算法之間的差距會隨著數(shù)據(jù)不斷增大而增大，正相關(guān)時差距不變。一個算法的I/O次數(shù)與支配比較次數(shù)有關(guān)，也就與時間復(fù)雜度有關(guān)，在障礙空間中SOS算法效率更高，且時間復(fù)雜度比OB2S2算法以及OLBC算法更低，故SOS算法在效率上優(yōu)于OB2S2算法和OLBC算法。

5 結(jié)束語

本文基于R+樹的性質(zhì)以及障礙空間的特點(diǎn)提出了障礙空間中的空間Skyline查詢方法，給出了障礙空間Skyline查詢的定義以及SOS算法。解決該問題難點(diǎn)在于如何計(jì)算兩數(shù)據(jù)點(diǎn)間以及兩個MBR間的障礙距離，為此在障礙物環(huán)境下提出了有效的剪枝策略。在過濾過程中利用剪枝策略對數(shù)據(jù)集進(jìn)行剪枝，過濾掉大量的被支配的MBR，快速地縮小查詢范圍，得到初步的候選集。精煉過程對候選集進(jìn)行精煉處理得到最終的Skyline集合。在SOS算法的基礎(chǔ)上進(jìn)一步給出數(shù)據(jù)點(diǎn)增加情況下的ADD_SOS算法，數(shù)據(jù)點(diǎn)減少情況下的DEN_SOS算法。未來的研究重點(diǎn)集中在動態(tài)不確定數(shù)據(jù)信息的空間Skyline查詢方面。

[1]Li Deren,Wang Shuliang,Li Deyi,et al.Theories and technologies of spatial data mining and knowledge discovery[J].Geomatics and Information Science of Wuhan University,2002,27(3):221-233.

[2]Jin Guang,Nittel S.Towards spatial window queries over continuous phenomena in sensor networks[J].IEEE Transactions on Parallel&Distributed Systems,2008,19(4):559-571.

[3]Ni Jinfeng,Ravishankar C V.Pointwise-dense region queries in spatio-temporal databases[C]//Proceedings of the 23rd International Conference on Data Engineering,Istanbul,Turkey,Apr 15-20,2007.Washington:IEEE Computer Society,2007:1066-1075.

[4]Zhang Liping,Liu Lei,Li Song,et al.Group reverseknearest neighbor query based on Voronoi diagram in spatial databases[J].Journal of Frontiers of Computer Science and Technology,2016,10(10):1365-1375.

[5]Li Song,Zhang Liping,Hao Zhongxiao.Strong neighborhood pair query in dynamic dataset[J].Journal of Computer Research and Development,2015,52(3):749-759.

[6]Vlachou A,Doulkeridis C,Polyzotis N.Skyline query processing over joins[C]//Proceedings of the 2011 ACM SIGMOD International Conference on Management of Data,Athens,Greece,Jun 12-16,2011.New York:ACM,2011:73-84.

[7]Miao Xiaoye,Gao Yunjun,Chen Gang,et al.K-dominant skyline queries on incomplete data[J].Information Sciences,2016,367:990-1011.

[8]Park Y,Min J K,Shim K.Processing of probabilistic skyline queries using MapReduce[J].Proceedings of VLDB Endowment,2015,8(12):1406-1417.

[9]Yang Linqing,Li Zhan,Mou Yanchao,et al.Algorithm of paralleltop-kskyline queries for large data set[J].Journal of Frontiers of Computer Science and Technology,2015,9(8):897-905.

[10]Sharifzadeh M,Shahabi C.The spatial skyline queries[C]//Proceedings of the 32nd International Conference on Very Large Data Bases,Seoul,Korea,Sep 12-15,2006.New York:ACM,2006:751-762.

[11]Deng Ke,Zhou Xiaofang,Tao Heng.Multi-source skyline query processing in road networks[C]//Proceedings of the 29th International Conference on Data Engineering,Istanbul,Turkey,Apr 15-20,2007.Washington:IEEE Computer Society,2007:796-805.

[12]Ma Geng,Arefin M S,Morimoto Y.A spatial skyline query for a group of users having different positions[C]//Proceedings of the 3rd International Conference on Networking&Computing,Okinawa,Japan,Dec 5-7,2012.Washington:IEEE Computer Society,2013:137-142.

[13]Guo Xi,Ishikawa Y,Gao Yunjun.Direction-based spatial skylines[C]//Proceedings of the 9th International Workshop on Data Engineering for Wireless&Mobile Access,Indianapolis,USA,Jun 6,2010.New York:ACM,2010:73-80.

[14]Lin Qianlu,Zhang Ying,Zhang Wenjie,et al.General spatial skyline operator[C]//LNCS 7238:Proceedings of the 17th International Conference on Database Systems for Advanced Applications,Busan,Korea,Apr 15-18,2012.Berlin,Heidelberg:Springer,2012:494-508.

[15]Zhu Huaijie,Wang Jiaying,Wang Bin,et al.Location privacy preserving obstructed nearest neighbor queries[J].Journal of Computer Research and Development,2014,51(1):115-125.

[16]Li Yuhan,Sun Dongpu.A clustering algorithm of uncertain data with obstacles based on Voronoi diagram[J].Computer Engineering and Science,2016,38(5):1031-1038.

[17]Hao Zhongxiao.Query and reasoning in spatio-temporal database[M].Beijing:Science Press,2010.

[18]Sack J R,Urrutia J.Handbook of computational geometry[M].Amsterdam:Elsevier Science Publishers B V,2000:829-876.

[19]Yu Xiaonan,Gu Yu,Zhang Tianping,et al.A method for reversek-nearest-neighborqueries in obstructed spaces[J].Chinese Journal of Computers,2011,34(10):1917-1925.

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

[1]李德仁,王樹良,李德毅,等.論空間數(shù)據(jù)挖掘和知識發(fā)現(xiàn)的理論與方法[J].武漢大學(xué)學(xué)報:信息科學(xué)版,2002,27(3):221-233.

[4]張麗平,劉蕾,李松,等.空間數(shù)據(jù)庫中基于Voronoi圖的組反k最近鄰查詢[J].計(jì)算機(jī)科學(xué)與探索,2016,10(10):1365-1375.

[5]李松,張麗平,郝忠孝.動態(tài)數(shù)據(jù)集下的強(qiáng)鄰近對查詢[J].計(jì)算機(jī)研究與發(fā)展,2015,52(3):749-759.

[9]楊林青,李湛,牟雁超,等.面向大規(guī)模數(shù)據(jù)集的并行化Top-kSkyline查詢算法[J].計(jì)算機(jī)科學(xué)與探索,2015,9(8):897-905.

[15]朱懷杰,王佳英,王斌,等.障礙空間中保持位置隱私的最近鄰查詢方法[J].計(jì)算機(jī)研究與發(fā)展,2014,51(1):115-125.

[16]李宇涵,孫冬璞.基于Voronoi圖的障礙不確定數(shù)據(jù)的聚類算法[J].計(jì)算機(jī)工程與科學(xué),2016,38(5):1031-1038.

[17]郝忠孝.時空數(shù)據(jù)庫查詢與推理[M].北京:科學(xué)出版社,2010.

[19]于嘵楠,谷峪,張?zhí)炱?等.一種障礙空間中的反k最近鄰查詢方法[J].計(jì)算機(jī)學(xué)報,2011,34(10):1917-1925.

Spatial Skyline Query Method Based on R+-Tree for Obstructed Spaces*

LI Song+,LI Shuang,ZHANG Liping,HAO Xiaohong

College of Computer Science and Technology,Harbin University of Science and Technology,Harbin 150080,China

2017-07,Accepted 2017-09.

In order to solve the problem that the existing methods can not deal with the spatial Skyline query in obstructed space,this paper proposes the spatial Skyline query method in obstructed space based on R+-tree(SOS algorithm).This algorithm adopts two processes:filtering and refinement.Filtering process mainly uses R+-tree quickly locating features to effectively prune away a large number of data points which are dominated,narrowing the scope of query,and improving the efficiency of algorithm.Refinement process mainly screens objects within the candidate set according to the obstacle distance and the topological relationship between data points and query point.Finally the Skyline set can be got.Further,ADD_SOS algorithm for newly added points and DEN_SOS algorithm for deleted points are given.Theoretical study and experiments show that the algorithm has advantages in dealing with the spatial Skyline query problem in obstructed spaces.

R+-tree;spatial Skyline query;obstructed spaces;obstacle distance

+Corresponding author:E-mail:lisongbeifen@163.com

10.3778/j.issn.1673-9418.1707008

*The Science and Technology Research Project of Heilongjiang Provincial Education Department under Grant No.12531z004(黑龍江省教育廳科學(xué)技術(shù)研究項(xiàng)目).

CNKI網(wǎng)絡(luò)優(yōu)先出版:2017-09-12,http://kns.cnki.net/kcms/detail/11.5602.TP.20170912.1514.002.html

LI Song,LI Shuang,ZHANG Liping,et al.Spatial Skyline query method based on R+-tree for obstructed spaces.Journal of Frontiers of Computer Science and Technology,2017,11(12)：1886-1896.

A

TP311

LI Song was born in 1977.He received the Ph.D.degree from Harbin University of Science and Technology.Now he is an associate professor at Harbin University of Science and Technology,and the member of CCF.His research interests include database theory and application,data mining and data query.

李松（1977—），男，江蘇沛縣人，博士，哈爾濱理工大學(xué)副教授、研究生導(dǎo)師，CCF會員，主要研究領(lǐng)域?yàn)閿?shù)據(jù)庫理論及應(yīng)用，數(shù)據(jù)挖掘，數(shù)據(jù)查詢。

LI Shuang was born in 1991.She is an M.S.candidate at Harbin University of Science and Technology.Her research interests include data mining and data query.

李爽（1991—），女，黑龍江哈爾濱人，哈爾濱理工大學(xué)碩士研究生，主要研究領(lǐng)域?yàn)閿?shù)據(jù)挖掘，數(shù)據(jù)查詢。

ZHANG Liping was born in 1976.She received the M.S.degree from Harbin University of Science and Technology.Now she is an associate professor at Harbin University of Science and Technology,and the member of CCF.Her research interests include database theory and application,data mining and data query.

張麗平（1976—），女，遼寧鐵嶺人，碩士，哈爾濱理工大學(xué)副教授、研究生導(dǎo)師，CCF會員，主要研究領(lǐng)域?yàn)閿?shù)據(jù)庫理論及應(yīng)用，數(shù)據(jù)挖掘，數(shù)據(jù)查詢。

HAO Xiaohong was born in 1969.She received the M.S.degree from Harbin University of Science and Technology.Now she is a senior experimentalist at Harbin University of Science and Technology.Her research interests include database theory and application,data mining and data query.

郝曉紅（1969—），女，黑龍江哈爾濱人，碩士，哈爾濱理工大學(xué)高級實(shí)驗(yàn)師，主要研究領(lǐng)域?yàn)閿?shù)據(jù)庫理論及應(yīng)用，數(shù)據(jù)挖掘，數(shù)據(jù)查詢。