The most-likely skyline problem for stochastic points [journal]

Journal

Computational Geometry - January 30, 2020

Authors

Akash Agrawal (Ph.D. 2016), Yuan Li (Ph.D. 2017), Jie Xue (Ph.D. 2019), Ravi Janardan (professor)

Abstract

For a set O of n points in R d, 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 o i∈ O has an associated probability of existence p i∈(0, 1]. The problem of computing the skyline with the maximum probability of occurrence is considered. It is shown that in R d, d≥ 3, the problem is NP-hard and that the desired skyline cannot even be well-approximated in polynomial time unless P= NP. In R 2, an optimal O (n log⁡ n)-time and O (n)-space algorithm is given.

Link to full paper

The most-likely skyline problem for stochastic points

Keywords

geometric computing