Processing k-skyband, constrained skyline, and group-by skyline queries on incomplete data

Y. Gao, X. Miao, H. Cui, G. Chen, Qing Li

Research output: Journal article publicationJournal articleAcademic researchpeer-review

27 Citations (Scopus)

Abstract

The skyline operator has been extensively explored in the literature, and most of the existing approaches 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. This paper is the first, to our knowledge, study of 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 two efficient algorithms for processing it. Our methods introduce some novel concepts including expired skyline, shadow skyline, and thickness warehouse, in order to boost the search performance. As a second step, we extend our techniques to tackle constrained skyline (CS) and group-by skyline (GBS) queries over incomplete data. Extensive experiments with both real and synthetic data sets demonstrate the effectiveness and efficiency of our proposed algorithms under various experimental settings. © 2014 Elsevier Ltd. All rights reserved.
Original languageEnglish
Pages (from-to)4959-4974
Number of pages16
JournalExpert Systems with Applications
Volume41
Issue number10
DOIs
Publication statusPublished - 1 Jan 2014
Externally publishedYes

Keywords

  • Constrained skyline
  • Group-by skyline
  • Incomplete data
  • k-Skyband
  • Query processing
  • Skyline

ASJC Scopus subject areas

  • Engineering(all)
  • Computer Science Applications
  • Artificial Intelligence

Cite this