障碍空间中基于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—），女，黑龙江哈尔滨人，硕士，哈尔滨理工大学高级实验师，主要研究领域为数据库理论及应用，数据挖掘，数据查询。