{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,1]],"date-time":"2025-11-01T07:14:18Z","timestamp":1761981258456,"version":"build-2065373602"},"reference-count":11,"publisher":"Association for Computing Machinery (ACM)","issue":"10","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. VLDB Endow."],"published-print":{"date-parts":[[2011,7]]},"abstract":"<jats:p>Top-k ranking for an uncertain database is to rank tuples in it so that the best k of them can be determined. The problem has been formalized under the unified approach based on parameterized ranking functions (PRFs) and the possible world semantics. Given a PRF, one can always compute the ranking function values of all the tuples to determine the top-k tuples, which is a formidable task for large databases. In this paper, we present a general approach to pruning for the framework based on PRFs. We show a mathematical manipulation of possible worlds which reveals key insights in the part of computation that may be pruned and how to achieve it in a systematic fashion. This leads to concrete pruning methods for a wide range of ranking functions. We show experimentally the effectiveness of our approach.<\/jats:p>","DOI":"10.14778\/2021017.2021018","type":"journal-article","created":{"date-parts":[[2014,6,24]],"date-time":"2014-06-24T12:17:57Z","timestamp":1403612277000},"page":"598-609","source":"Crossref","is-referenced-by-count":10,"title":["On pruning for top-k ranking in uncertain databases"],"prefix":"10.14778","volume":"4","author":[{"given":"Chonghai","family":"Wang","sequence":"first","affiliation":[{"name":"University of Alberta, Edmonton, Alberta, Canada"}]},{"given":"Li Yan","family":"Yuan","sequence":"additional","affiliation":[{"name":"University of Alberta, Edmonton, Alberta, Canada"}]},{"given":"Jia-Huai","family":"You","sequence":"additional","affiliation":[{"name":"University of Alberta, Edmonton, Alberta, Canada"}]},{"given":"Osmar R.","family":"Zaiane","sequence":"additional","affiliation":[{"name":"University of Alberta, Edmonton, Alberta, Canada"}]},{"given":"Jian","family":"Pei","sequence":"additional","affiliation":[{"name":"Simon Fraser University, Burnaby, BC Canada"}]}],"member":"320","published-online":{"date-parts":[[2011,7]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2009.75"},{"key":"e_1_2_1_2_1","first-page":"696","volume-title":"Proc. VLDB","author":"Fuhr N.","year":"1990","unstructured":"N. Fuhr . A probabilistic framework for vague queries and imprecise information in databases . In Proc. VLDB , pages 696 -- 707 , 1990 . N. Fuhr. A probabilistic framework for vague queries and imprecise information in databases. In Proc. VLDB, pages 696--707, 1990."},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/1066157.1066176"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/1376616.1376685"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/1634.1886"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/1559795.1559835"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-011-0220-3"},{"key":"e_1_2_1_8_1","first-page":"15","volume-title":"Proc. VLDB","author":"Pei J.","year":"2007","unstructured":"J. Pei , B. Jiang , X. Lin , and Y. Yuan . Probabilistic skylines on uncertain data . In Proc. VLDB , pages 15 -- 26 , 2007 . J. Pei, B. Jiang, X. Lin, and Y. Yuan. Probabilistic skylines on uncertain data. In Proc. VLDB, pages 15--26, 2007."},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2006.10"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2007.367935"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2008.90"}],"container-title":["Proceedings of the VLDB Endowment"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.14778\/2021017.2021018","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,12,28]],"date-time":"2022-12-28T09:42:51Z","timestamp":1672220571000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.14778\/2021017.2021018"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2011,7]]},"references-count":11,"journal-issue":{"issue":"10","published-print":{"date-parts":[[2011,7]]}},"alternative-id":["10.14778\/2021017.2021018"],"URL":"https:\/\/doi.org\/10.14778\/2021017.2021018","relation":{},"ISSN":["2150-8097"],"issn-type":[{"type":"print","value":"2150-8097"}],"subject":[],"published":{"date-parts":[[2011,7]]}}}