Truth Discovery and Copying Detection in a Dynamic World

Xin Luna Dong, Laure Berti-Équille, Divesh SrivastavaPVLDB 2009 · DOI · OpenReview

TL;DR

This paper tackles the challenge of integrating data from multiple sources that may be outdated, contain errors, and even copy from each other, especially in dynamic environments where real-world information changes frequently. The authors introduce novel probabilistic models to simultaneously discover the true values of data items over time and identify which data sources copy from others, and when.

What Problem Does This Paper Address?

In today's data-driven world, information is often gathered from a multitude of sources. These sources can range from official databases to web crawls and user-generated content. A significant challenge arises when these sources provide conflicting or outdated information, especially in dynamic domains like contact information or business listings that change frequently. Furthermore, some sources might directly copy data from others, potentially propagating errors and staleness. Traditional data integration methods, like simple voting, struggle to handle these complexities. This paper addresses the critical need to accurately determine the "truth" from such a heterogeneous and dynamic data landscape, specifically by accounting for both the evolving quality of data sources and the often-hidden relationships of data copying between them.

Methods

The paper proposes a two-pronged probabilistic approach:

  • Copying Detection: A Hidden Markov Model (HMM) is employed to model the relationship between pairs of data sources. The HMM's hidden states represent whether one source is copying from another, and its observations are the updates made by the sources. The model is designed to capture not just whether copying occurs, but also when it happens, and to distinguish copying from simple slow updates by considering source quality metrics. A "timespan HMM" is also introduced to model periodic copying.
  • Truth Discovery (Life Span Discovery): A Bayesian model is developed to determine the true value of a data item over time. This model considers the quality of each source (measured by coverage, exactness, and freshness – collectively the CEF-measure) and the discovered copying relationships. It iteratively decides the true value and the timing of transitions (changes) in that value, accounting for both independent source updates and copied data. The model also handles delayed publishing, where sources don't immediately release their updates.

Datasets

  • Real-world data: Data on Manhattan restaurants was collected weekly from 12 web sources over two months. This dataset was used to evaluate the models' ability to discover restaurant existence periods and copying relationships.
  • Synthetic data: Datasets were generated to systematically test the models under various conditions, including different numbers of sources, copier types (independent, copier, random), object lifespans (single-period, multi-period), and publishing behaviors (instant, delayed). This allowed for controlled evaluation of model robustness and performance.

Key Insights and Ideas

  • CEF-Measure is Crucial: The paper emphasizes that source quality isn't a single metric. Coverage (what data is included), exactness (how accurate it is), and freshness (how up-to-date it is) are orthogonal and all vital for accurate truth discovery.
  • Copying is a Hidden State: Identifying data copying is framed as a hidden state problem, best modeled by HMMs that can infer these relationships from observed update patterns.
  • Dynamic Truth: The "truth" isn't static. The paper models the "life span" of data items, recognizing that values change over time, and the goal is to reconstruct this historical evolution.
  • Copying vs. Slow Updates: A key challenge is distinguishing a source that copies from another versus one that is simply slow to update. The models explicitly use source quality metrics to make this distinction.
  • Delayed Publishing Matters: Real-world data often has delays in publication. The models are extended to account for this, showing significant improvements when delays are present.

Key Results

  • High Accuracy: The proposed models (particularly COPYCEF and CEFDELAY) demonstrated high accuracy in both life-span discovery and copying detection on both real-world and synthetic datasets. For instance, on the restaurant data, COPYCEF achieved high precision and recall.
  • Robustness: The models showed robustness to variations in source quality and copying patterns. For example, COPYCEF was relatively insensitive to the quality of the source being copied.
  • Improved Performance: Compared to simpler methods like voting (NAIVE) or considering only snapshots (CURR, INIT), the proposed probabilistic models significantly improved accuracy.
  • Copying Detection Effectiveness: The HMM-based copying detection achieved high accuracy, especially in distinguishing between independent sources and copier-source pairs.
  • Delayed Publishing Benefits: CEFDELAY significantly improved results in the presence of delayed publishing, outperforming models that assumed instant updates.

Limitations and Future Work

  • Algorithm Convergence: The paper notes that the convergence of the main algorithm (LIFESPAN) is an open problem, although it was observed to converge quickly in experiments.
  • Update Correlation: The models currently assume independence of updates within a source, which might not always hold in reality.
  • Transitive Inference of Loops: The copying detection might struggle with complex cyclic copying relationships among multiple sources.
  • Future Work: The authors suggest applying these techniques to applications like identifying trustworthy sources or users in Web 2.0 environments and optimizing query answering in data integration systems by leveraging source quality and dependency knowledge.

Summary updated

BibTeX
@article{dong2009truth,
  author = {Xin Luna Dong and Laure Berti-Équille and Divesh Srivastava},
  title = {{Truth Discovery and Copying Detection in a Dynamic World}},
  journal = {Proc. VLDB Endow.},
  year = {2009},
  doi = {10.14778/1687627.1687691},
}
Figure