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 data items. However, many practical applications such as sensor networks, decision making, location-based services, may involve incomplete items, i.e., some dimensional values missing, due to device failure or privacy preservation. In this paper, first time, we study problem of efficient k-Skyband (kSB) processing on data, where multi-dimensional items missing their dimensions. We formalize problem, then present several algorithms tackling it. Our methods employ novel concepts/structures (e.g., expired skyline, shadow thickness warehouse, etc.) improve search performance. Extensive experiments with both real synthetic sets demonstrate effectiveness efficiency our proposed algorithms.