The most-likely skyline problem for stochastic points

Akash Agrawal, Yuan Li, Jie Xue, Ravi Janardan

Research output: Contribution to conferencePaperpeer-review

4 Scopus citations


For a set O of n points in Rd, the skyline consists of the subset of all points of O where no point is dominated by any other point of O. Suppose that each point oi ∈ O has an associated probability of existence pi ∈ (0, 1]. The problem of computing the skyline with the maximum probability of occurrence is considered. It is shown that in Rd, d ≥ 3, the problem is NP-hard and that the desired skyline cannot even be well-approximated in polynomial-time unless P = NP. In R2, an optimal O(n log n)-time and O(n)-space algorithm is given.

Original languageEnglish (US)
Number of pages6
StatePublished - 2017
Event29th Canadian Conference on Computational Geometry, CCCG 2017 - Ottawa, Canada
Duration: Jul 26 2017Jul 28 2017


Conference29th Canadian Conference on Computational Geometry, CCCG 2017

Bibliographical note

Funding Information:
The research of the first author was supported, in part, by a Doctoral Dissertation Fellowship from the Graduate School of the University of Minnesota.

Publisher Copyright:
Compilation copyright © 2017 Michiel Smid Copyright of individual papers retained by authors.All right reserved.


Dive into the research topics of 'The most-likely skyline problem for stochastic points'. Together they form a unique fingerprint.

Cite this