{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,25]],"date-time":"2026-02-25T17:00:52Z","timestamp":1772038852277,"version":"3.50.1"},"reference-count":36,"publisher":"Association for Computing Machinery (ACM)","issue":"1","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. VLDB Endow."],"published-print":{"date-parts":[[2008,8]]},"abstract":"<jats:p>\n            Uncertain or imprecise data are pervasive in applications like location-based services, sensor monitoring, and data collection and integration. For these applications,\n            <jats:italic>probabilistic databases<\/jats:italic>\n            can be used to store uncertain data, and querying facilities are provided to yield answers with statistical confidence. Given that a limited amount of resources is available to \"clean\" the database (e.g., by probing some sensor data values to get their latest values), we address the problem of choosing the set of uncertain objects to be cleaned, in order to achieve the best improvement in the quality of query answers. For this purpose, we present the\n            <jats:italic>PWS-quality<\/jats:italic>\n            metric, which is a universal measure that quantifies the ambiguity of query answers under the\n            <jats:italic>possible world semantics.<\/jats:italic>\n            We study how PWS-quality can be efficiently evaluated for two major query classes: (1) queries that examine the satisfiability of tuples independent of other tuples (e.g., range queries); and (2) queries that require the knowledge of the relative ranking of the tuples (e.g., MAX queries). We then propose a polynomial-time solution to achieve an optimal improvement in PWS-quality. Other fast heuristics are presented as well. Experiments, performed on both real and synthetic datasets, show that the PWS-quality metric can be evaluated quickly, and that our cleaning algorithm provides an optimal solution with high efficiency. To our best knowledge, this is the first work that develops a quality metric for a probabilistic database, and investigates how such a metric can be used for data cleaning purposes.\n          <\/jats:p>","DOI":"10.14778\/1453856.1453935","type":"journal-article","created":{"date-parts":[[2014,6,24]],"date-time":"2014-06-24T12:17:57Z","timestamp":1403612277000},"page":"722-735","source":"Crossref","is-referenced-by-count":60,"title":["Cleaning uncertain data with quality guarantees"],"prefix":"10.14778","volume":"1","author":[{"given":"Reynold","family":"Cheng","sequence":"first","affiliation":[{"name":"The Hong Kong Polytechnic University, Hung Hom, Kowloon, Hong Kong"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jinchuan","family":"Chen","sequence":"additional","affiliation":[{"name":"The Hong Kong Polytechnic University, Hung Hom, Kowloon, Hong Kong"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Xike","family":"Xie","sequence":"additional","affiliation":[{"name":"The Hong Kong Polytechnic University, Hung Hom, Kowloon, Hong Kong"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2008,8]]},"reference":[{"key":"e_1_2_1_1_1","volume-title":"VLDB","author":"Agrawal P.","year":"2006","unstructured":"P. Agrawal , O. Benjelloun , A. D. Sarma , C. Hayworth , S. Nabar , T. Sugihara , and J. Widom . Trio: A system for data, uncertainty, and lineage . In VLDB , 2006 . P. Agrawal, O. Benjelloun, A. D. Sarma, C. Hayworth, S. Nabar, T. Sugihara, and J. Widom. Trio: A system for data, uncertainty, and lineage. In VLDB, 2006."},{"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.1109\/69.166990"},{"key":"e_1_2_1_4_1","volume-title":"VLDB","author":"Benjelloun O.","year":"2006","unstructured":"O. Benjelloun , A. Sarma , A. Halevy , and J. Widom . ULDBs: Databases with uncertainty and lineage . In VLDB , 2006 . O. Benjelloun, A. Sarma, A. Halevy, and J. Widom. ULDBs: Databases with uncertainty and lineage. In VLDB, 2006."},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2006.159"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-69497-7_31"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2008.4497506"},{"key":"e_1_2_1_8_1","unstructured":"R. Cheng J. Chen and X. Xie. Cleaning uncertain data with quality guarantees (technical report). In http:\/\/www2.comp.polyu.edu.hk:8080\/~csjcchen\/quality.pdf.  R. Cheng J. Chen and X. Xie. Cleaning uncertain data with quality guarantees (technical report). In http:\/\/www2.comp.polyu.edu.hk:8080\/~csjcchen\/quality.pdf."},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/872757.872823"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.5555\/1316689.1316765"},{"key":"e_1_2_1_11_1","volume-title":"Introduction to Algorithms","author":"Cormen T.","year":"2001","unstructured":"T. Cormen , C. Leiserson , R. Rivest , and C. Stein . Introduction to Algorithms . The MIT Press , 2001 . T. Cormen, C. Leiserson, R. Rivest, and C. Stein. Introduction to Algorithms. The MIT Press, 2001."},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.5555\/1316689.1316764"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/212433.212479"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.5555\/1316689.1316741"},{"key":"e_1_2_1_15_1","volume-title":"The average behaviour of greedy algorithms for the knapsack problem: general distributions. Mathematical Methods of Operations Research, 57(3)","author":"Diubin G.","year":"2003","unstructured":"G. Diubin . The average behaviour of greedy algorithms for the knapsack problem: general distributions. Mathematical Methods of Operations Research, 57(3) , 2003 . G. Diubin. The average behaviour of greedy algorithms for the knapsack problem: general distributions. Mathematical Methods of Operations Research, 57(3), 2003."},{"key":"e_1_2_1_16_1","volume-title":"SSDBM","author":"Pfoser D.","year":"1999","unstructured":"D. Pfoser and C. Jensen . Capturing the uncertainty of moving-objects representations . In SSDBM , 1999 . D. Pfoser and C. Jensen. Capturing the uncertainty of moving-objects representations. In SSDBM, 1999."},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/275487.295124"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/1140104.1140114"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.5555\/1783823.1783863"},{"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\/1066677.1066823"},{"key":"e_1_2_1_22_1","unstructured":"M. Hadjieleftheriou. Spatial index library 0.44.2b. http:\/\/u-foria.org\/marioh\/spatialindex\/index.html.  M. Hadjieleftheriou. Spatial index library 0.44.2b. http:\/\/u-foria.org\/marioh\/spatialindex\/index.html."},{"key":"e_1_2_1_23_1","unstructured":"A. moving rating database. http:\/\/infolab.stanford.edu\/trio\/code\/index.html#examples.  A. moving rating database. http:\/\/infolab.stanford.edu\/trio\/code\/index.html#examples."},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/210332.210343"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/872757.872825"},{"key":"e_1_2_1_26_1","volume-title":"VLDB","author":"Pei J.","year":"2007","unstructured":"J. Pei , B. Jiang , X. Lin , and Y. Yuan . Probabilistic skylines on uncertain data . In VLDB , 2007 . J. Pei, B. Jiang, X. Lin, and Y. Yuan. Probabilistic skylines on uncertain data. In VLDB, 2007."},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2007.367934"},{"key":"e_1_2_1_28_1","volume-title":"University of Illinois Press","author":"Shannon C.","year":"1949","unstructured":"C. Shannon . The Mathematical Theory of Communication . University of Illinois Press , 1949 . C. Shannon. The Mathematical Theory of Communication. University of Illinois Press, 1949."},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2006.10"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2007.367907"},{"key":"e_1_2_1_31_1","volume-title":"ICDE","year":"2008","unstructured":"Singh Database support for pdf attributes . In ICDE , 2008 . Singh et al. Database support for pdf attributes. In ICDE, 2008."},{"key":"e_1_2_1_32_1","volume-title":"Temporal Databases: Research and Practice","author":"Sistla P. A.","year":"1998","unstructured":"P. A. Sistla , O. Wolfson , S. Chamberlain , and S. Dao . Querying the uncertain position of moving objects . In Temporal Databases: Research and Practice . Springer Verlag , 1998 . P. A. Sistla, O. Wolfson, S. Chamberlain, and S. Dao. Querying the uncertain position of moving objects. In Temporal Databases: Research and Practice. Springer Verlag, 1998."},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2007.367935"},{"key":"e_1_2_1_34_1","volume-title":"VLDB","author":"Tao Y.","year":"2005","unstructured":"Y. Tao , R. Cheng , X. Xiao , W. K. Ngai , B. Kao , and S. Prabhakar . Indexing multi-dimensional uncertain data with arbitrary probability density functions . In VLDB , 2005 . Y. Tao, R. Cheng, X. Xiao, W. K. Ngai, B. Kao, and S. Prabhakar. Indexing multi-dimensional uncertain data with arbitrary probability density functions. In VLDB, 2005."},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1023\/A:1008782710752"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2008.4497571"}],"container-title":["Proceedings of the VLDB Endowment"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.14778\/1453856.1453935","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,12,28]],"date-time":"2022-12-28T11:08:58Z","timestamp":1672225738000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.14778\/1453856.1453935"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2008,8]]},"references-count":36,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2008,8]]}},"alternative-id":["10.14778\/1453856.1453935"],"URL":"https:\/\/doi.org\/10.14778\/1453856.1453935","relation":{},"ISSN":["2150-8097"],"issn-type":[{"value":"2150-8097","type":"print"}],"subject":[],"published":{"date-parts":[[2008,8]]}}}