{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,17]],"date-time":"2026-04-17T02:53:21Z","timestamp":1776394401666,"version":"3.51.2"},"reference-count":35,"publisher":"Association for Computing Machinery (ACM)","issue":"3","license":[{"start":{"date-parts":[[2008,8,1]],"date-time":"2008-08-01T00:00:00Z","timestamp":1217548800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/501100000038","name":"Natural Sciences and Engineering Research Council of Canada","doi-asserted-by":"publisher","award":["311671-05"],"award-info":[{"award-number":["311671-05"]}],"id":[{"id":"10.13039\/501100000038","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":[[2008,8]]},"abstract":"<jats:p>Ranking and aggregation queries are widely used in data exploration, data analysis, and decision-making scenarios. While most of the currently proposed ranking and aggregation techniques focus on deterministic data, several emerging applications involve data that is unclean or uncertain. Ranking and aggregating uncertain (probabilistic) data raises new challenges in query semantics and processing, making conventional methods inapplicable. Furthermore, uncertainty imposes probability as a new ranking dimension that does not exist in the traditional settings.<\/jats:p>\n          <jats:p>\n            In this article we introduce new probabilistic formulations for top-\n            <jats:italic>k<\/jats:italic>\n            and ranking-aggregate queries in probabilistic databases. Our formulations are based on marriage of traditional top-\n            <jats:italic>k<\/jats:italic>\n            semantics with possible worlds semantics. In the light of these formulations, we construct a generic processing framework supporting both query types, and leveraging existing query processing and indexing capabilities in current RDBMSs. The framework encapsulates a state space model and efficient search algorithms to compute query answers. Our proposed techniques minimize the number of accessed tuples and the size of materialized search space to compute query answers. Our experimental study shows the efficiency of our techniques under different data distributions with orders of magnitude improvement over na\u00efve methods.\n          <\/jats:p>","DOI":"10.1145\/1386118.1386119","type":"journal-article","created":{"date-parts":[[2008,9,4]],"date-time":"2008-09-04T12:51:35Z","timestamp":1220532695000},"page":"1-54","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":66,"title":["Probabilistic top-\n            <i>k<\/i>\n            and ranking-aggregate queries"],"prefix":"10.1145","volume":"33","author":[{"given":"Mohamed A.","family":"Soliman","sequence":"first","affiliation":[{"name":"University of Waterloo, Ontario, Canada"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ihab F.","family":"Ilyas","sequence":"additional","affiliation":[{"name":"University of Waterloo, Ontario, Canada"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Kevin Chen--Chuan","family":"Chang","sequence":"additional","affiliation":[{"name":"University of Illinois at Urbana-Champaign, Urbana, IL"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2008,9,3]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/38714.38724"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2006.35"},{"key":"e_1_2_1_3_1","volume-title":"Proceedings of the 32nd International Conference on Very Large Data Bases (VLDB). 953--964","author":"Benjelloun O.","unstructured":"Benjelloun , O. , Sarma , A. D. , Halevy , A. , and Widom , J . 2006. ULDBs: Databases with uncertainty and lineage . In Proceedings of the 32nd International Conference on Very Large Data Bases (VLDB). 953--964 . Benjelloun, O., Sarma, A. D., Halevy, A., and Widom, J. 2006. ULDBs: Databases with uncertainty and lineage. In Proceedings of the 32nd International Conference on Very Large Data Bases (VLDB). 953--964."},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/1150402.1150463"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.is.2005.06.002"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-006-0004-3"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0022-0000(03)00026-6"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/1066157.1066176"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/376284.375706"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1023\/A:1009726021843"},{"key":"e_1_2_1_11_1","first-page":"100","article-title":"A formal basis for the heuristic determination of minimum cost paths","volume":"4","author":"Hart P. E.","year":"1968","unstructured":"Hart , P. E. , Nilsson , N. J. , and Raphael , B. 1968 . A formal basis for the heuristic determination of minimum cost paths . IEEE Trans. 4 , 2, 100 -- 107 . Hart, P. E., Nilsson, N. J., and Raphael, B. 1968. A formal basis for the heuristic determination of minimum cost paths. IEEE Trans. 4, 2, 100--107.","journal-title":"IEEE Trans."},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/1132863.1132872"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/253260.253291"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1023\/A:1009761603038"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/375663.375690"},{"key":"e_1_2_1_16_1","volume-title":"Proceedings of the 29th International Conference on Very Large Data Base (VLDB). 754--765","author":"Ilyas I. F.","unstructured":"Ilyas , I. F. , Aref , W. G. , and Elmagarmid , A. K . 2003. Supporting top-k join queries in relational databases . In Proceedings of the 29th International Conference on Very Large Data Base (VLDB). 754--765 . Ilyas, I. F., Aref, W. G., and Elmagarmid, A. K. 2003. Supporting top-k join queries in relational databases. In Proceedings of the 29th International Conference on Very Large Data Base (VLDB). 754--765."},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/1007568.1007593"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/1634.1886"},{"key":"e_1_2_1_19_1","volume-title":"Proceedings of the 18th Annual ACM-SIAM SODA Conference. 346--355","author":"Jayram T. S.","unstructured":"Jayram , T. S. , Kale , S. , and Vee , E . 2007. Efficient aggregation algorithms for probabilistic data . In Proceedings of the 18th Annual ACM-SIAM SODA Conference. 346--355 . Jayram, T. S., Kale, S., and Vee, E. 2007. Efficient aggregation algorithms for probabilistic data. In Proceedings of the 18th Annual ACM-SIAM SODA Conference. 346--355."},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1983.35"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/261124.261131"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/1142473.1142481"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/1066157.1066173"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/872757.872817"},{"key":"e_1_2_1_25_1","volume-title":"Proceedings of the 27th Conference on Very Large Data Bases (VLDB). 281--290","author":"Natsev A.","unstructured":"Natsev , A. , Chang , Y. , Smith , J. R. , Li , C. , and Vitter , J. S . 2001. Supporting incremental join queries on ranked inputs . In Proceedings of the 27th Conference on Very Large Data Bases (VLDB). 281--290 . Natsev, A., Chang, Y., Smith, J. R., Li, C., and Vitter, J. S. 2001. Supporting incremental join queries on ranked inputs. In Proceedings of the 27th Conference on Very Large Data Bases (VLDB). 281--290."},{"key":"e_1_2_1_26_1","unstructured":"R-project. The R project for statistical computing: www.r-project.org.  R-project. The R project for statistical computing: www.r-project.org."},{"key":"e_1_2_1_27_1","volume-title":"Proceedings of the 23rd ICDE Conference. 886--895","author":"R\u00e9 C.","unstructured":"R\u00e9 , C. , Dalvi , N. N. , and Suciu , D . 2007. Efficient top-k query evaluation on probabilistic Data . In Proceedings of the 23rd ICDE Conference. 886--895 . R\u00e9, C., Dalvi, N. N., and Suciu, D. 2007. Efficient top-k query evaluation on probabilistic Data. In Proceedings of the 23rd ICDE Conference. 886--895."},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/1044731.1044734"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2006.174"},{"key":"e_1_2_1_30_1","volume-title":"Proceedings of the 23rd ICDE Conference. 596--605","author":"Sen P.","unstructured":"Sen , P. and Deshpande , A . 2007. Representing and querying correlated tuples in probabilistic databases . In Proceedings of the 23rd ICDE Conference. 596--605 . Sen, P. and Deshpande, A. 2007. Representing and querying correlated tuples in probabilistic databases. In Proceedings of the 23rd ICDE Conference. 596--605."},{"key":"e_1_2_1_31_1","volume-title":"Proceedings of the 23rd ICDE Conference. 896--905","author":"Soliman M. A.","unstructured":"Soliman , M. A. , Ilyas , I. F. , and Chang , K. C . 2007a. Top-k query processing in uncertain databases . In Proceedings of the 23rd ICDE Conference. 896--905 . Soliman, M. A., Ilyas, I. F., and Chang, K. C. 2007a. Top-k query processing in uncertain databases. In Proceedings of the 23rd ICDE Conference. 896--905."},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/1247480.1247613"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1137\/0208032"},{"key":"e_1_2_1_34_1","volume-title":"Proceedings of the 2nd Biennial CIDR Conference. 262--276","author":"Widom J.","year":"2005","unstructured":"Widom , J. 2005 . Trio: A system for integrated management of data, accuracy, and lineage . In Proceedings of the 2nd Biennial CIDR Conference. 262--276 . Widom, J. 2005. Trio: A system for integrated management of data, accuracy, and lineage. In Proceedings of the 2nd Biennial CIDR Conference. 262--276."},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2008.4497571"}],"container-title":["ACM Transactions on Database Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1386118.1386119","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1386118.1386119","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T13:57:47Z","timestamp":1750255067000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1386118.1386119"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2008,8]]},"references-count":35,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2008,8]]}},"alternative-id":["10.1145\/1386118.1386119"],"URL":"https:\/\/doi.org\/10.1145\/1386118.1386119","relation":{},"ISSN":["0362-5915","1557-4644"],"issn-type":[{"value":"0362-5915","type":"print"},{"value":"1557-4644","type":"electronic"}],"subject":[],"published":{"date-parts":[[2008,8]]},"assertion":[{"value":"2007-07-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2008-03-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2008-09-03","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}