Approximate Continuous Skyline Queries over Memory Limitation-Based Streaming Data

Continuous skyline query over sliding window is an important problem over streaming data. The query returns all skyline objects to the system whenever the window slides. Existing efforts include exact-based algorithms and approximate-based algorithms. Their key idea is to find objects that cannot become skyline objects before they expire from the window, delete them, and use reminders to support query processing. However, the space cost of all existing efforts is high, and cannot work under memory limitation-based streaming data, i.e., a general environment in real applications. In this paper, we define a novel query named \(\rho -\) approximate continuous skyline query( \(\rho \) -ACSQ), which returns error-bounded answers to the system. Here, \(\rho \) is a threshold, which can bind the error ratio between approximate and exact results. In order to support \(\rho \) -ACSQ, we propose a novel framework named \(\rho -\) SEAK(short for \(\rho -\) Self-adaptive Error-based Approximate Skyline). It can self-adaptively adjust \(\rho \) based on the distribution of streaming data, and achieve the goal of supporting \(\rho \) -ACSQ over memory limitation-based streaming data. Theoretical analysis indicates that even in the worst case, both the running cost and space cost of \(\rho -\) SEAK are all unrelated with data scale.