摘要
为了解决已有研究成果无法有效解决障碍空间中的空间Skyline查询问题,提出了障碍物环境下基于R+树的空间Skyline查询方法——SOS算法。该算法采用了两个过程:过滤过程和精炼过程。过滤过程主要是利用R+树的快速定位特性有效地剪枝掉大量被支配的数据点,缩小查询范围,提高算法效率。精炼过程主要根据障碍距离以及数据点与查询点间的拓扑关系对候选集中数据点进行二次筛选,最终得到Skyline集合。进一步给出新增点的ADD_SOS算法和删除点的DEN_SOS算法。理论研究和实验结果表明,该算法在处理障碍空间中的空间Skyline查询问题时具有优势。
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.
出处
《计算机科学与探索》
CSCD
北大核心
2017年第12期1886-1896,共11页
Journal of Frontiers of Computer Science and Technology
基金
黑龙江省教育厅科学技术研究项目No.12531z004~~