The most-likely skyline problem for stochastic points

Akash Agrawal, Yuan Li, Jie Xue, Ravi Janardan

Research output: Contribution to journalArticle

Abstract

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(nlog⁡n)-time and O(n)-space algorithm is given.

Original languageEnglish (US)
Article number101609
JournalComputational Geometry: Theory and Applications
Volume88
DOIs
StatePublished - Jun 2020

Keywords

  • Inapproximability
  • NP-hardness
  • Optimal algorithm
  • Skyline
  • Stochastic points

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

  • Cite this