Skyline Computation for Supporting Location-Based Services in a Road Network

Recent advances in mobile communication and positioning technology have made Location-Based Services (LBSs) flourish. LBSs provide the ability to process location-dependent queries for users equipped with global positioning systems. Location-dependent skyline query (LDSQ) is a new type of location-dependent query, which is one very important query for users' decision making. The existing work on LDSQ assumes the Euclidean distance is used. However, in numerous applications such as intelligent traffic, city plan, etc., objects can only move on a pre-defined network, where the distance between two objects means the shortest path distance (network distance). Obviously, the existing LDSQ algorithms based on Euclidean distance cannot return the correct result in road networks. Considering the problem, this paper focuses on how to efficiently answer LDSQs in road networks, and proposes PCNE (a pre-processing combining network expansion algorithm) for processing LDSQs in road networks, which integrates pre-processing strategy and network expansion method. The extensive experiments are done, and the experimental results show that the proposal performs more efficiently than the simple extension of existing methods.