{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,19]],"date-time":"2025-03-19T11:37:45Z","timestamp":1742384265494},"reference-count":39,"publisher":"Association for Computing Machinery (ACM)","issue":"1","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. VLDB Endow."],"published-print":{"date-parts":[[2009,8]]},"abstract":"<jats:p>\n            The dramatic growth in the number of application domains that naturally generate probabilistic, uncertain data has resulted in a need for efficiently supporting complex querying and decision-making over such data. In this paper, we present a unified approach to ranking and top-k query processing in probabilistic databases by viewing it as a multi-criteria optimization problem, and by deriving a set of\n            <jats:italic>features<\/jats:italic>\n            that capture the key properties of a probabilistic dataset that dictate the ranked result. We contend that a single, specific ranking function may not suffice for probabilistic databases, and we instead propose two\n            <jats:italic>parameterized ranking functions<\/jats:italic>\n            , called\n            <jats:italic>PRF<\/jats:italic>\n            <jats:sup>\u03c9<\/jats:sup>\n            and\n            <jats:italic>PRF<\/jats:italic>\n            <jats:sup>\n              <jats:italic>e<\/jats:italic>\n            <\/jats:sup>\n            , that generalize or can approximate many of the previously proposed ranking functions. We present novel\n            <jats:italic>generating functions<\/jats:italic>\n            -based algorithms for efficiently ranking large datasets according to these ranking functions, even if the datasets exhibit complex correlations modeled using\n            <jats:italic>probabilistic and\/xor trees<\/jats:italic>\n            or\n            <jats:italic>Markov networks<\/jats:italic>\n            . We further propose that the parameters of the ranking function be learned from user preferences, and we develop an approach to learn those parameters. Finally, we present a comprehensive experimental study that illustrates the effectiveness of our parameterized ranking functions, especially\n            <jats:italic>PRF<\/jats:italic>\n            <jats:sup>\n              <jats:italic>e<\/jats:italic>\n            <\/jats:sup>\n            , at approximating other ranking functions and the scalability of our proposed algorithms for exact or approximate ranking.\n          <\/jats:p>","DOI":"10.14778\/1687627.1687685","type":"journal-article","created":{"date-parts":[[2014,6,24]],"date-time":"2014-06-24T12:17:57Z","timestamp":1403612277000},"page":"502-513","source":"Crossref","is-referenced-by-count":85,"title":["A unified approach to ranking in probabilistic databases"],"prefix":"10.14778","volume":"2","author":[{"given":"Jian","family":"Li","sequence":"first","affiliation":[{"name":"University of Maryland at College Park"}]},{"given":"Barna","family":"Saha","sequence":"additional","affiliation":[{"name":"University of Maryland at College Park"}]},{"given":"Amol","family":"Deshpande","sequence":"additional","affiliation":[{"name":"University of Maryland at College Park"}]}],"member":"320","published-online":{"date-parts":[[2009,8]]},"reference":[{"key":"e_1_2_1_1_1","volume-title":"Managing uncertainty in social networks","author":"Adar E.","year":"2007","unstructured":"E. Adar and C. Re . Managing uncertainty in social networks . IEEE Data Eng. Bull ., 2007 . E. Adar and C. Re. Managing uncertainty in social networks. IEEE Data Eng. Bull., 2007."},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2006.35"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.acha.2005.01.003"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/1102351.1102363"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/872757.872823"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2009.75"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.5555\/1316689.1316764"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/1265530.1265531"},{"key":"e_1_2_1_9_1","volume-title":"NIPS 16","author":"Dekel O.","year":"2004","unstructured":"O. Dekel , C. Manning , and Y. Singer . Log-linear models for label-ranking . In NIPS 16 , 2004 . O. Dekel, C. Manning, and Y. Singer. Log-linear models for label-ranking. In NIPS 16, 2004."},{"key":"e_1_2_1_10_1","volume-title":"CIDR","author":"Deshpande A.","year":"2005","unstructured":"A. Deshpande , C. Guestrin , and S. Madden . Using probabilistic models for data management in acquisitional environments . In CIDR , 2005 . A. Deshpande, C. Guestrin, and S. Madden. Using probabilistic models for data management in acquisitional environments. In CIDR, 2005."},{"key":"e_1_2_1_11_1","volume-title":"VLDB","author":"Dong Xin Luna","year":"2007","unstructured":"Xin Luna Dong , Alon Y. Halevy , and Cong Yu . Data integration with uncertainty . In VLDB , 2007 . Xin Luna Dong, Alon Y. Halevy, and Cong Yu. Data integration with uncertainty. In VLDB, 2007."},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/371920.372165"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.5555\/644108.644113"},{"key":"e_1_2_1_14_1","first-page":"360","volume-title":"UAI","author":"Finn Jensen","year":"1994","unstructured":"Jensen Finn and Jensen Frank . Optimal junction trees . In UAI , pages 360 -- 366 , 1994 . Jensen Finn and Jensen Frank. Optimal junction trees. In UAI, pages 360--366, 1994."},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/239041.239045"},{"key":"e_1_2_1_16_1","volume-title":"IEEE Data Engineering Bulletin Special Issue on Probabilistic Data Management","author":"Garofalakis Minos","year":"2006","unstructured":"Minos Garofalakis and Dan Suciu , editors. IEEE Data Engineering Bulletin Special Issue on Probabilistic Data Management . March 2006 . Minos Garofalakis and Dan Suciu, editors. IEEE Data Engineering Bulletin Special Issue on Probabilistic Data Management. March 2006."},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/1265530.1265535"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1007\/11896548_24"},{"key":"e_1_2_1_19_1","volume-title":"VLDB","author":"Gupta R.","year":"2006","unstructured":"R. Gupta and S. Sarawagi . Creating probabilistic databases from information extraction models . In VLDB , 2006 . R. Gupta and S. Sarawagi. Creating probabilistic databases from information extraction models. In VLDB, 2006."},{"key":"e_1_2_1_20_1","first-page":"83","volume-title":"ICML-98 Workshop: Text Categorization and Machine Learning","author":"Herbrich R.","year":"1998","unstructured":"R. Herbrich , T. Graepel , P. Bollmann-Sdorra , and K. Obermayer . Learning preference relations for information retrieval . In ICML-98 Workshop: Text Categorization and Machine Learning , page 83 -- 86 , 1998 . R. Herbrich, T. Graepel, P. Bollmann-Sdorra, and K. Obermayer. Learning preference relations for information retrieval. In ICML-98 Workshop: Text Categorization and Machine Learning, page 83--86, 1998."},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/1376616.1376685"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/1391729.1391730"},{"key":"e_1_2_1_23_1","volume-title":"Avatar information extraction system","author":"Jayram T. S.","year":"2006","unstructured":"T. S. Jayram , R. Krishnamurthy , S. Raghavan , S. Vaithyanathan , and H. Zhu . Avatar information extraction system . IEEE Data Eng. Bull ., 29(1), 2006 . T. S. Jayram, R. Krishnamurthy, S. Raghavan, S. Vaithyanathan, and H. Zhu. Avatar information extraction system. IEEE Data Eng. Bull., 29(1), 2006."},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1109\/59.49090"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.14778\/1453856.1453892"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/775047.775067"},{"key":"e_1_2_1_27_1","volume-title":"MayBMS: A System for Managing Large Uncertain and Probabilistic Databases","author":"Koch C.","year":"2009","unstructured":"C. Koch . MayBMS: A System for Managing Large Uncertain and Probabilistic Databases . Chapter in Managing and Mining Uncertain Data, C. Aggarwal ed., Springer , 2009 . C. Koch. MayBMS: A System for Managing Large Uncertain and Probabilistic Databases. Chapter in Managing and Mining Uncertain Data, C. Aggarwal ed., Springer, 2009."},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.14778\/1453856.1453894"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1145\/261124.261131"},{"key":"e_1_2_1_30_1","volume-title":"A unified approach to ranking in probabilistic databases. CoRR, abs\/0904.1366","author":"Li J.","year":"2009","unstructured":"J. Li , B. Saha , and A. Deshpande . A unified approach to ranking in probabilistic databases. CoRR, abs\/0904.1366 , 2009 . J. Li, B. Saha, and A. Deshpande. A unified approach to ranking in probabilistic databases. CoRR, abs\/0904.1366, 2009."},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/1559795.1559835"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2007.367934"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2006.174"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-009-0153-2"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2007.367935"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.14778\/1453856.1453941"},{"key":"e_1_2_1_37_1","volume-title":"CIDR","author":"Widom J.","year":"2005","unstructured":"J. Widom . Trio : A system for integrated management of data, accuracy, and lineage . In CIDR , 2005 . J. Widom. Trio: A system for integrated management of data, accuracy, and lineage. In CIDR, 2005."},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2008.4497571"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDEW.2008.4498380"}],"container-title":["Proceedings of the VLDB Endowment"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.14778\/1687627.1687685","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,12,28]],"date-time":"2022-12-28T11:29:04Z","timestamp":1672226944000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.14778\/1687627.1687685"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2009,8]]},"references-count":39,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2009,8]]}},"alternative-id":["10.14778\/1687627.1687685"],"URL":"https:\/\/doi.org\/10.14778\/1687627.1687685","relation":{},"ISSN":["2150-8097"],"issn-type":[{"value":"2150-8097","type":"print"}],"subject":[],"published":{"date-parts":[[2009,8]]}}}