Industry-scale duplicate detection

Melanie Weis, Felix Naumann, Ulrich Jehle, Jens Lufter, Holger SchusterPVLDB 2008 · OpenReview

TL;DR

This paper tackles the challenge of identifying duplicate records in massive relational databases, a critical task for data quality and business operations. The authors successfully adapt and extend a previously developed XML duplicate detection framework (DogmatiX) to a large-scale industrial setting, achieving high effectiveness and scalability.

What Problem Does This Paper Address?

Duplicate detection, the process of identifying multiple representations of the same real-world object within a dataset, is crucial for numerous applications like customer relationship management and data mining. However, it's a complex problem for several reasons:

  • Data Variability: Duplicates are rarely exact matches; they often contain variations due to misspellings, outdated information, or missing fields. This makes simple exact matching ineffective.
  • Scalability: Comparing every possible pair of records in a massive database (like Schufa's 64 million individuals) is computationally prohibitive, requiring billions of comparisons.
  • Domain Specificity: Effective duplicate detection often requires incorporating domain knowledge, which can be challenging to integrate into generic algorithms.

The paper specifically addresses the need for industry-scale batch duplicate detection at Schufa Holding AG, a German credit bureau, where identifying duplicates is vital for both individual creditworthiness and preventing fraudulent identity creation.

Methods

The core of the solution involves extending the DogmatiX framework, originally designed for XML, to a relational database context. Key methodological contributions include:

  • Description Selection: Instead of using all available attributes, the authors employ a multi-stage process to select only the most informative "descriptions" for identifying duplicates. This involves:
  • Schema-based heuristics: Adapting XML schema-based rules to relational schemas, focusing on attribute proximity and data types.
  • Instance-based heuristics: Analyzing attribute value distributions and using Inverse Document Frequency (IDF) to identify attributes that best discriminate records.
  • Domain Knowledge Integration: Incorporating expert knowledge to refine the selected descriptions (e.g., including gender for person matching).
  • Comparison Profile: A sophisticated classifier is developed, comprising a sequence of "base classifiers." These include:
  • Negative Classifiers: Rules that definitively identify pairs as non-duplicates based on domain knowledge (e.g., different genders). This significantly prunes the search space.
  • Positive Classifiers: Rules that identify pairs as duplicates based on specific patterns (e.g., matching names and address changes).
  • Similarity-Based Classifiers: Employing a modified DogmatiX similarity measure that considers data similarity, data relevance, and how to handle contradictory vs. missing data.
  • Scalability with Sorted Neighborhood Method (SNM): To address the computational challenge, the authors adapt the SNM. Crucially, they develop novel key definitions for SNM that are derived from the comparison profile. This ensures that records likely to be duplicates are sorted close to each other, minimizing the number of pairwise comparisons needed within a sliding window. They also explore two SNM strategies: rule-based and profile-based.

Datasets

  • Dsmall: A dataset of 100,000 randomly selected persons from Schufa, with all duplicate pairs manually identified. This dataset was used for evaluating the effectiveness of different classifier combinations.
  • DLarge: A larger dataset of 10,000,000 randomly selected persons from Schufa. This dataset was used for evaluating the standard profile and scalability.

The paper does not introduce a new benchmark dataset but uses real-world data from Schufa.

Key Insights and Ideas

  • Domain Knowledge is King (and Queen): Integrating expert knowledge, even for seemingly simple attributes like gender, significantly improves the accuracy of duplicate detection by allowing for definitive non-duplicate classifications.
  • Pruning is Paramount: The effectiveness of duplicate detection hinges not just on finding matches but also on efficiently discarding non-matches. Negative classifiers and smart key definitions for SNM are crucial for this.
  • The Power of a Profile: A well-structured comparison profile, combining negative, positive, and similarity-based classifiers in a specific order, can achieve much higher effectiveness than a single similarity measure alone.
  • SNM Keys Matter: The effectiveness of SNM is highly dependent on the key used for sorting. Deriving these keys directly from the classification rules of the comparison profile is a novel approach that bridges effectiveness and scalability.
  • Rule-Based SNM Strategy Wins: For their specific scenario, the rule-based SNM strategy (applying only relevant classifiers per key) proved more efficient than the profile-based strategy without sacrificing significant effectiveness.

Key Results

  • Effectiveness: The final "standard profile" achieved a maximum f-measure of 86% on the Dsmall dataset. On the larger DLarge dataset, it reached 90% precision at 53% recall for time-critical scenarios, and up to 85% recall with more processing time.
  • Scalability: The SNM approach dramatically improved runtime. Processing 10 million persons took approximately 2.5 hours with SNM, compared to an estimated 300 days for a naive pairwise comparison. The comparison phase scales linearly with the number of candidates (O(N)).
  • Runtime Improvement: The rule-based SNM strategy was consistently faster than the profile-based strategy, with processing 10 million persons taking about 15 hours on an off-the-shelf PC.

Limitations and Future Work

  • Limitations:
    • The paper acknowledges that SNM, while efficient, can potentially miss some duplicates due to its windowing mechanism.
  • The effectiveness on DLarge was slightly lower than on Dsmall, partly attributed to the SNM's inherent limitations and the fact that not all duplicates were known in DLarge.
  • The exact matching between keys and classifiers is confidential.
  • Future Work:
    • Investigate variable window sizes for SNM to further mitigate missed duplicates.
  • Develop specialized profiles that classify duplicate pairs based on the reason for their duplication (e.g., address change vs. name change), enabling more automated post-processing.
  • Explore learning similarity measure parameters and classifier rules more dynamically.

Summary updated

BibTeX
@article{weis2008industry,
  author = {Melanie Weis and Felix Naumann and Ulrich Jehle and Jens Lufter and Holger Schuster},
  title = {{Industry-scale duplicate detection}},
  journal = {Proc. VLDB Endow.},
  year = {2008},
  url = {https://openreview.net/forum?id=Ql-ecvuhi9},
}

Loading related content...

Figure