Approximate) Uncertain Skylines
作者： Peyman Afshani , Pankaj K. Agarwal , Lars Arge , Kasper Green Larsen , Jeff M. Phillips
DOI: 10.1007/S00224-012-9382-7
关键词:
摘要: Given a set of points with uncertain locations, we consider the problem computing probability each point lying on skyline, that is, it is not dominated by any other input point. If point's uncertainty described as distribution over discrete improve best known exact solution. We also suggest why believe our solution might be optimal. Next, describe simple, near-linear time approximation algorithms for skyline. In addition, some methods can adapted to construct data structures efficiently determine query
springer.com
sci-hub.se 参考文章(36)
Pankaj K. Agarwal, Micha Sharir, Arrangements and Their Applications Handbook of Computational Geometry. pp. 49- 119 ,(2000) , 10.1016/B978-044482537-7/50003-6
Beng Chin Ooi, Pin-Kwang Eng, Kian-Lee Tan, Efficient Progressive Skyline Computation very large data bases. pp. 301- 310 ,(2001)
J.-D. Boissonnat, M. Sharir, B. Tagansky, M. Yvinec, Voronoi Diagrams in Higher Dimensions under Certain Polyhedral Distance Functions Discrete and Computational Geometry. ,vol. 19, pp. 485- 519 ,(1998) , 10.1007/PL00009366
Xiang Lian, Lei Chen, Monochromatic and bichromatic reverse skyline search over uncertain databases Proceedings of the 2008 ACM SIGMOD international conference on Management of data - SIGMOD '08. pp. 213- 226 ,(2008) , 10.1145/1376616.1376641
Dan E. Willard, New data structures for orthogonal range queries SIAM Journal on Computing. ,vol. 14, pp. 232- 253 ,(1985) , 10.1137/0214019
Wenjie Zhang, Xuemin Lin, Ying Zhang, Wei Wang, Jeffrey Xu Yu, Probabilistic Skyline Operator over Sliding Windows 2009 IEEE 25th International Conference on Data Engineering. pp. 1060- 1071 ,(2009) , 10.1109/ICDE.2009.83
Maarten Löffler, Jack Snoeyink, Delaunay triangulation of imprecise points in linear time after preprocessing Computational Geometry. ,vol. 43, pp. 234- 242 ,(2010) , 10.1016/J.COMGEO.2008.12.007
H. T. Kung, F. Luccio, F. P. Preparata, On Finding the Maxima of a Set of Vectors Journal of the ACM. ,vol. 22, pp. 469- 476 ,(1975) , 10.1145/321906.321910
Mikhail J. Atallah, Yinian Qi, Computing all skyline probabilities for uncertain data Proceedings of the twenty-eighth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems - PODS '09. pp. 279- 287 ,(2009) , 10.1145/1559795.1559837
Nilesh Dalvi, Dan Suciu, Efficient query evaluation on probabilistic databases very large data bases. ,vol. 16, pp. 523- 544 ,(2004) , 10.1007/S00778-006-0004-3