On efficient k-Skyband query processing over incomplete data

Xiaoye Miao, Yunjun Gao, Lu Chen, Gang Chen, Qing Li, Tao Jiang

Research output: Chapter in book / Conference proceedingConference article published in proceeding or bookAcademic researchpeer-review

12 Citations (Scopus)


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.

Original languageEnglish
Title of host publicationDatabase Systems for Advanced Applications - 18th International Conference, DASFAA 2013, Proceedings
Number of pages16
EditionPART 1
Publication statusPublished - 1 Dec 2013
Externally publishedYes
Event18th International Conference on Database Systems for Advanced Applications, DASFAA 2013 - Wuhan, China
Duration: 22 Apr 201325 Apr 2013

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
NumberPART 1
Volume7825 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


Conference18th International Conference on Database Systems for Advanced Applications, DASFAA 2013

ASJC Scopus subject areas

  • Theoretical Computer Science
  • General Computer Science


Dive into the research topics of 'On efficient k-Skyband query processing over incomplete data'. Together they form a unique fingerprint.

Cite this