Efficient Computation of Skyline Queries on Incomplete Dynamic Data

Skyline query is a typical preference query method. Due to its capacity of extracting interesting information from multi-dimensional datasets abided by multiple criterions, the skyline query has been extensively studied. All of the existing studies assume that the data are complete and available, which may not hold in many real applications because of device exception, privacy protection and other reasons. Datasets with missing attribute values or missing tuples are called incomplete datasets. In this paper, we mainly discussed the case of incomplete attribute values in a dynamic dataset. First, considering the dynamic dataset, we propose the kISkyline algorithm based on the traditional sliding window model with a split bucket strategy. We then propose the sISkyline algorithm based on a real point, virtual point, and shadow point with a split bucket strategy along with the traditional sliding window model. Finally, simulation results are provided to demonstrate the feasibility and effectiveness of these two new algorithms.