一种基于路网的多源聚合距离Skyline查询算法

Multi-source aggregate distance Skyline query algorithm based on road network

基于路网距离的多源Skyline查询在地图服务中广泛使用,但现有的Skyline查询方法对于复杂的路网距离计算效率低下,并且随着查询点数量的增加查询结果集变得过于庞大,无法为用户提供精简有效的查询结果。为了提高查询结果的有效性和查询效率,提出一种基于最小聚合距离的倒排索引Skyline查询算法,该算法对道路网建立QG-tree索引,提高聚合距离的计算效率;同时对兴趣点集建立倒排索引,结合剪枝策略对兴趣点进行检索,减少聚合距离计算和支配判定的开销,有效地提高查询效率。在真实道路网上的实验表明,所提出的算法效率比现有算法DSR和N3S快1~3个数量级,可以有效地处理道路网环境下多源Skyline查询问题。

Multi-source Skyline query based on road network distance is widely used in map services.However,the existing Skyline query methods are inefficient for complex road network distance calculation,and with the increasing of the number of the query point,the query result set becomes too large to provide users with tidy and effective query results.In order to improve the validity of the query results and the query efficiency,this paper proposed an inverted index Skyline query algorithm based on the minimum aggregation distance,which established QG-tree index for road network to improve the calculation efficiency of aggregation distance.And it established an inverted index for the points of interest set to retrieve the points of interest combined with pruning strategy,which reduced the overhead of aggregation distance calculation and the domination determination,and effectively improved the query efficiency.Finally,experiments on the real road network show that the efficiency of the proposed algorithm is 1~3 orders of magnitude faster than that of the existing algorithms DSR and N3S,and it can effectively handle the multi-source Skyline query problem in the road network.