Abstract: 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.

Key words:  R+-tree, spatial Skyline query, obstructed spaces, obstacle distance

摘要： 为了解决已有研究成果无法有效解决障碍空间中的空间Skyline查询问题，提出了障碍物环境下基于R+树的空间Skyline查询方法——SOS算法。该算法采用了两个过程：过滤过程和精炼过程。过滤过程主要是利用R+树的快速定位特性有效地剪枝掉大量被支配的数据点，缩小查询范围，提高算法效率。精炼过程主要根据障碍距离以及数据点与查询点间的拓扑关系对候选集中数据点进行二次筛选，最终得到Skyline集合。进一步给出新增点的ADD_SOS算法和删除点的DEN_SOS算法。理论研究和实验结果表明，该算法在处理障碍空间中的空间Skyline查询问题时具有优势。

关键词: R+树, 空间Skyline查询, 障碍空间, 障碍距离