Cleaning Uncertain Data with Quality Guarantees

Summary: Proposes PWS-quality, an ambiguity metric for probabilistic databases under possible-world semantics. Develops polynomial-time optimal cleaning to maximize PWS-quality by probing uncertain objects; efficient evaluation for independent and ranking queries, with practical heuristics. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: h02aefb5d46935252
Venue: VLDB
Year: 2008
Pagerank: 6.2400289e-05
Overall Rank: 5,176 | 65.22%
DOI: 10.14778/1454159.1454164

Incoming Non-self Citations Over Time

Authors

1. Reynold Cheng (Hong Kong Polytechnic University)
2. Jinchuan Chen (Hong Kong Polytechnic University)
3. Xike Xie (Hong Kong Polytechnic University)

BibTeX Citation

@article{cheng_vldb08,
        title = {{Cleaning Uncertain Data with Quality Guarantees}},
        author = {Cheng, Reynold and Chen, Jinchuan and Xie, Xike},
        journal = {PVLDB},
        series = {{VLDB} '08},
        volume = {1},
        number = {2},
        pages = {722--733},
        doi = {10.14778/1454159.1454164},
        url = {https://doi.org/10.14778/1454159.1454164},
        year = {2008}
}

Incoming Citations (Sorted by Pagerank)

Showing 8 of 8 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
1,615	Sensitivity Analysis and Explanations for Robust Query Evaluation in Probabilistic Databases	2011	SIGMOD	0.00010062545
2,719	Partial Results in Database Systems	2014	SIGMOD	8.0942034e-05
5,805	Top-K Deep Video Analytics: A Probabilistic Approach	2021	SIGMOD	5.9861675e-05
6,975	Explore or Exploit? Effective Strategies for Disambiguating Large Databases	2010	VLDB	5.6277347e-05
9,382	Query-Guided Resolution in Uncertain Databases	2023	SIGMOD	5.1843659e-05
9,393	Selecting Data to Clean for Fact Checking: Minimizing Uncertainty vs. Maximizing Surprise	2019	VLDB	5.1843659e-05
10,859	Noisy Interactive Graph Search: An Uncertainty-Based Approach with Online Modeling of Latent Expertise and Difficulty	2026	VLDB	4.9769913e-05
11,705	LinCQA: Faster Consistent Query Answering with Linear Time Guarantees	2023	SIGMOD	4.9769913e-05

Outgoing Citations (Sorted by Pagerank)

Showing 12 of 12 cited papers.

Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.

Rank	Cited Paper	Year	Venue	Pagerank
51	Efficient Query Evaluation on Probabilistic Databases	2004	VLDB	0.00042926566
84	ULDBs: Databases with Uncertainty and Lineage	2006	VLDB	0.00035960573
337	Trio: A System for Data, Uncertainty, and Lineage	2006	VLDB	0.00020613834
343	Model-Driven Data Acquisition in Sensor Networks	2004	VLDB	0.00020510274
370	Evaluating Probabilistic Queries over Imprecise Data	2003	SIGMOD	0.00019837998
660	The Complexity of Query Reliability	1998	PODS	0.00015045167
735	Adaptive Filters for Continuous Queries over Distributed Data Streams	2003	SIGMOD	0.00014367765
1,125	Probabilistic Skylines on Uncertain Data	2007	VLDB	0.00011921893
1,518	Indexing Multi-Dimensional Uncertain Data with Arbitrary Probability Density Functions	2005	VLDB	0.0001039208
2,105	Efficient Indexing Methods for Probabilistic Threshold Queries over Uncertain Data	2004	VLDB	9.0323688e-05
2,133	The reliability of queries (Extended Abstract)	1995	PODS	8.9917097e-05
3,193	Monochromatic and Bichromatic Reverse Skyline Search over Uncertain Databases	2008	SIGMOD	7.5476762e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	4,657	A Temporal-Probabilistic Database Model for Information Extraction	2013	VLDB
2	1,865	A Probabilistic Framework for Vague Queries and Imprecise Information in Databases	1990	VLDB
3	51	Efficient Query Evaluation on Probabilistic Databases	2004	VLDB
4	4,215	Approximating Predicates and Expressive Queries on Probabilistic Databases	2008	PODS
5	1,615	Sensitivity Analysis and Explanations for Robust Query Evaluation in Probabilistic Databases	2011	SIGMOD
6	8,435	Efficient Uncertainty Tracking for Complex Queries with Attribute-level Bounds	2021	SIGMOD
7	12,867	Query Answering Techniques on Uncertain and Probabilistic Data	2008	SIGMOD
8	9,382	Query-Guided Resolution in Uncertain Databases	2023	SIGMOD
9	5,781	Consistent Query Answers in Inconsistent Probabilistic Databases	2010	SIGMOD
10	370	Evaluating Probabilistic Queries over Imprecise Data	2003	SIGMOD