(Approximate) Uncertain Skylines

被引：4

作者：

Afshani, Peyman ^{[1
]}

Agarwal, Pankaj K. ^{[2
]}

Arge, Lars ^{[3
,4
]}

Larsen, Kasper Green ^{[3
,4
]}

Phillips, Jeff M. ^{[5
]}

机构：

[1] Dalhousie Univ, Fac Comp Sci, Halifax, NS, Canada

[2] Duke Univ, Dept Comp Sci, Durham, NC 27708 USA

[3] Univ Aarhus, MADALGO, DK-8200 Aarhus N, Denmark

[4] Univ Aarhus, Dept Comp Sci, DK-8200 Aarhus N, Denmark

[5] Univ Utah, Sch Comp, Salt Lake City, UT 84112 USA

来源：

THEORY OF COMPUTING SYSTEMS | 2013年 / 52卷 / 03期

基金：

美国国家科学基金会;

关键词：

Data structures; Approximation algorithms; Computational geometry;

D O I：

10.1007/s00224-012-9382-7

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

Given a set of points with uncertain locations, we consider the problem of computing the probability of each point lying on the skyline, that is, the probability that it is not dominated by any other input point. If each point's uncertainty is described as a probability distribution over a discrete set of locations, we improve the best known exact solution. We also suggest why we believe our solution might be optimal. Next, we describe simple, near-linear time approximation algorithms for computing the probability of each point lying on the skyline. In addition, some of our methods can be adapted to construct data structures that can efficiently determine the probability of a query point lying on the skyline.

引用

页码：342 / 366

页数：25

共 32 条

[1] Afshani P., 2011, 14 INT C DAT THEOR
[2] Agarwal PK, 2000, HANDBOOK OF COMPUTATIONAL GEOMETRY, P49, DOI 10.1016/B978-044482537-7/50003-6
[3] Agrawal P., 2006, ACM S PRINC DAT SYST
[4] Computing All Skyline Probabilities for Uncertain Data
Atallah, Mikhail J.
Qi, Yinian
[J]. PODS'09: PROCEEDINGS OF THE TWENTY-EIGHTH ACM SIGMOD-SIGACT-SIGART SYMPOSIUM ON PRINCIPLES OF DATABASE SYSTEMS, 2009, : 279 - 287
[5] MULTIDIMENSIONAL BINARY SEARCH TREES USED FOR ASSOCIATIVE SEARCHING
BENTLEY, JL
[J]. COMMUNICATIONS OF THE ACM, 1975, 18 (09) : 509 - 517
[6] Voronoi diagrams in higher dimensions under certain polyhedral distance functions
Boissonnat, JD
Sharir, M
Tagansky, B
Yvinec, M
[J]. DISCRETE & COMPUTATIONAL GEOMETRY, 1998, 19 (04) : 485 - 519
[7] The Skyline operator
Börzsönyi, S
Kossmann, D
Stocker, K
[J]. 17TH INTERNATIONAL CONFERENCE ON DATA ENGINEERING, PROCEEDINGS, 2001, : 421 - 430
[8] Chan C.-Y., 2006, ACM SIGMOD INT C MAN
[9] Cheng R., 2003, ACM SIGMOD INT C MAN
[10] Cormode G., 2009, INT C VER LARG DAT B

← 1 2 3 4 →