The Most-Likely Skyline Problem for Stochastic Points.
2017
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.
- Correction
- Source
- Cite
- Save
- Machine Reading By IdeaReader
9
References
5
Citations
NaN
KQI