On efficient k-Skyband query processing over incomplete data

The Skyline query and its variants have been extensively explored in the literature. Existing approaches, except one, assume that all dimensions are available for all data items. However, many practical applications such as sensor networks, decision making, and location-based services, may involve incomplete data items, i.e., some dimensional values are missing , due to the device failure or the privacy preservation. In this paper, for the first time, we study the problem of efficient k-Skyband (kSB) query processing on incomplete data, where multi-dimensional data items are missing some values of their dimensions. We formalize the problem, and then present several efficient algorithms for tackling it. Our methods employ some novel concepts/structures (e.g., expired skyline, shadow skyline, thickness warehouse, etc.) to improve the search performance. Extensive experiments with both real and synthetic data sets demonstrate the effectiveness and efficiency of our proposed algorithms. © Springer-Verlag 2013.