Efficient and scalable continuous skyline monitoring in two-tier streaming settings

Two-tier streaming settings are a typical dynamic environment where continuous skylines represent an important semantic indicator for multiple attributes. To monitor skylines over the dynamic data in such settings, one needs to continuously update the skyline query results in order to reflect the new data values. This paper tackles the problem of continuous skyline monitoring on a central query server over dynamic data from multiple data sites. Simply sending the updates of tuple values to the server is cost-prohibitive. Therefore, we propose an approach that allows the central server to collaborate with the data sites to monitor the possible skyline changes. By doing so, the processing load is distributed over all the data sites instead of only on the central server. Furthermore, this collaborative approach minimizes the bandwidth consumption between the server and the data sites, which is often critical in a widely distributed environment such as a wide-area sensor network. We give theoretical upper bounds for the computation costs and communication costs of the proposed collaborative approach. We also conduct extensive experiments on both synthetic and real data sets. The experimental results demonstrate that our collaborative approach is efficient, scalable and well-balanced in terms of communication costs and computation costs.

► We formalize the continuous skyline monitoring problem in a generic streaming setting.
► A thorough case study is conducted on the incremental changes of continuous skylines.
► An efficient two-tier continuous skyline maintenance approach is proposed.
► Theoretical upper bounds for computation and communication costs are presented.
► The proposal is evaluated by an extensive experimental study.