Skyline ranking for uncertain databases

Hyountaek Yong, Jongwuk Lee, Jinha Kim, Seung Won Hwang

Research output: Contribution to journalArticlepeer-review

14 Citations (Scopus)


Skyline queries have been actively studied to effectively identify interesting tuples with low formulation overhead. This paper aims to support skyline queries for uncertain data with maybe confidence. Prior skyline work for uncertain data assumes that each tuple is exhaustively enumerated with all possible probabilities of alternative confidence. However, it is inappropriate to some real-life scenarios, e.g., scientific Web data or privacy-preserving data, such that each tuple is associated with a probability of existence. We thus propose novel skyline algorithms that efficiently deal with maybe uncertainty, leveraging auxiliary indexes, i.e., an R-tree or a dominance graph. We also discuss our proposed algorithms over data dependency. Our experiments demonstrate that the proposed algorithms are significantly faster than a naive method by orders of magnitude.

Original languageEnglish
Pages (from-to)247-262
Number of pages16
JournalInformation sciences
Publication statusPublished - 2014

Bibliographical note

Funding Information:
This research was supported by IT R&D program of MKE/KEIT . [ KI001810041244 , SmartTV 2.0 Software Platform]

All Science Journal Classification (ASJC) codes

  • Software
  • Control and Systems Engineering
  • Theoretical Computer Science
  • Computer Science Applications
  • Information Systems and Management
  • Artificial Intelligence


Dive into the research topics of 'Skyline ranking for uncertain databases'. Together they form a unique fingerprint.

Cite this