{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,9,8]],"date-time":"2025-09-08T06:05:29Z","timestamp":1757311529308},"reference-count":33,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2012,2,10]],"date-time":"2012-02-10T00:00:00Z","timestamp":1328832000000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Theory Comput Syst"],"published-print":{"date-parts":[[2013,4]]},"DOI":"10.1007\/s00224-012-9382-7","type":"journal-article","created":{"date-parts":[[2012,2,9]],"date-time":"2012-02-09T13:12:39Z","timestamp":1328793159000},"page":"342-366","source":"Crossref","is-referenced-by-count":8,"title":["(Approximate) Uncertain Skylines"],"prefix":"10.1007","volume":"52","author":[{"given":"Peyman","family":"Afshani","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Pankaj K.","family":"Agarwal","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Lars","family":"Arge","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Kasper Green","family":"Larsen","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jeff M.","family":"Phillips","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2012,2,10]]},"reference":[{"key":"9382_CR1","volume-title":"14th International Conference on Database Theory","author":"P. Afshani","year":"2011","unstructured":"Afshani, P., Agarwal, P.K., Arge, L., Larsen, K.G., Phillips, J.M.: (Appoximate) uncertain skylines. In: 14th International Conference on Database Theory (2011)"},{"key":"9382_CR2","doi-asserted-by":"crossref","first-page":"49","DOI":"10.1016\/B978-044482537-7\/50003-6","volume-title":"Handbook of Computational Geometry","author":"P.K. Agarwal","year":"2000","unstructured":"Agarwal, P.K., Sharir, M.: Arrangements of surfaces in higher dimensions. In: Sack, J., Urrutia, J. (eds.) Handbook of Computational Geometry, pp. 49\u2013119. North-Holland, Amsterdam (2000)"},{"key":"9382_CR3","volume-title":"ACM Symposium on Principles of Database Systems","author":"P. Agrawal","year":"2006","unstructured":"Agrawal, P., Benjelloun, O., Sarma, A.D., Hayworth, C., Nabar, S., Sugihara, T., Widom, J.: Trio: a\u00a0system for data, uncertainty, and lineage. In: ACM Symposium on Principles of Database Systems (2006)"},{"key":"9382_CR4","first-page":"279","volume-title":"ACM Symposium on Principles of Database Systems","author":"M.J. Atallah","year":"2009","unstructured":"Atallah, M.J., Qi, Y.: Computing all skyline probabilities for uncertain data. In: ACM Symposium on Principles of Database Systems, pp. 279\u2013287 (2009)"},{"issue":"9","key":"9382_CR5","doi-asserted-by":"crossref","first-page":"509","DOI":"10.1145\/361002.361007","volume":"18","author":"J.L. Bentley","year":"1975","unstructured":"Bentley, J.L.: Multidimensional binary search trees used for associative searching. Commun. ACM 18(9), 509\u2013517 (1975)","journal-title":"Commun. ACM"},{"key":"9382_CR6","doi-asserted-by":"crossref","first-page":"485","DOI":"10.1007\/PL00009366","volume":"19","author":"J.-D. Boissonnat","year":"1998","unstructured":"Boissonnat, J.-D., Sharir, M., Tagansky, B., Yvinec, M.: Voronoi diagrams in higher dimensions under certain polyhedral distance functions. Discrete Comput. Geom. 19, 485\u2013519 (1998)","journal-title":"Discrete Comput. Geom."},{"key":"9382_CR7","volume-title":"IEEE International Conference on Data Engineering","author":"S. B\u00f6rzs\u00f6nyi","year":"2001","unstructured":"B\u00f6rzs\u00f6nyi, S., Kossman, D., Stocker, K.: The skyline operator. In: IEEE International Conference on Data Engineering (2001)"},{"key":"9382_CR8","volume-title":"ACM-SIGMOD International Conference on Management of Data","author":"C.-Y. Chan","year":"2006","unstructured":"Chan, C.-Y., Jagadish, H.V., Tan, K.-L., Tung, A.K.H., Zhang, Z.: Finding k-dominant skylines in high dimensional space. In: ACM-SIGMOD International Conference on Management of Data (2006)"},{"key":"9382_CR9","volume-title":"ACM-SIGMOD International Conference on Management of Data","author":"R. Cheng","year":"2003","unstructured":"Cheng, R., Kalashnikov, D.V., Prabhakar, S.: Evaluating probabilitic queries over imprecise data. In: ACM-SIGMOD International Conference on Management of Data (2003)"},{"key":"9382_CR10","volume-title":"IEEE International Conference on Data Engineering","author":"G. Cormode","year":"2009","unstructured":"Cormode, G., Garafalakis, M.: Histograms and wavelets of probabilitic data. In: IEEE International Conference on Data Engineering (2009)"},{"key":"9382_CR11","volume-title":"International Conference on Very Large Data Bases","author":"G. Cormode","year":"2009","unstructured":"Cormode, G., Deligiannakis, A., Garafalakis, M., McGregor, A.: Probabilistic histograms for probabilistic data. In: International Conference on Very Large Data Bases (2009)"},{"key":"9382_CR12","volume-title":"IEEE International Conference on Data Engineering","author":"G. Cormode","year":"2009","unstructured":"Cormode, G., Li, F., Yi, K.: Semantics of ranking queries for probabilistic data and expected ranks. In: IEEE International Conference on Data Engineering (2009)"},{"key":"9382_CR13","doi-asserted-by":"crossref","first-page":"523","DOI":"10.1007\/s00778-006-0004-3","volume":"16","author":"N. Dalvi","year":"2007","unstructured":"Dalvi, N., Suciu, D.: Efficient query evaluation on probabilitic databases. VLDB J. 16, 523\u2013544 (2007)","journal-title":"VLDB J."},{"key":"9382_CR14","volume-title":"International Conference on Very Large Data Bases","author":"A. Sarma Das","year":"2009","unstructured":"Das\u00a0Sarma, A., Lall, A., Nanongkai, D., Xu, J.: Randomized multi-pass streaming skyline algorithms. In: International Conference on Very Large Data Bases (2009)"},{"key":"9382_CR15","volume-title":"IEEE International Conference on Data Engineering","author":"A. Sarma Das","year":"2011","unstructured":"Das\u00a0Sarma, A., Lall, A., Nanongkai, D., Lipton, R.J., Xu, J.: Representative skylines using threshold-based preference distributions. In: IEEE International Conference on Data Engineering (2011)"},{"key":"9382_CR16","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-540-77974-2","volume-title":"Computational Geometry Algorithms and Applications","author":"M. Berg de","year":"2008","unstructured":"de Berg, M., Cheong, O., van Kreveld, M., Overmars, M.: Computational Geometry Algorithms and Applications. Springer, Berlin (2008)"},{"key":"9382_CR17","doi-asserted-by":"crossref","first-page":"317","DOI":"10.1137\/0215023","volume":"15","author":"H. Edelsbunner","year":"1986","unstructured":"Edelsbunner, H., Guibas, L.J., Stolfi, J.: Optimal point location on a monotone subdivision. SIAM J. Comput. 15, 317\u2013340 (1986)","journal-title":"SIAM J. Comput."},{"key":"9382_CR18","doi-asserted-by":"crossref","first-page":"148","DOI":"10.1016\/j.tcs.2006.11.003","volume":"371","author":"V. Koltun","year":"2007","unstructured":"Koltun, V., Papadimitriou, C.H.: Approximately dominating representatives. Theor. Comput. Sci. 371, 148\u2013154 (2007)","journal-title":"Theor. Comput. Sci."},{"key":"9382_CR19","volume-title":"International Conference on Very Large Data Bases","author":"D. Kossman","year":"2002","unstructured":"Kossman, D., Ramsak, F., Rost, S.: Shooting stars in the sky: an optimal algorithm for skyline queries. In: International Conference on Very Large Data Bases (2002)"},{"issue":"4","key":"9382_CR20","doi-asserted-by":"crossref","first-page":"469","DOI":"10.1145\/321906.321910","volume":"22","author":"H.T. Kung","year":"1975","unstructured":"Kung, H.T., Luccio, F., Preparata, F.P.: On finding the maxima of a set of vectors. J. ACM 22(4), 469\u2013476 (1975)","journal-title":"J. ACM"},{"key":"9382_CR21","volume-title":"International Conference on Very Large Data Bases","author":"J. Li","year":"2009","unstructured":"Li, J., Saha, B., Deshpande, A.: A\u00a0unified approach to ranking in probabilistic databases. In: International Conference on Very Large Data Bases (2009)"},{"key":"9382_CR22","volume-title":"ACM-SIGMOD International Conference on Management of Data","author":"X. Lian","year":"2008","unstructured":"Lian, X., Chen, L.: Monochromatic and bichromatic reverse skyline search over uncertain databases. In: ACM-SIGMOD International Conference on Management of Data (2008)"},{"key":"9382_CR23","volume-title":"European Symposium on Algorithms","author":"M. L\u00f6ffler","year":"2009","unstructured":"L\u00f6ffler, M., Phillips, J.M.: Shape fitting of point sets with probability distributions. In: European Symposium on Algorithms (2009)"},{"key":"9382_CR24","first-page":"298","volume-title":"Symposium on Computational Geometry","author":"M. L\u00f6ffler","year":"2008","unstructured":"L\u00f6ffler, M., Snoeyink, J.: Delaunay triangulations of imprecise points in linear time after preprocessing. In: Symposium on Computational Geometry, pp. 298\u2013304 (2008)"},{"key":"9382_CR25","doi-asserted-by":"crossref","DOI":"10.1017\/CBO9780511814075","volume-title":"Randomized Algorithms","author":"R. Motwani","year":"1995","unstructured":"Motwani, R., Raghavan, P.: Randomized Algorithms. Cambridge University Press, Cambridge (1995)"},{"key":"9382_CR26","volume-title":"International Conference on Very Large Data Bases","author":"D. Nanongkai","year":"2010","unstructured":"Nanongkai, D., Das Sarma, A., Lall, A., Lipton, R.J., Xu, J.: Regret-minimizing representative databases. In: International Conference on Very Large Data Bases (2010)"},{"key":"9382_CR27","volume-title":"ACM-SIGMOD International Conference on Management of Data","author":"D. Papadias","year":"2003","unstructured":"Papadias, D., Tao, Y., Fu, G., Seeger, B.: An optimal and progressive algorithm for skyline queries. In: ACM-SIGMOD International Conference on Management of Data (2003)"},{"key":"9382_CR28","volume-title":"International Conference on Very Large Data Bases","author":"J. Pei","year":"2007","unstructured":"Pei, J., Jiang, B., Lin, X., Yuan, Y.: Probabilistic skylines on uncertain data. In: International Conference on Very Large Data Bases (2007)"},{"key":"9382_CR29","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4612-1098-6","volume-title":"Computational Geometry an Introduction","author":"F.P. Preparata","year":"1985","unstructured":"Preparata, F.P., Shamos, M.I.: Computational Geometry an Introduction. Springer, Berlin (1985)"},{"key":"9382_CR30","volume-title":"International Conference on Very Large Data Bases","author":"K.-L. Tan","year":"2001","unstructured":"Tan, K.-L., Eng, P.-K., Ooi, B.C.: Efficient progressive skyline computation. In: International Conference on Very Large Data Bases (2001)"},{"key":"9382_CR31","volume-title":"International Conference on Very Large Data Bases","author":"Y. Tao","year":"2005","unstructured":"Tao, Y., Cheng, R., Xiao, X., Ngai, W.K., Kao, B., Prabhakar, S.: Indexing multi-dimensional uncertain data with arbitrary probability density functions. In: International Conference on Very Large Data Bases (2005)"},{"issue":"1","key":"9382_CR32","doi-asserted-by":"crossref","first-page":"232","DOI":"10.1137\/0214019","volume":"14","author":"D.E. Willard","year":"1985","unstructured":"Willard, D.E.: New data structures for orthogonal range queries. SIAM J. Comput. 14(1), 232\u2013253 (1985)","journal-title":"SIAM J. Comput."},{"key":"9382_CR33","volume-title":"IEEE International Conference on Data Engineering","author":"W. Zhang","year":"2009","unstructured":"Zhang, W., Lin, X., Zhang, Y., Wang, W., Yu, J.X.: Probabilistic skyline operator over sliding windows. In: IEEE International Conference on Data Engineering (2009)"}],"container-title":["Theory of Computing Systems"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-012-9382-7.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00224-012-9382-7\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-012-9382-7","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,7,2]],"date-time":"2020-07-02T00:17:19Z","timestamp":1593649039000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00224-012-9382-7"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012,2,10]]},"references-count":33,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2013,4]]}},"alternative-id":["9382"],"URL":"https:\/\/doi.org\/10.1007\/s00224-012-9382-7","relation":{},"ISSN":["1432-4350","1433-0490"],"issn-type":[{"value":"1432-4350","type":"print"},{"value":"1433-0490","type":"electronic"}],"subject":[],"published":{"date-parts":[[2012,2,10]]}}}