障碍空间中基于R+树的空间Skyline查询方法

来源：计算机科学与探索杂志2017年第12期北京时间：

作者：李松，李爽，张丽平，郝晓红

单位：哈尔滨理工大学 计算机科学与技术学院，哈尔滨 150080

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

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