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

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

哈爾濱理工大學 計算機科學與技術學院，哈爾濱 150080

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

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

哈爾濱理工大學 計算機科學與技術學院，哈爾濱 150080

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

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

1 引言

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

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

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

對于空間Skyline查詢，文獻[12]采用Voronoi圖與R樹相結合的方法處理數據。文獻[13]研究基于方向的空間 Skyline（direction-based spatial Skyline，DSS）查詢。文獻[14]提出了計算一般空間Skyline查詢的方法，利用全最近鄰（all nearest neighbor，ANN）的方法計算面向對象的查詢，利用增量最近鄰（incremental nearest neighbors，INN）的方法計算面向設施的查詢。

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

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

2 基礎定義與定理

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

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

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

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

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

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

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

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

3.1 過濾過程

過濾過程主要是充分利用空間索引結構以排除大量不滿足查詢條件的數據點來縮小查詢范圍。

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

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

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

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

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

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

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

算法1SOS_filter(P,q,O)

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

3.2 精煉過程

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

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

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

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

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

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

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

算法2 SOS_prune(CandidateSet,q,O)

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

3.3 障礙空間中新增點對Skyline查詢影響

通常，數據點集的數量不是固定不變的，數據點集的增加會對原來的查詢結果產生影響。為了方便查詢處理，本節給出每次動態增加一個數據點的Skyline查詢處理方法。如果增加多個數據點，R+樹要進行局部重構。

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

Fig.2 Example of dynamically increasing data set圖2 數據點集動態增加的示例

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

根據以上兩種情況的討論得出判定規則1。

判定規則1給定數據點集P={p1,p2,…,pn}和查詢點集Q={q1,q2,…,qm}，設新增點為p′，若，則p′對SOS查詢結果無影響；若，則需對SOS查詢結果集與p′再進行支配判斷。

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

基于以上討論，進一步給出算法3。

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

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

3.4 障礙空間中刪除點對Skyline查詢影響

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

根據刪除的數據點所在的位置，分兩種情況討論：一種情況是刪除點對SOS查詢結果有影響；另一種是沒有影響。設刪除的數據點為p′，當p′∈時，因為在精煉過程中根據定理3會對支配判定圓區域以外的數據點進行剪枝，此時p′會一同被剪枝，所以p′對SOS查詢結果無影響。當p′∈SkylineSet時，p′被刪除，有些之前只被p′支配的數據點則有可能成為Skyline點，這時需要重新調用過濾算法和精煉算法計算新數據點集的Skyline集合。故此時刪除p′對查詢結果有影響。

基于以上討論進一步給出判定規則2和判定規則3。

判定規則2設減少的數據點為p′，若，則對SOS查詢沒有影響；若p′∈SkylineSet，則需將數據點集更新為P-p′后再進行查詢。

判定規則3數據點集減少情況下SOS查詢結果一定是原數據集的SOS查詢結果集的子集。

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

基于以上討論，進一步給出算法4。

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

該算法首先調用SOS_filter算法和SOS_prune算法。然后判斷刪除點的位置。若刪除點不在SkylineSet集合中，直接返回SkylineSet。若刪除點在SkylineSet集合中，需重新計算數據集P′關于Q的Skyline集合NewSkylineSet，并返回NewSkylineSet。

4 實驗比較與分析

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

實驗平臺配置：Pentium 4核，2.216 GHz CPU，8 GB內存。本文使用的數據集是來自美國加利福尼亞州空間信息的真實數據，并對數據集進行了適當的調整（http://konect.uni-koblenz.de/networks/roadNet-CA）。

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

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

Fig.3 Effects of data set size on execution time圖3 數據集大小對執行時間的影響

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

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

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

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

5 結束語

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

附中文參考文獻：

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

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

[5]李松,張麗平,郝忠孝.動態數據集下的強鄰近對查詢[J].計算機研究與發展,2015,52(3):749-759.

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

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

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

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

[19]于嘵楠,谷峪,張天平,等.一種障礙空間中的反k最近鄰查詢方法[J].計算機學報,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(黑龍江省教育廳科學技術研究項目).

CNKI網絡優先出版: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—），男，江蘇沛縣人，博士，哈爾濱理工大學副教授、研究生導師，CCF會員，主要研究領域為數據庫理論及應用，數據挖掘，數據查詢。

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—），女，黑龍江哈爾濱人，哈爾濱理工大學碩士研究生，主要研究領域為數據挖掘，數據查詢。

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—），女，遼寧鐵嶺人，碩士，哈爾濱理工大學副教授、研究生導師，CCF會員，主要研究領域為數據庫理論及應用，數據挖掘，數據查詢。

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—），女，黑龍江哈爾濱人，碩士，哈爾濱理工大學高級實驗師，主要研究領域為數據庫理論及應用，數據挖掘，數據查詢。