基于位置范围的道路网skyline查询

Location Range-based Skyline Query in Road Networks

随着无线通信和定位技术的发展,道路网skyline查询在基于位置的服务等方面越来越重要。考虑到现今道路网中位置隐私保护和定位设备的精度问题,用户在道路网上的位置通常用一个范围来表示。但是,已有的道路网skyline研究都是基于单一查询点。针对这一问题,研究了一种新的查询——基于位置范围的道路网skyline查询(RNS),提出了一种基于边界点替换的有效查询处理算法。另外,针对已有的道路网skyline查询中复杂的道路网距离计算对查询效率的影响问题,通过计算兴趣点在道路网上的有效skyline路段,将其与道路网信息融合,建立了道路网skyline模型。基于该模型设计了一种能有效支持RNS查询的道路网skyline索引SSR-tree,提出了基于索引的RNS查询处理算法。通过大量实验验证了所提方法的有效性,并比较了基于索引的算法在查询效率和精度上的提高。

With the development of wireless communication and positioning technology, skyline query in road networks has recently been important in LBS. For the consideration of human privacy and the limited accuracy of positioning devices, user＇s location is always represented as a spatial range. However, the existing researches focus on the point-based skyline query. This paper studied a new problem of the location ranges-based skyline query in road networks（RNS）, and proposed an efficient query processing algorithm. In addition, because the complex distance calculation brings decrease of the query efficiency, this paper also proposed an index-based query algorithm, and then by pre-computing effective skyline road segments of POI and creating a new road network model, designed an index to support the RNS efficiently. Extensive experiments on real networks datasets verify the performance and accuracy of the proposed algorithms.