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

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