Candidate Pruning Technique for Skyline Computation Over Frequent Update Streams

摘要

Skyline query processing reveals a set of preferable results based on the competitiveness of many criteria among all data objects. This is a very useful query for multi-attribute decision making. Moreover, monitoring and tracing skyline over time-series data axe also important not only for real-time applications (e.g., environmental monitoring) but also historical time-series analysis (e.g., sports archives, historical stock data). In these applications, considering consecutive snapshots, a large fraction of the fixed number of observing objects (e.g., weather stations) can change their values resulting to the possibility of complete change in the previous skyline. Without any technique, computing skyline from a scratch is unavoidable and can be outperformed some traditional skyline update methods. In this paper, we propose an efficient method to compute skyline sets over data update streams. Our proposed method uses bounding boxes to summarize consecutive data updates of each data object. This technique enables the pruning capability to identify a smaller set of candidates in skyline computation resulting in faster total computation time. We conduct some experiments through both synthetic and real-life datasets. The results explicitly show that our proposed method significantly runs faster than the baseline in various parameter studies.