Journal of Frontiers of Computer Science and Technology ›› 2018, Vol. 12 ›› Issue (12): 1882-1890.DOI: 10.3778/j.issn.1673-9418.1805021

Previous Articles     Next Articles

Method of Spatial Skyline Query in Obstacle Environment

LI Song, DOU Yanan, ZHANG Liping, HAO Xiaohong   

  1. College of Computer Science and Technology, Harbin University of Science and Technology, Harbin 150080, China
  • Online:2018-12-01 Published:2018-12-07



  1. 哈尔滨理工大学 计算机科学与技术学院,哈尔滨 150080


In order to make up for the shortcomings of the existing research results in dealing with the space Skyline query problem in the obstacle environment, this paper proposes a spatial Skyline query method based on Voronoi diagram in the obstacle environment. This method can be used to solve multi-objective decision problems in practical applications. According to the change of the query point set, the spatial Skyline queries in obstacle space (OSSQ query) method is proposed in two cases. One method is a static query points of Skyline query in obstacle space (STA_OSSQ query) method. This query method mainly includes two processes: a cut data set and a dominance check, and finally a Skyline set is obtained. The other is the dynamic query points of Skyline query in obstacle space (DYN_OSSQ query) method in the dynamic query point state. The method mainly deals with the space Skyline in the obstacle environment when the query point is dynamically increased and decreased. Finally, it is shown that the proposed method has higher efficiency through theoretical research and experiments.

Key words: spatial Skyline query, multi-objective decision-making, Voronoi diagram, obstacle space


为了弥补现有的研究成果对处理障碍环境下空间Skyline查询问题的不足,提出了在障碍环境下基于Voronoi图的空间Skyline查询方法。该方法在实际应用中可以用来解决多目标决策问题。依据查询点集合是否发生变化提出了两种情况下的障碍环境中空间Skyline查询(spatial Skyline queries in obstacle space,OSSQ)方法:一种是静态查询点的障碍环境中空间Skyline查询(static query points of Skyline query in obstacle space,STA_OSSQ)方法,该查询方法主要包括约剪数据集和支配检查两个过程,最后得到Skyline集合;另一种是动态查询点状态下的障碍环境中Skyline查询(dynamic query points of Skyline query in obstacle space,DYN_OSSQ)方法,该方法主要处理了查询点动态增加和减少情况下障碍环境中空间Skyline查询问题。理论研究和实验表明所提出的方法具有较高的效率。

关键词: 空间Skyline查询, 多目标决策, Voronoi图, 障碍空间