Integrating Conflicting Data: The Role of Source Dependence

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

TL;DR

This paper tackles the challenge of integrating data from multiple sources, where conflicts are common due to copying and errors. They introduce a novel approach that explicitly models source dependence (i.e., one source copying from another) to improve truth discovery, going beyond simple majority voting. Their method significantly enhances accuracy by understanding these relationships and also incorporates source accuracy for even better results.

What Problem Does This Paper Address?

In today's data-rich world, we often need to combine information from various sources, like websites, databases, or APIs. A major hurdle is that these sources can provide conflicting information – some true, some false. A common approach to resolve these conflicts is "majority voting," assuming the most frequent value is the true one. However, this breaks down when sources copy from each other. A false value, if copied by many, can appear to be the majority truth. This paper addresses the critical problem of how to accurately determine the "true" value from a large number of potentially dependent and error-prone data sources, especially when copying is prevalent.

Methods

The core of the paper's contribution lies in its novel approach to truth discovery by modeling source dependence.

  • DEPEN Model: This model uses Bayesian analysis to compute the probability that two data sources are dependent. The intuition is that if two sources share many false values, they are more likely to be copying from each other, as sharing true values is less indicative of dependence. This allows the system to identify potential copiers.
  • Vote Counting: Instead of simply ignoring suspected copiers, the paper proposes methods to count their votes more intelligently. The "ideal vote count" considers the probability of copying, and an "estimated vote count" provides a scalable approximation.
  • ACCU Model: This model extends DEPEN by incorporating the accuracy of data sources. It learns source accuracy by analyzing the confidence of values they provide and uses this to refine dependence probabilities and vote counts. This means more accurate sources get a higher say.
  • Iterative Refinement: The models operate iteratively. They first estimate dependence and accuracy, then use these estimates to discover true values, and then refine the estimates based on the discovered truths. This process continues until convergence.
  • Extensions: The paper also discusses extensions to handle non-uniform distributions of false values (NonUni) and similarity between values (SIM), further enhancing robustness.

Datasets

The paper evaluates its methods on:

  • Synthetic Data: Generated across various "universes" (Indep-source, Copier, Pareto) with controlled parameters like error rates, number of sources, and copying behavior. This allows for systematic testing of assumptions and robustness.
  • Real-World Data: A dataset of computer-science books from AbeBooks.com, where the task is to determine the correct list of authors for each book from multiple bookstore listings. This dataset was also used in prior work for comparison.

Key Insights and Ideas

  • Copying is Key: The most significant insight is that simply counting votes is insufficient when copying occurs. Understanding who copies from whom is crucial for accurate truth discovery.
  • False Values as Dependence Signals: Sharing false values is a stronger indicator of dependence than sharing true values. This is a counter-intuitive but powerful observation.
  • Accuracy and Dependence are Intertwined: Source accuracy influences dependence, and dependence influences how we assess accuracy. The ACCU model elegantly captures this feedback loop.
  • Robustness to Assumptions: The proposed models show remarkable robustness to violations of their assumptions (e.g., indirect copying, parameter variations), making them practical for real-world scenarios.
  • Preventing Falsification: The models can effectively prevent malicious actors from manipulating truth discovery, especially against "innocent" or "knowledgeable" falsifiers.

Key Results

  • Significant Accuracy Improvement: The ACCU model, which considers both dependence and accuracy, achieved the highest precision on both synthetic and real-world datasets, outperforming naive voting and other baseline methods. For instance, on the book data, ACCU achieved 87% precision, compared to 71% for naive voting.
  • Scalability: The algorithms are designed to be scalable, with vote-count estimation taking O(s² log s) time, where 's' is the number of sources.
  • Effective Dependence Detection: The DEPEN model successfully identified dependencies, leading to improved results, especially in scenarios with significant copying.
  • Real-World Performance: On the book data, ACCU and SIM models achieved the highest precision, demonstrating the practical utility of considering source accuracy and value similarity.
  • Robustness Demonstrated: Experiments showed that the models perform well even with variations in parameters and indirect copying, and can prevent falsification in most cases.

Limitations and Future Work

  • Convergence Guarantees: While the VOTE algorithm is proven to converge, the ACCUVOTE algorithm's convergence is not strictly guaranteed in all cases, though experimental results show it typically converges soon. The paper notes that the precise condition for convergence remains an open problem.
  • Dynamic Data: The current models focus on a snapshot of data. Future work includes extending these models to handle evolving true values and data in dynamic environments.
  • Record Linkage Integration: Combining record linkage techniques with truth discovery is suggested as a promising direction to enhance both processes.
  • Query Answering Efficiency: Leveraging the discovered source dependencies to answer queries more efficiently in data integration systems is another area for future exploration.

Summary updated

BibTeX
@article{dong2009integrating,
  author = {Xin Luna Dong and Laure Berti-Équille and Divesh Srivastava},
  title = {{Integrating Conflicting Data: The Role of Source Dependence}},
  journal = {Proc. VLDB Endow.},
  year = {2009},
  doi = {10.14778/1687627.1687690},
}
Figure