Skip to main content
Journal cover image

Ranking uncertain sky: The probabilistic top-k skyline operator

Publication ,  Journal Article
Zhang, Y; Zhang, W; Lin, X; Jiang, B; Pei, J
Published in: Information Systems
July 1, 2011

Many recent applications involve processing and analyzing uncertain data. In this paper, we combine the feature of top-k objects with that of skyline to model the problem of top-k skyline objects against uncertain data. The problem of efficiently computing top-k skyline objects on large uncertain datasets is challenging in both discrete and continuous cases. In this paper, firstly an efficient exact algorithm for computing the top-k skyline objects is developed for discrete cases. To address applications where each object may have a massive set of instances or a continuous probability density function, we also develop an efficient randomized algorithm with an approximation guarantee. Moreover, our algorithms can be immediately extended to efficiently compute p-skyline; that is, retrieving the uncertain objects with skyline probabilities above a given threshold. Our extensive experiments on synthetic and real data demonstrate the efficiency of both algorithms and the randomized algorithm is highly accurate. They also show that our techniques significantly outperform the existing techniques for computing p-skyline. © 2011 Elsevier B.V. All rights reserved.

Duke Scholars

Published In

Information Systems

DOI

ISSN

0306-4379

Publication Date

July 1, 2011

Volume

36

Issue

5

Start / End Page

898 / 915

Related Subject Headings

  • Information Systems
  • 4609 Information systems
  • 0806 Information Systems
 

Citation

APA
Chicago
ICMJE
MLA
NLM
Zhang, Y., Zhang, W., Lin, X., Jiang, B., & Pei, J. (2011). Ranking uncertain sky: The probabilistic top-k skyline operator. Information Systems, 36(5), 898–915. https://doi.org/10.1016/j.is.2011.03.008
Zhang, Y., W. Zhang, X. Lin, B. Jiang, and J. Pei. “Ranking uncertain sky: The probabilistic top-k skyline operator.” Information Systems 36, no. 5 (July 1, 2011): 898–915. https://doi.org/10.1016/j.is.2011.03.008.
Zhang Y, Zhang W, Lin X, Jiang B, Pei J. Ranking uncertain sky: The probabilistic top-k skyline operator. Information Systems. 2011 Jul 1;36(5):898–915.
Zhang, Y., et al. “Ranking uncertain sky: The probabilistic top-k skyline operator.” Information Systems, vol. 36, no. 5, July 2011, pp. 898–915. Scopus, doi:10.1016/j.is.2011.03.008.
Zhang Y, Zhang W, Lin X, Jiang B, Pei J. Ranking uncertain sky: The probabilistic top-k skyline operator. Information Systems. 2011 Jul 1;36(5):898–915.
Journal cover image

Published In

Information Systems

DOI

ISSN

0306-4379

Publication Date

July 1, 2011

Volume

36

Issue

5

Start / End Page

898 / 915

Related Subject Headings

  • Information Systems
  • 4609 Information systems
  • 0806 Information Systems