Continuous dε-Skyline Queries for Objects with Time-Varying Attribute in Road Networks

摘要

The continuous dε-skyline query (or Cdε-SQ for short) is an important type of location-based queries, which can provide useful skyline object information for the user. Given a path Pq, along which the query object q moves, a set of data objects So, and a distance d_epsilon, Cdε-SQ retrieves a set of skyline objects for each point p on Pq, such that the road distance from each skyline object to point p is less than or equal to dε. Previous studies on processing the Cdε-SQ focus exclusively on a static road network, where the object attributes remain unchanged. However, in real-world applications, the object attributes inevitably vary with time, which severely limits the applicability of previous studies in practice. Therefore, in this paper we address the issue of efficiently processing the Cdε-SQ for objects with time-varying attributes. We design two elaborate data structures, the object attribute dominating matrix (OADM) and the road distance sorted list (RDSL), to maintain information of objects and road network. Combined with OADM and RDSL, we develop an efficient algorithm, namely the Cdε-SQ updating algorithm, to provide real-time processing of the time-varying object attributes. Finally, a thorough experimental evaluation is conducted to show the merits of the proposed approaches.