On Efficiently Answering Why-Not Range-Based Skyline Queries in Road Networks

摘要

The range-based skyline (r-skyline) query on road networks retrieves the skyline objects for each of the query points that are within a road region, considering the objects' spatial and non-spatial attributes. However, reasoning about missing query results, specified by why-not questions, has not till recently received the attention it is worth of. In this paper, we systematically carry out the study of why-not questions on the r-skyline query in the road network environment (abbrev. as the why-not RSQ problem). We present three modification strategies, including modifying the query range, modifying the why-not point, and modifying both of them, for supporting the why-not RSQ problem. We also propose three efficient algorithms to tackle the why-not RSQ problem, where several newly presented effective concepts/techniques are leveraged, such as the concepts of skyline scope and skyline dominance region, non-spatial attribute modification pruning, and G-tree index. Extensive experimental evaluation using both real and synthetic data sets demonstrates the performance of our proposed algorithms.