The most-likely skyline problem for stochastic points

Akash Agrawal; Yuan Li; Jie Xue; Ravi Janardan

doi:10.1016/j.comgeo.2020.101609

The most-likely skyline problem for stochastic points

Akash Agrawal, Yuan Li, Jie Xue, Ravi Janardan

Computer Science and Engineering

Research output: Contribution to journal › Article › peer-review

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

Original language	English (US)
Article number	101609
Journal	Computational Geometry: Theory and Applications
Volume	88
DOIs	https://doi.org/10.1016/j.comgeo.2020.101609
State	Published - Jun 2020

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. The authors thank the reviewers for their insightful comments, which have helped improve the paper greatly.

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:
© 2020 Elsevier B.V.

Keywords

Inapproximability
NP-hardness
Optimal algorithm
Skyline
Stochastic points

Access

10.1016/j.comgeo.2020.101609

OpenUrl availability

Full text

Cite this

@article{ede23233e0df458babca8c4000b5f2dd,

title = "The most-likely skyline problem for stochastic points",

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.",

keywords = "Inapproximability, NP-hardness, Optimal algorithm, Skyline, Stochastic points",

author = "Akash Agrawal and Yuan Li and Jie Xue and Ravi Janardan",

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. The authors thank the reviewers for their insightful comments, which have helped improve the paper greatly. 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: {\textcopyright} 2020 Elsevier B.V.",

year = "2020",

month = jun,

doi = "10.1016/j.comgeo.2020.101609",

language = "English (US)",

volume = "88",

journal = "Computational Geometry: Theory and Applications",

issn = "0925-7721",

publisher = "Elsevier",

}

TY - JOUR

T1 - The most-likely skyline problem for stochastic points

AU - Agrawal, Akash

AU - Li, Yuan

AU - Xue, Jie

AU - Janardan, Ravi

N1 - 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. The authors thank the reviewers for their insightful comments, which have helped improve the paper greatly. 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: © 2020 Elsevier B.V.

PY - 2020/6

Y1 - 2020/6

N2 - 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.

AB - 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.

KW - Inapproximability

KW - NP-hardness

KW - Optimal algorithm

KW - Skyline

KW - Stochastic points

UR - http://www.scopus.com/inward/record.url?scp=85078927846&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85078927846&partnerID=8YFLogxK

U2 - 10.1016/j.comgeo.2020.101609

DO - 10.1016/j.comgeo.2020.101609

M3 - Article

AN - SCOPUS:85078927846

SN - 0925-7721

VL - 88

JO - Computational Geometry: Theory and Applications

JF - Computational Geometry: Theory and Applications

M1 - 101609

ER -

The most-likely skyline problem for stochastic points

Abstract

Bibliographical note

Keywords

Access

OpenUrl availability

Other files and links

Fingerprint

Cite this