{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,3]],"date-time":"2026-03-03T16:38:52Z","timestamp":1772555932156,"version":"3.50.1"},"reference-count":29,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2012,5,1]],"date-time":"2012-05-01T00:00:00Z","timestamp":1335830400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/501100000923","name":"Australian Research Council","doi-asserted-by":"publisher","award":["PSE1799"],"award-info":[{"award-number":["PSE1799"]}],"id":[{"id":"10.13039\/501100000923","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001773","name":"University of New South Wales","doi-asserted-by":"publisher","award":["PSE1799"],"award-info":[{"award-number":["PSE1799"]}],"id":[{"id":"10.13039\/501100001773","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Database Syst."],"published-print":{"date-parts":[[2012,5]]},"abstract":"<jats:p>\n            In many applications involving multiple criteria optimal decision making, users may often want to make a personal trade-off among all optimal solutions for selecting one object that fits best their personal needs. As a key feature, the skyline in a multidimensional space provides the minimum set of candidates for such purposes by removing all points not preferred by any (monotonic) utility\/scoring functions; that is, the skyline removes all objects not preferred by any user no matter how their preferences vary. Driven by many recent applications with uncertain data, the probabilistic skyline model is proposed to retrieve uncertain objects based on skyline probabilities. Nevertheless, skyline probabilities cannot capture the preferences of monotonic utility functions. Motivated by this, in this article we propose a novel skyline operator, namely stochastic skylines. In the light of the expected utility principle, stochastic skylines guarantee to provide the minimum set of candidates to optimal solutions over a family of utility functions. We first propose the\n            <jats:italic>lskyline<\/jats:italic>\n            operator based on the\n            <jats:italic>lower orthant orders<\/jats:italic>\n            . lskyline guarantees to provide the minimum set of candidates to the optimal solutions for the family of monotonic multiplicative utility functions. While lskyline works very effectively for the family of multiplicative functions, it may miss optimal solutions for other utility \/scoring functions (e.g., linear functions). To resolve this, we also propose a general stochastic skyline operator,\n            <jats:italic>gskyline<\/jats:italic>\n            , based on the\n            <jats:italic>usual orders<\/jats:italic>\n            . gskyline provides the minimum candidate set to the optimal solutions for all monotonic functions. For the first time regarding the existing literature, we investigate the complexities of determining a stochastic order between two uncertain objects whose probability distributions are described\n            <jats:italic>discretely<\/jats:italic>\n            . We firstly show that determining the lower orthant order is NP-complete with respect to the dimensionality; consequently the problem of computing lskyline is NP-complete. We also show an interesting result as follows. While the usual order involves more complicated geometric forms than the lower orthant order, the usual order may be determined in polynomial time regarding all the inputs, including the dimensionality; this implies that gskyline can be computed in polynomial time. A general framework is developed for efficiently and effectively retrieving lskyline and gskyline from a set of uncertain objects, respectively, together with efficient and effective filtering techniques. Novel and efficient verification algorithms are developed to efficiently compute lskyline over multidimensional uncertain data, which run in polynomial time if the dimensionality is fixed, and to efficiently compute gskyline in polynomial time regarding all inputs. We also show, by theoretical analysis and experiments, that the sizes of lskyline and gskyline are both quite similar to that of conventional skyline over certain data. Comprehensive experiments demonstrate that our techniques are efficient and scalable regarding both CPU and IO costs.\n          <\/jats:p>","DOI":"10.1145\/2188349.2188356","type":"journal-article","created":{"date-parts":[[2012,6,1]],"date-time":"2012-06-01T15:51:28Z","timestamp":1338565888000},"page":"1-34","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":26,"title":["Stochastic skylines"],"prefix":"10.1145","volume":"37","author":[{"given":"Wenjie","family":"Zhang","sequence":"first","affiliation":[{"name":"The University of New South Wales, Australia"}]},{"given":"Xuemin","family":"Lin","sequence":"additional","affiliation":[{"name":"East China Normal University and The University of New South Wales, Australia"}]},{"given":"Ying","family":"Zhang","sequence":"additional","affiliation":[{"name":"The University of New South Wales, Australia"}]},{"given":"Muhammad Aamir","family":"Cheema","sequence":"additional","affiliation":[{"name":"The University of New South Wales, Australia"}]},{"given":"Qing","family":"Zhang","sequence":"additional","affiliation":[{"name":"The Australian EHealth Research Centre, CSIRO, Australia"}]}],"member":"320","published-online":{"date-parts":[[2012,6,4]]},"reference":[{"key":"e_1_2_2_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/1966385.1966390"},{"key":"e_1_2_2_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/1412331.1412343"},{"key":"e_1_2_2_3_1","volume-title":"Proceedings of the International Conference on Data Engineering (ICDE'01)","author":"B\u00f6rzs\u00f6nyi S."},{"key":"e_1_2_2_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/1066157.1066277"},{"key":"e_1_2_2_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/170035.170075"},{"key":"e_1_2_2_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/1066157.1066181"},{"key":"e_1_2_2_7_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2006.131"},{"key":"e_1_2_2_8_1","volume-title":"Proceedings of the International Conference on Data Engineering (ICDE'03)","author":"Chomicki J."},{"key":"e_1_2_2_9_1","unstructured":"Cormen T. H. Leiserson C. E. Rivest R. L. and Stein C. 2001. Introduction to Algorithms 2nd Ed. The MIT Press Cambridge MA.   Cormen T. H. Leiserson C. E. Rivest R. L. and Stein C. 2001. Introduction to Algorithms 2 nd Ed. The MIT Press Cambridge MA."},{"key":"e_1_2_2_10_1","unstructured":"Garey M. and Johnson D. 1990. Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman and Company.  Garey M. and Johnson D. 1990. Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman and Company."},{"key":"e_1_2_2_11_1","volume-title":"Proceedings of the International Conference on Very Large Databases (VLDB'05)","author":"Godfrey P."},{"key":"e_1_2_2_12_1","doi-asserted-by":"publisher","DOI":"10.1287\/opre.1080.0524"},{"key":"e_1_2_2_13_1","doi-asserted-by":"publisher","DOI":"10.1007\/s001860050102"},{"key":"e_1_2_2_14_1","volume-title":"Proceedings of the International Conference on Very Large Databases (VLDB'02)","author":"Kossmann D."},{"key":"e_1_2_2_15_1","volume-title":"Proceedings of the International Conference on Very Large Databases (VLDB'07)","author":"Lee K. C. K."},{"key":"e_1_2_2_16_1","doi-asserted-by":"publisher","DOI":"10.1287\/mnsc.38.4.555"},{"key":"e_1_2_2_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/1376616.1376641"},{"key":"e_1_2_2_18_1","volume-title":"Proceedings of the International Conference on Data Engineering (ICDE'07)","author":"Lin X."},{"key":"e_1_2_2_19_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2011.5767896"},{"key":"e_1_2_2_20_1","doi-asserted-by":"crossref","volume-title":"A Natural Introduction to Probability Theory","author":"Meester R.","DOI":"10.1007\/978-3-0348-7786-2"},{"key":"e_1_2_2_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/872757.872814"},{"key":"e_1_2_2_22_1","volume-title":"Proceedings of the International Conference on Very Large Databases (VLDB'07)","author":"Pei J."},{"key":"e_1_2_2_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/1189769.1189774"},{"key":"e_1_2_2_24_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2006.174"},{"key":"e_1_2_2_25_1","doi-asserted-by":"crossref","unstructured":"Shaked M. and Shanthikumar J. G. 2007. Stochastic Orders and Their Applications. Academic Press.  Shaked M. and Shanthikumar J. G. 2007. Stochastic Orders and Their Applications. Academic Press.","DOI":"10.1007\/978-0-387-34675-5"},{"key":"e_1_2_2_26_1","volume-title":"Multi Criteria Optimization: Theory, Computation, and Application","author":"Steuer R. E."},{"key":"e_1_2_2_27_1","volume-title":"Proceedings of the International Conference on Very Large Databases (VLDB'01)","author":"Tan K.-L."},{"key":"e_1_2_2_28_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2004.93"},{"key":"e_1_2_2_29_1","doi-asserted-by":"publisher","DOI":"10.1145\/1559845.1559897"}],"container-title":["ACM Transactions on Database Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2188349.2188356","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2188349.2188356","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T08:49:11Z","timestamp":1750236551000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2188349.2188356"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012,5]]},"references-count":29,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2012,5]]}},"alternative-id":["10.1145\/2188349.2188356"],"URL":"https:\/\/doi.org\/10.1145\/2188349.2188356","relation":{},"ISSN":["0362-5915","1557-4644"],"issn-type":[{"value":"0362-5915","type":"print"},{"value":"1557-4644","type":"electronic"}],"subject":[],"published":{"date-parts":[[2012,5]]},"assertion":[{"value":"2011-08-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2012-03-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2012-06-04","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}