Dynamic Skyline Maintaining Strategies for Moving Query Points in Road Networks

Abstract

Skyline query processing in Location-based Services has been investigated extensively in recent years. In this paper, we address the issue of efficient evaluation of Continuous Range Skyline Queries (CRSQ) in road networks where the query points are moving and the interest points are within a certain range. We develop efficient skyline maintaining strategies to answer continuous range skyline queries. First, we propose a novel method named Dynamic Split Points Setting (DSPS) dividing a given path in road networks into several segments. Second, for each segment, we adopt the Progressive Incremental Network Expansion (PINE) technique based on Network Voronoi Diagrams (NVD) to calculate candidates of skyline interest points. After that, when the query point moves, the spilt points are dynamically set by DSPS strategies to ensure that when the query point moves within a segment, skyline points remain unchanged and only need to be updated while moving across the split points. Finally, extensive experiments show that our DSPS strategies are efficient compared with previous approaches.