Skip to main content
Journal cover image

Probabilistic skylines on uncertain data: Model and bounding-pruning- refining methods

Publication ,  Journal Article
Jiang, B; Pei, J; Lin, X; Yuan, Y
Published in: Journal of Intelligent Information Systems
February 1, 2012

Uncertain data are inherent in some important applications. Although a considerable amount of research has been dedicated to modeling uncertain data and answering some types of queries on uncertain data, how to conduct advanced analysis on uncertain data remains an open problem at large. In this paper, we tackle the problem of skyline analysis on uncertain data. We propose a novel probabilistic skyline model where an uncertain object may take a probability to be in the skyline, and a p-skyline contains all objects whose skyline probabilities are at least p (0 < p ≤ 1). Computing probabilistic skylines on large uncertain data sets is challenging. We develop a bounding-pruning- refining framework and three algorithms systematically. The bottom-up algorithm computes the skyline probabilities of some selected instances of uncertain objects, and uses those instances to prune other instances and uncertain objects effectively. The top-down algorithm recursively partitions the instances of uncertain objects into subsets, and prunes subsets and objects aggressively. Combining the advantages of the bottom-up algorithm and the top-down algorithm, we develop a hybrid algorithm to further improve the performance. Our experimental results on both the real NBA player data set and the benchmark synthetic data sets show that probabilistic skylines are interesting and useful, and our algorithms are efficient on large data sets. © 2010 Springer Science+Business Media, LLC.

Duke Scholars

Altmetric Attention Stats
Dimensions Citation Stats

Published In

Journal of Intelligent Information Systems

DOI

EISSN

1573-7675

ISSN

0925-9902

Publication Date

February 1, 2012

Volume

38

Issue

1

Start / End Page

1 / 39

Related Subject Headings

  • Information Systems
  • 46 Information and computing sciences
  • 0804 Data Format
  • 0801 Artificial Intelligence and Image Processing
 

Citation

APA
Chicago
ICMJE
MLA
NLM
Jiang, B., Pei, J., Lin, X., & Yuan, Y. (2012). Probabilistic skylines on uncertain data: Model and bounding-pruning- refining methods. Journal of Intelligent Information Systems, 38(1), 1–39. https://doi.org/10.1007/s10844-010-0141-4
Jiang, B., J. Pei, X. Lin, and Y. Yuan. “Probabilistic skylines on uncertain data: Model and bounding-pruning- refining methods.” Journal of Intelligent Information Systems 38, no. 1 (February 1, 2012): 1–39. https://doi.org/10.1007/s10844-010-0141-4.
Jiang B, Pei J, Lin X, Yuan Y. Probabilistic skylines on uncertain data: Model and bounding-pruning- refining methods. Journal of Intelligent Information Systems. 2012 Feb 1;38(1):1–39.
Jiang, B., et al. “Probabilistic skylines on uncertain data: Model and bounding-pruning- refining methods.” Journal of Intelligent Information Systems, vol. 38, no. 1, Feb. 2012, pp. 1–39. Scopus, doi:10.1007/s10844-010-0141-4.
Jiang B, Pei J, Lin X, Yuan Y. Probabilistic skylines on uncertain data: Model and bounding-pruning- refining methods. Journal of Intelligent Information Systems. 2012 Feb 1;38(1):1–39.
Journal cover image

Published In

Journal of Intelligent Information Systems

DOI

EISSN

1573-7675

ISSN

0925-9902

Publication Date

February 1, 2012

Volume

38

Issue

1

Start / End Page

1 / 39

Related Subject Headings

  • Information Systems
  • 46 Information and computing sciences
  • 0804 Data Format
  • 0801 Artificial Intelligence and Image Processing