Cleaning uncertain data with quality guarantees
Authors:
Open Access
- 1 August 2008
- journal article
- research article
- Published by Association for Computing Machinery (ACM) in Proceedings of the VLDB Endowment
- Vol. 1 (1) , 722-735
Abstract
Uncertain or imprecise data are pervasive in applications like location-based services, sensor monitoring, and data collection and integration. For these applications, probabilistic databases 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 PWS-quality metric, which is a universal measure that quantifies the ambiguity of query answers under the possible world semantics. 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.Keywords
This publication has 19 references indexed in Scilit:
- Monochromatic and bichromatic reverse skyline search over uncertain databases2008
- Probabilistic Verifiers: Evaluating Constrained Nearest-Neighbor Queries over Uncertain Data2008
- Quality-Aware Probing of Uncertain Data with Resource ConstraintsLecture Notes in Computer Science, 2007
- Towards correcting input data errors probabilistically using integrity constraints2006
- Cost-efficient processing of MIN/MAX queries over distributed sensors with uncertainty2005
- Adaptive filters for continuous queries over distributed data streams2003
- Evaluating probabilistic queries over imprecise data2003
- The complexity of query reliability1998
- Greed sortJournal of the ACM, 1995
- The management of probabilistic dataIEEE Transactions on Knowledge and Data Engineering, 1992