{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,24]],"date-time":"2026-02-24T12:56:34Z","timestamp":1771937794870,"version":"3.50.1"},"reference-count":38,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2011,5,1]],"date-time":"2011-05-01T00:00:00Z","timestamp":1304208000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/100000143","name":"Division of Computing and Communication Foundations","doi-asserted-by":"publisher","award":["CCF-0939370"],"award-info":[{"award-number":["CCF-0939370"]}],"id":[{"id":"10.13039\/100000143","id-type":"DOI","asserted-by":"publisher"}]},{"name":"Qtar National Research","award":["FA9550-09-1-0223"],"award-info":[{"award-number":["FA9550-09-1-0223"]}]},{"DOI":"10.13039\/100000144","name":"Division of Computer and Network Systems","doi-asserted-by":"publisher","award":["CNS-0915436CNS-0913875"],"award-info":[{"award-number":["CNS-0915436CNS-0913875"]}],"id":[{"id":"10.13039\/100000144","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100007567","name":"City University of Hong Kong","doi-asserted-by":"publisher","award":["7200218"],"award-info":[{"award-number":["7200218"]}],"id":[{"id":"10.13039\/100007567","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":[[2011,5]]},"abstract":"<jats:p>\n            Skyline computation is widely used in multicriteria decision making. As research in uncertain databases draws increasing attention, skyline queries with uncertain data have also been studied. Some earlier work focused on probabilistic skylines with a given threshold; Atallah and Qi [2009] studied the problem to compute skyline probabilities for all instances of uncertain objects without the use of thresholds, and proposed an algorithm with subquadratic time complexity. In this work, we propose a new algorithm for computing all skyline probabilities that is asymptotically faster: worst-case\n            <jats:italic>O(n<\/jats:italic>\n            \u221a\n            <jats:italic>n<\/jats:italic>\n            log\n            <jats:italic>n<\/jats:italic>\n            ) time and\n            <jats:italic>O(n)<\/jats:italic>\n            space for 2D data;\n            <jats:italic>O<\/jats:italic>\n            (\n            <jats:italic>n<\/jats:italic>\n            <jats:sup>2\u22121\/d<\/jats:sup>\n            log\n            <jats:sup>\n              <jats:italic>d<\/jats:italic>\n              \u22121\n            <\/jats:sup>\n            <jats:italic>n<\/jats:italic>\n            ) time and\n            <jats:italic>O(n<\/jats:italic>\n            log\n            <jats:sup>\n              <jats:italic>d<\/jats:italic>\n              \u22122\n            <\/jats:sup>\n            <jats:italic>n<\/jats:italic>\n            ) space for\n            <jats:italic>d<\/jats:italic>\n            -dimensional data. Furthermore, we study the online version of the problem: Given any query point\n            <jats:italic>p<\/jats:italic>\n            (unknown until the query time), return the probability that no instance in the given data set dominates\n            <jats:italic>p<\/jats:italic>\n            . We propose an algorithm for answering such an online query for\n            <jats:italic>d<\/jats:italic>\n            -dimensional data in\n            <jats:italic>O(n<\/jats:italic>\n            <jats:sup>\n              1\u22121\/\n              <jats:italic>d<\/jats:italic>\n            <\/jats:sup>\n            log\n            <jats:sup>\n              <jats:italic>d<\/jats:italic>\n              \u22121\n            <\/jats:sup>\n            <jats:italic>n<\/jats:italic>\n            ) time after preprocessing the data in\n            <jats:italic>O(n<\/jats:italic>\n            <jats:sup>2\u22121\/d<\/jats:sup>\n            log\n            <jats:sup>\n              <jats:italic>d<\/jats:italic>\n              \u22121\n            <\/jats:sup>\n            ) time and space.\n          <\/jats:p>","DOI":"10.1145\/1966385.1966390","type":"journal-article","created":{"date-parts":[[2011,6,6]],"date-time":"2011-06-06T11:51:38Z","timestamp":1307361098000},"page":"1-28","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":23,"title":["Asymptotically efficient algorithms for skyline probabilities of uncertain data"],"prefix":"10.1145","volume":"36","author":[{"given":"Mikhail J.","family":"Atallah","sequence":"first","affiliation":[{"name":"Purdue University, West Lafayette"}]},{"given":"Yinian","family":"Qi","sequence":"additional","affiliation":[{"name":"Purdue University, West Lafayette"}]},{"given":"Hao","family":"Yuan","sequence":"additional","affiliation":[{"name":"City University of Hong Kong, Kowloon, Hong Kong"}]}],"member":"320","published-online":{"date-parts":[[2011,6,2]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1137\/0216067"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/1938551.1938576"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2008.4497507"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/1559795.1559837"},{"key":"e_1_2_1_5_1","volume-title":"Proceedings of the 32nd International Conference on Very Large Data Bases (VLDB). VLDB Endowment, 953--964","author":"Benjelloun O."},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/358841.358850"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.14778\/1453856.1453895"},{"key":"e_1_2_1_8_1","volume-title":"Proceedings of the 17th International Conference on Data Engineering. IEEE Computer Society","author":"B\u00f6rzs\u00f6nyi S."},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/1066157.1066277"},{"key":"e_1_2_1_10_1","volume-title":"Proceedings of the 33rd International Conference on Very Large Data Bases (VLDB). VLDB Endowment, 770--781","author":"Chen B.-C."},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2008.4497506"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/872757.872823"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2004.46"},{"key":"e_1_2_1_14_1","volume-title":"Proceedings of the 30th International Conference on Very Large Data Bases VLDB.","volume":"30","author":"Cheng R."},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2009.75"},{"key":"e_1_2_1_16_1","volume-title":"Proceedings of the 33rd International Conference on Very Large Data Bases (VLDB). VLDB Endowment, 291--302","author":"Dellis E."},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/1376616.1376685"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/321906.321910"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.14778\/1687627.1687685"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/1376616.1376641"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/1353343.1353406"},{"key":"e_1_2_1_22_1","volume-title":"Proceedings of the IEEE 23rd International Conference on Data Engineering (ICDE). 86--95","author":"Lin X."},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2008.4497465"},{"key":"e_1_2_1_24_1","doi-asserted-by":"crossref","unstructured":"Mehlhorn K. 1984. Data Structures and Algorithms 3: Multi-dimensional Searching and Computational Geometry. Springer-Verlag Berlin.   Mehlhorn K. 1984. Data Structures and Algorithms 3: Multi-dimensional Searching and Computational Geometry. Springer-Verlag Berlin.","DOI":"10.1007\/978-3-642-69900-9_2"},{"key":"e_1_2_1_25_1","volume-title":"Proceedings of the 33rd International Conference on Very Large Data Bases (VLDB). VLDB Endowment, 267--278","author":"Morse M."},{"key":"e_1_2_1_26_1","volume-title":"Proceedings of the IEEE 23rd International Conference on Data Engineering (ICDE). 96--105","author":"Pei J."},{"key":"e_1_2_1_27_1","volume-title":"Proceedings of the 33rd International Conference on Very Large Data Bases (VLDB). VLDB Endowment, 15--26","author":"Pei J."},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4612-1098-6"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2008.4497511"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2008.4497514"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/1247480.1247613"},{"key":"e_1_2_1_32_1","volume-title":"Proceedings of the 31st International Conference on Very Large Data Bases (VLDB). VLDB Endowment, 922--933","author":"Tao Y."},{"key":"e_1_2_1_33_1","volume-title":"Proceedings of the IEEE 23rd International Conference on Data Engineering (ICDE). 416--425","author":"Vlachou A."},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1137\/0214019"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2007.367894"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2009.83"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10619-009-7050-y"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1109\/FGCN.2007.115"}],"container-title":["ACM Transactions on Database Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1966385.1966390","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1966385.1966390","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T11:22:26Z","timestamp":1750245746000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1966385.1966390"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2011,5]]},"references-count":38,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2011,5]]}},"alternative-id":["10.1145\/1966385.1966390"],"URL":"https:\/\/doi.org\/10.1145\/1966385.1966390","relation":{},"ISSN":["0362-5915","1557-4644"],"issn-type":[{"value":"0362-5915","type":"print"},{"value":"1557-4644","type":"electronic"}],"subject":[],"published":{"date-parts":[[2011,5]]},"assertion":[{"value":"2010-05-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2011-02-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2011-06-02","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}