Skip to content

Software Quality

Duplicate-record detection

Finding the records that describe the same person, organization or product although no key says so.

Duplicate-record detection finds the records in a table, or across two tables, that refer to the same real-world entity: one customer entered twice with a misspelled name, one patient registered at two clinics, one product listed by two shops. The records carry different keys and differ in their values, so a uniqueness assertion on the key passes them. The method compares the records' values instead and decides which pairs are the same entity. The same matching links two datasets that share no identifier, such as two systems being merged.

How matches are found

  • Blocking. Comparing every pair of records grows with the square of the table, so a blocking step chooses the candidate pairs: records with the same postcode, or each record's nearest neighbors by text similarity (Li et al. 2020)1. A pair the blocking step leaves out is never compared.
  • Comparing a pair. Each attribute is compared with a similarity function, such as edit distance on names or token overlap on addresses, and the scores are combined into one decision by a rule, a threshold, or a model.
  • Probabilistic linkage estimates from the data how strongly agreement on each field indicates a match, and so can estimate its own false-positive and false-negative rates (Enamorado et al. 2019)2.
  • Learned matchers train a classifier on pairs a person labeled as match or non-match. Deep-learning matchers help most where records are text-heavy or where values sit in the wrong fields (Mudgal et al. 2018)3.

The matched pairs are then grouped, so that three records of one customer become one cluster rather than three separate pairs.

What it catches

  • Repeated entry. The same person or organization created again with a spelling variant, a new address format or a missing field.
  • Records of one entity across sources. Customers present in both a billing and a support system, products listed by several suppliers.
  • Duplicates from reloads. A batch imported twice under newly generated keys.

It does not catch a wrong value: it decides whether two records describe the same entity, not whether either record is correct.

Tools

  • Splink — open-source Python library from Britain's Ministry of Justice for probabilistic record linkage, running on several SQL engines.
  • dedupe — Python library for fuzzy matching, deduplication and record linkage that learns from pairs a person labels.
  • Zingg — open-source entity resolution on Spark, trained from labeled pairs.
  • fastLink — R package for probabilistic record linkage that estimates its own error rates.

When to use, when not

Use:

  • Before counting entities: customers, patients, suppliers, products.
  • When merging the records of two systems that share no identifier.
  • On tables filled by hand or by several import paths.

Don't:

  • To merge automatically above a threshold without reviewing a sample of matches. A false merge joins two people's records, and it is harder to undo than a duplicate.
  • As a replacement for an identifier at the point of entry, where one can be assigned.

Evidence

  • Product matching is far harder than matching publications. In a comparison of more than 20 approaches, including a commercial system, nearly every non-learning approach reached an F-measure above 91% on a bibliographic task, while none exceeded 62% matching Amazon and Google products or 70% matching Abt and Buy products. Learned matchers trained on 500 labeled pairs reached about 60% and 71% (Köpcke et al. 2010)4.
  • Deep learning helps with text and messy records, not clean ones. Against Magellan, a learning-based matcher, deep-learning matchers did not do better on structured records but improved F1 by 3.0–22.0% on textual records and by 6.2–32.6% on dirty ones (Mudgal et al. 2018)3.
  • Probabilistic linkage beats exact matching. Across 270 simulation settings, probabilistic linkage outperformed exact and partial deterministic matching, and in a merge of voter files across states its estimated false discovery rate was below 0.1% for every state (Enamorado et al. 2019)2.
  • One learned matcher held up at company scale. Matching 789,000 internal employer records against 412,000 public ones, a matcher built on pre-trained language models reached 96.5% F1 on a holdout set (Li et al. 2020)1.

Classification

  • Data-quality characteristics: Consistency (two records of one entity that disagree contradict each other), Accuracy (an entity stored twice is counted twice in every report built on the table).
  • Area: Tables of people, organizations and products entered by hand or merged from several sources — customer and patient records, supplier lists, product catalogs, administrative registers.
  • Guarantee: Empirical — matches are as good as the similarity measure and the threshold; a pair the blocking step never compares is never found, and two distinct entities that look alike are merged.

Referenced by

References

  1. Li, Yuliang, Jinfeng Li, Yoshihiko Suhara, AnHai Doan, and Wang-Chiew Tan. 2020. "Deep Entity Matching with Pre-Trained Language Models." Proceedings of the VLDB Endowment 14 (1). https://doi.org/10.14778/3421424.3421431. ↩↩

  2. Enamorado, Ted, Benjamin Fifield, and Kosuke Imai. 2019. "Using a Probabilistic Model to Assist Merging of Large-Scale Administrative Records." American Political Science Review 113 (2). https://doi.org/10.1017/S0003055418000783. ↩↩

  3. Mudgal, Sidharth, Han Li, Theodoros Rekatsinas, et al. 2018. "Deep Learning for Entity Matching: A Design Space Exploration." Proceedings of the 2018 International Conference on Management of Data (SIGMOD 2018). https://doi.org/10.1145/3183713.3196926. ↩↩

  4. Köpcke, Hanna, Andreas Thor, and Erhard Rahm. 2010. "Evaluation of Entity Resolution Approaches on Real-World Match Problems." Proceedings of the VLDB Endowment 3 (1). https://doi.org/10.14778/1920841.1920904. ↩