A sample-and-clean framework for fast and accurate query processing on dirty data

By Jiannan Wang, Sanjay Krishnan, M. Franklin, Ken Goldberg, Tim Kraska, Tova Milo. 2014

127 citations recorded by the source corpus.

In emerging Big Data scenarios, obtaining timely, high-quality answers to aggregate queries is difficult due to the challenges of processing and cleaning large, dirty data sets. To increase the speed of query processing, there has been a resurgence of interest in sampling-based approximate query processing (SAQP). In its usual formulation, however, SAQP does not address data cleaning at all, and in fact, exacerbates answer quality problems by introducing sampling error. In this paper, we explore an intriguing opportunity. That is, we explore the use of sampling to actually improve answer quality. We introduce the Sample-and-Clean framework, which applies data cleaning to a relatively small subset of the data and uses the results of the cleaning process to lessen the impact of dirty data on aggregate query answers. We derive confidence intervals as a function of sample size and show how our approach addresses error bias. We evaluate the Sample-and-Clean framework using data from three sources: the TPC-H benchmark with synthetic noise, a subset of the Microsoft academic citation index and a sensor data set. Our results are consistent with the theoretical confidence intervals and suggest that the Sample-and-Clean framework can produce significant improvements in accuracy compared to query processing without data cleaning and speed compared to data cleaning without sampling.

Subfields: Artificial Intelligence, Management Science and Operations Research, Information Retrieval & Search, Signal Processing

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Management Science and Operations Research

In Information Retrieval & Search

In Signal Processing

Citations in the corpus

AlphaClean: Automatic Generation of Data Cleaning Pipelines (2019, background): “cleaning [4, 23, 28, 30, 41, 45] has revealed human-time — Machine Learning in Data Cleaning: Machine learning Application-Aware Cleaning: Semantics about the down-stream Generating Cleaning Programs: A composable data”
A Survey on Cleaning Dirty Data Using Machine Learning Paradigm for Big Data Analytics (2018, methodology): “Existing procedures involve jamming data for identical data detection [29], [30], identification and linkage for data cleaning [30], clean data using sampling [31], and distributed data cleaning [32].”
BoostClean: Automated Error Detection and Repair for Machine Learning (2017, methodology): “Sensor: The Intel sensor dataset [4,49,50] contains 928,991 temperature, humidity, and light sensor readings a sensor deployment.”
ActiveClean: An Interactive Data Cleaning Framework For Modern Machine Learning (2016, methodology): “The selection technique applied in ActiveClean uses pointwise gradients to generalize the outlier filtering heuristics to select potentially dirty data even in complex models.”
Learning accurate kinematic control of cable-driven surgical robots using data cleaning and Gaussian Process Regression (2014, methodology): “Details of our specific data collection procedure can be found in Section V.”
Effective Data Cleaning with Continuous Evaluation (2016, methodology): “The scale challenge is often addressed using a variety of techniques including the use of sampling [17], approximate cleaning by partitioning the data into blocks as often done in data deduplication [3], and by adopting scale-out computing infrastructure such as Spark [19].”
PrivateClean: Data Cleaning and Differential Privacy (2016, background): “This is a tradeoff that has been highlighted before in the SampleClean project [23,44].”
Data Cleaning: Overview and Emerging Challenges (2016, methodology): “Current techniques include blocking for duplicate detection [5], sampling for data cleaning [75], and distributed data cleaning [47, 45, 20].”
A Data Quality Metric (DQM): How to Estimate the Number of Undetected Errors in Data Sets (2016, methodology): “Similarly, sampling is now a widely studied in the context of data cleaning [33, 18].”
SampleClean: Fast and Reliable Analytics on Dirty Data (2015, methodology): “In this article, we highlight three projects: SampleClean [45] 1 : SampleClean estimates aggregate ( sum , count , avg ) queries using samples of clean data.”
QuERy: A Framework for Integrating Entity Resolution with Query Processing (2015, background): “Recent work on analysis-aware data cleaning seeks to overcome the limitations of traditional oﬄine data cleaning techniques [4,8,17,22,24].”
Wisteria: Nurturing Scalable Data Cleaning Infrastructure (2015, methodology): “• Crowd Latency: We leverage techniques for straggler mitigation [14] and model crowd worker speed and accuracy to reduce the (often rate-limiting) latency of crowd data cleaning, consistently retrieving results in seconds rather than hours.”
A Survey of Research on Cloud Robotics and Automation (2015, background): “New approaches are required that are robust to dirty data.”
Trends in Cleaning Relational Data: Consistency and Deduplication (2015, methodology): “SampleClean [115] applies data cleaning to a relatively small sample of the data and uses the cleaned sample for answering queries.”
ActiveClean: Interactive Data Cleaning For Statistical Modeling (2016, methodology): “This approach is similar to SampleClean [33], which was proposed to approximate the results of aggregate queries by applying them to a clean sample of data.”
ActiveClean: Interactive Data Cleaning While Learning Convex Loss Models (2016, methodology): “SampleClean [33] applies data cleaning to a sample of data, and estimates the results of aggregate queries.”
Crowdsourced Data Management: A Survey (2016, background): “Crowdsourcing can also benefit data management applications , such as data cleaning [93], [119], data integration [58], [73], [127], knowledge construction [9], [12].”
Query-Oriented Data Cleaning with Oracles (2015, background): “In the context of data cleaning [62] introduced the idea of cleaning only a sample of data to obtain unbiased query results with conﬁdence intervals.”