Duplicate Record Detection: A Survey

Ahmed K. ElmagarmidPanagiotis G. IpeirotisVassilios S. Verykios

article2007TKDE2,264 citations

Synthesizes decades of research on duplicate record detection by systematically analyzing field-level similarity metrics, multi-attribute matching algorithms, scalability methods, and practical data cleaning tools.

Listen

Modern operational environments and business systems rely heavily on high-quality database information, yet data quality is frequently degraded by human error, inconsistent conventions, and the lack of universal identifiers across disparate systems. When consolidating records, organizations face substantial costs and operational risks if multiple, non-identical entries referring to the same real-world entity are left unresolved. This article presents an extensive survey of the duplicate record detection literature, evaluating how organizations can systematically identify, match, and merge approximate duplicate records across structured database environments.

The article synthesizes decades of foundational research across database management, artificial intelligence, and statistics to compare field-matching metrics, multi-field record matching algorithms, and computational scaling techniques. By reviewing the evolution from classical probabilistic record linkage to advanced machine learning and relational database indexing, the article maps how different methodological paradigms balance matching accuracy against execution speed.

The findings establish that duplicate record detection requires a structured pipeline starting with essential data preparation—including parsing, transformation, and standardization—which resolves surface-level structural variations before record comparison begins. For field-level comparisons, character-based metrics excel at catching typographical mistakes, token-based approaches best handle word rearrangements, and phonetic encodings mitigate pronunciation-based errors, with hybrid token-frequency metrics demonstrating superior overall performance. For multi-field matching, probabilistic and supervised machine learning models achieve the highest matching accuracy, though they depend heavily on labeled training data or manual clerical reviews for ambiguous edge cases. In contrast, ad hoc database methods and distance-based heuristics run significantly faster and scale to millions of records, but sacrifice matching precision. Finally, computational bottlenecks are effectively mitigated through efficiency techniques such as blocking, sorted neighborhood sliding windows, and canopy clustering, which prevent exhaustive pairwise record comparisons.

These insights demonstrate that no single algorithm or distance metric provides an optimal solution across all data environments. High-accuracy statistical and probabilistic models remain computationally prohibitive for massive datasets, while simple rule-based and distance metrics risk accumulating errors if deployed without careful domain adaptation. The persistence of duplicate records degrades analytical reporting, increases operating costs, and can cause systemic failures across customer relationship management, healthcare record linkage, and enterprise compliance.

Organizations addressing data deduplication should deploy a multi-stage approach: first standardize and clean incoming data, apply computationally light filtering methods like canopies or blocking to narrow candidate pairs, and then deploy domain-adapted matching algorithms for detailed evaluation. Active learning tools should be leveraged to minimize the expensive manual effort required to label training data. Future strategic efforts must prioritize the development of standardized, large-scale benchmark datasets to rigorously compare matching models and the creation of adaptive, continuous monitoring pipelines capable of handling noisy data extracted from web and text sources.

While the article provides high confidence in its comparative architectural findings, it notes clear limitations: existing evaluations largely depend on small, proprietary, or domain-specific datasets, and current duplicate detection techniques for non-textual numeric fields remain primitive. Decision-makers should validate candidate deduplication pipelines on representative organizational data before full-scale deployment.

New York University Purdue University University of Thessaly database systems detection algorithm duplicate record detection record linkage system data deduplication

Elmagarmid et al (2007).pdf

Paper: Winnowing: local algorithms for document fingerprinting, S. Schleimer et al. (2003). Read this earlier fingerprinting method first to understand the local-hash techniques and detection guarantees that inform approaches to finding duplicate text.

Paper: Deduplicating Training Data Makes Language Models Better, Katherine Lee et al. (2022). This study carries deduplication into large-scale language-model training, testing scalable exact and approximate matching methods and measuring their effects on model quality and memorization.
Paper: The RefinedWeb Dataset for Falcon LLM: Outperforming Curated Corpora with Web Data Only, Guilherme Penedo et al. (2023). This work extends deduplication to a web-scale training-data pipeline, combining exact and fuzzy matching with other cleaning stages and testing the resulting corpus through language-model training.
Paper: DataComp-LM: In search of the next generation of training sets for language models, Jeffrey Li et al. (2024). This benchmark continues the study of scalable dataset curation by isolating deduplication alongside extraction, filtering, and data mixing in controlled language-model experiments.
Paper: Deduplicating Training Data Mitigates Privacy Risks in Language Models, Nikhil Kandpal et al. (2022). This study applies sequence-level deduplication to a consequential downstream problem, measuring how removing repeated training data changes privacy leakage from language models.

Cover for Duplicate Record Detection: A Survey

Abstract

Often, in the real world, entities have two or more representations in databases. Duplicate records do not share a common key and/or they contain errors that make duplicate matching a difficult task. Errors are introduced as the result of transcription errors, incomplete information, lack of standard formats, or any combination of these factors. In this paper, we present a thorough analysis of the literature on duplicate record detection. We cover similarity metrics that are commonly used to detect similar field entries, and we present an extensive set of duplicate detection algorithms that can detect approximately duplicate records in a database. We also cover multiple techniques for improving the efficiency and scalability of approximate duplicate detection algorithms. We conclude with coverage of existing tools and with a brief discussion of the big open problems in the area.

Topics

database systems detection algorithm

Keywords

duplicate record detection record linkage system data deduplication entity resolution data reconciliation approximate string matching field matching string comparison techniques similarity metrics data cleaning

1 INTRODUCTION
2 DATA PREPARATION
3 FIELD MATCHING TECHNIQUES
3.1 Character-Based Similarity Metrics
3.1.1 Edit Distance
3.1.2 Affine Gap Distance
3.1.3 Smith-Waterman Distance
3.1.4 Jaro Distance Metric
3.1.5 Q -Grams
3.2 Token-Based Similarity Metrics
3.2.1 Atomic Strings
3.2.2 WHIRL
3.2.3 Q - Grams with tf.idf
3.3 Phonetic Similarity Metrics
3.3.1 Soundex
3.3.2 New York State Identification and Intelligence System (NYSIIS)
3.3.3 Oxford Name Compression Algorithm (ONCA)
3.3.4 Metaphone and Double Metaphone
3.4 Numeric Similarity Metrics
3.5 Concluding Remarks
4 DETECTING DUPLICATE RECORDS
4.1 Notation
4.2 Probabilistic Matching Models
4.2.1 The Bayes Decision Rule for Minimum Error
4.2.2 The Bayes Decision Rule for Minimum Cost
4.2.3 Decision with a Reject Region
4.3 Supervised and Semisupervised Learning
4.4 Active-Learning-Based Techniques
4.5 Distance-Based Techniques
4.6 Rule-Based Approaches
4.7 Unsupervised Learning
4.8 Concluding Remarks
5 IMPROVING THE EFFICIENCY OF DUPLICATE DETECTION
5.1 Reducing the Number of Record Comparisons
5.1.1 Blocking
5.1.2 Sorted Neighborhood Approach
5.1.3 Clustering and Canopies
5.1.4 Set Joins
5.2 Improving the Efficiency of Record Comparison
6 DUPLICATE DETECTION TOOLS
7 FUTURE DIRECTIONS AND CONCLUSIONS
ACKNOWLEDGMENTS
REFERENCES

Knowls

Knowl 1 — Formal Framework and Vector Representation for Duplicate Record Detection
definition
In duplicate record detection (also termed record linkage, entity resolution, or data deduplication), two database tables $A$ and $B$ possessing $n$ comparable fields are evaluated. Each candidate tuple pair $\langle \alpha, \beta \rangle \in A \times B$ belongs to one of two mutually exclusive classes: the match class $M$ , containing pairs where $\alpha$ and $\beta$ refer to the same real-world entity, and the nonmatch class $U$ , containing pairs referring to distinct entities.

The comparison between records $\alpha$ and $\beta$ is represented as a comparison random vector: $\mathbf{x} = [x_1, x_2, \dots, x_n]^T$ where each scalar component $x_i$ quantifies the level of agreement between $\alpha$ and $\beta$ on the $i$ -th comparable attribute. In binary agreement models, $x_i = 1$ if field $i$ agrees and $x_i = 0$ if field $i$ disagrees. In continuous models, $x_i \in [0, 1]$ represents a similarity score produced by a field-matching distance metric.
Knowl 2 — Bayes Decision Rule for Minimum Classification Error in Record Linkage
theoretical result
Let $\mathbf{x} = [x_1, \dots, x_n]^T$ be a comparison vector drawn from the comparison space of record pairs $\langle \alpha, \beta \rangle \in A \times B$ . Let $p(\mathbf{x}|M)$ and $p(\mathbf{x}|U)$ be the class-conditional probability density functions for the match class $M$ and nonmatch class $U$ , respectively, with prior probabilities $p(M)$ and $p(U)$ .

The decision rule that assigns a record pair to $M$ when $p(M|\mathbf{x}) \ge p(U|\mathbf{x})$ can be expressed via the likelihood ratio $l(\mathbf{x})$ : $\langle \alpha, \beta \rangle \in \begin{cases} M & \text{if } l(\mathbf{x}) = \frac{p(\mathbf{x}|M)}{p(\mathbf{x}|U)} \ge \frac{p(U)}{p(M)} \\ U & \text{otherwise} \end{cases}$

This decision rule is the Bayes test for minimum error and achieves the minimum overall probability of misclassification. When the Naive Bayes assumption of conditional independence across field agreements holds, the class-conditional joint distributions factorize as: $p(\mathbf{x}|M) = \prod_{i=1}^n p(x_i|M), \quad p(\mathbf{x}|U) = \prod_{i=1}^n p(x_i|U)$
Knowl 3 — Bayes Decision Rule for Minimum Cost under Asymmetric Misclassification
theoretical result
Let $c_{ij}$ denote the cost incurred by classifying a comparison vector $\mathbf{x}$ into class $i$ when its true class is $j$ , where $i, j \in \{M, U\}$ . The conditional expected costs $r_M(\mathbf{x})$ and $r_U(\mathbf{x})$ of deciding match ( $M$ ) and nonmatch ( $U$ ), respectively, are: $r_M(\mathbf{x}) = c_{MM} p(M|\mathbf{x}) + c_{MU} p(U|\mathbf{x})$ $r_U(\mathbf{x}) = c_{UM} p(M|\mathbf{x}) + c_{UU} p(U|\mathbf{x})$

Assigning $\langle \alpha, \beta \rangle$ to $M$ whenever $r_M(\mathbf{x}) < r_U(\mathbf{x})$ results in the minimum-cost decision rule: $\langle \alpha, \beta \rangle \in \begin{cases} M & \text{if } l(\mathbf{x}) = \frac{p(\mathbf{x}|M)}{p(\mathbf{x}|U)} > \frac{(c_{MU} - c_{UU}) p(U)}{(c_{UM} - c_{MM}) p(M)} \\ U & \text{otherwise} \end{cases}$

When the cost matrix satisfies the symmetry condition $c_{UM} - c_{MM} = c_{MU} - c_{UU}$ , the minimum-cost decision rule becomes mathematically identical to the minimum-error Bayes decision rule.
Knowl 4 — Fellegi-Sunter Decision Model with Reject Region for Clerical Review
model/method
In the Fellegi-Sunter theory of record linkage, record pairs whose likelihood ratio $l(\mathbf{x}) = \frac{p(\mathbf{x}|M)}{p(\mathbf{x}|U)}$ is close to the decision boundary are assigned to a third "reject" class $R$ for manual clerical review by human experts rather than being automatically classified into $M$ or $U$ .

Using two predefined thresholds $T_U$ and $T_M$ where $T_U < T_M$ , the classification rule operates as:
1. Classify $\langle \alpha, \beta \rangle$ into $M$ (link) if $l(\mathbf{x}) \ge T_M$ .
2. Classify $\langle \alpha, \beta \rangle$ into $R$ (clerical review) if $T_U < l(\mathbf{x}) < T_M$ .
3. Classify $\langle \alpha, \beta \rangle$ into $U$ (non-link) if $l(\mathbf{x}) \le T_U$ .
The thresholds $T_U$ and $T_M$ are determined either by constraining the maximum acceptable conditional error probabilities for false matches and false nonmatches or by optimizing total operational costs, including the cost of human review.
Knowl 5 — Du Bois Model for Handling Missing Values in Comparison Vectors
model/method
To prevent missing (null) values from causing false mismatch penalties during duplicate record detection, the standard $n$ -dimensional comparison vector $\mathbf{x} = [x_1, \dots, x_n]^T$ is extended to a $2n$ -dimensional comparison vector $\mathbf{x}^*$ : $\mathbf{x}^* = (x_1, x_2, \dots, x_n, x_1 y_1, x_2 y_2, \dots, x_n y_n)$ where $y_i$ is a presence indicator variable defined as: $y_i = \begin{cases} 1 & \text{if the } i\text{-th field is present in both records} \\ 0 & \text{otherwise} \end{cases}$

When either record lacks a value for attribute $i$ , $y_i = 0$ and $x_i y_i = 0$ . By estimating distributions over $p(x_i, y_i | M)$ and $p(x_i, y_i | U)$ from prelabeled training pairs, the linkage model discounts missing attributes rather than interpreting unobserved entries as negative agreement.
Knowl 6 — Jaro and Jaro-Winkler String Distance Metrics
equation
The Jaro comparison metric computes the similarity between two strings $\sigma_1$ and $\sigma_2$ . Two characters $\sigma_1[i]$ and $\sigma_2[j]$ are considered common characters if $\sigma_1[i] = \sigma_2[j]$ and $|i - j| \le \frac{1}{2}\min(|\sigma_1|, |\sigma_2|)$ .

Let $c$ be the number of common characters, and let $t$ be the number of transpositions (half the number of common characters that do not appear in the same relative order in both strings). The Jaro similarity is defined as: $\text{Jaro}(\sigma_1, \sigma_2) = \frac{1}{3}\left( \frac{c}{|\sigma_1|} + \frac{c}{|\sigma_2|} + \frac{c - t/2}{c} \right)$

The Winkler extension (Jaro-Winkler) increases the similarity score for strings that share a common prefix of length $L \le 4$ : $\text{Jaro-Winkler}(\sigma_1, \sigma_2) = \text{Jaro}(\sigma_1, \sigma_2) + L \cdot p \cdot (1 - \text{Jaro}(\sigma_1, \sigma_2))$ where $p$ is a constant scaling factor (typically $p = 0.1$ ).
Knowl 7 — Soundex Phonetic Encoding Algorithm
algorithm
Soundex is a phonetic encoding algorithm that maps names to four-character codes to enable string comparisons that are robust to pronunciation-preserving typographical variations.
Input: String sigma representing a name
Output: Four-character alphanumeric code
code = empty string
Append the first letter of sigma (capitalized) to code
Ignore all subsequent occurrences of 'W' and 'H' in sigma
Map each remaining letter in sigma from position 2 onwards to a digit:
  'B', 'F', 'P', 'V' -> '1'
  'C', 'G', 'J', 'K', 'Q', 'S', 'X', 'Z' -> '2'
  'D', 'T' -> '3'
  'L' -> '4'
  'M', 'N' -> '5'
  'R' -> '6'
  'A', 'E', 'I', 'O', 'U', 'Y' -> '0' (used as separators)
Replace adjacent runs of identical digits with a single occurrence of that digit
Remove all '0' separator digits
Append the mapped digits to code
Truncate code to 4 characters, or pad with trailing '0' characters until length is 4
return code
Knowl 8 — Sorted Neighborhood Method and Multipass Merge-Purge Algorithm
algorithm
The Sorted Neighborhood Method avoids exhaustive $O(|A| \cdot |B|)$ pairwise comparisons by sorting records on an extracted key and restricting comparisons to a sliding window of size $w$ .
Input: Database D of N records, window size w, key definitions K_1, ..., K_m
Output: Set of matching record pairs
all_matches = empty set
for each key definition K in {K_1, ..., K_m} do
  for each record r in D do
    r.key = extract_sorting_key(r, K)
  end for

  sorted_D = sort D lexicographically by r.key

  for i = 1 to N do
    for j = max(1, i - w + 1) to i - 1 do
      if records_match(sorted_D[i], sorted_D[j]) then
        Add (sorted_D[i], sorted_D[j]) to all_matches
      end if
    end for
  end for
end for
clusters = compute transitive closure over all_matches
return clusters
Knowl 9 — Canopy Clustering Method for Efficient Candidate Pair Filtering
model/method
Canopy clustering speeds up duplicate detection over large databases by partitioning records into overlapping subsets (canopies) using an inexpensive similarity metric, eliminating the need to evaluate expensive distance functions across all pairs.

In the first phase, a computationally cheap metric (such as string length bounds, positional $q$ -gram overlap thresholds, or sparse TF-IDF inverted index pruning) places records into multiple, overlapping canopies. In the second phase, computationally intensive and exact field-matching metrics (such as edit distance, affine gap distance, or learned classifier models) are evaluated strictly for pairs of records that co-occur in at least one canopy. Because canopies overlap, this approach eliminates false dismissals caused by rigid non-overlapping boundary partitions while reducing the quadratic comparison complexity.
Knowl 10 — SoftTF-IDF Hybrid Similarity Metric
model/method
The SoftTF-IDF metric combines token-based cosine similarity with fine-grained character-level string distance metrics to handle both word transpositions and token misspellings within database fields.

In standard TF-IDF cosine similarity, strings $\sigma_1$ and $\sigma_2$ are tokenized into words with weights $v_\sigma(w) = \log(\text{tf}_w + 1) \cdot \log(\text{idf}_w)$ , where tokens match only if they are identical. SoftTF-IDF relaxes this constraint by finding pairs of tokens $(w_1 \in \sigma_1, w_2 \in \sigma_2)$ whose character-level similarity (computed via Jaro-Winkler or edit distance) exceeds a similarity threshold $\theta \in [0, 1]$ . In the cosine similarity computation, the product of the token weights $v_{\sigma_1}(w_1) \cdot v_{\sigma_2}(w_2)$ is scaled by the similarity score $\text{sim}(w_1, w_2)$ , capturing both word rearrangements and internal character errors.
Knowl 11 — Early Termination of Multi-Field Record Comparisons
algorithm
Early termination improves the efficiency of individual record comparisons by halting evaluation as soon as the accumulated field evidence guarantees that the final likelihood ratio cannot cross the decision threshold.
Input: Record pair (alpha, beta) with n fields, decision threshold T, prior ratio P(U)/P(M)
Output: Decision Match or Nonmatch
current_ratio = 1.0
for i = 1 to n do
  current_ratio = current_ratio * (p(x_i | M) / p(x_i | U))

  max_potential_gain = product of maximum possible (p(x_j | M) / p(x_j | U)) for remaining fields j = i + 1 to n
  if current_ratio * max_potential_gain < T * (P(U) / P(M)) then
    return Nonmatch
  end if

  min_potential_loss = product of minimum possible (p(x_j | M) / p(x_j | U)) for remaining fields j = i + 1 to n
  if current_ratio * min_potential_loss >= T * (P(U) / P(M)) then
    return Match
  end if
end for
if current_ratio >= T * (P(U) / P(M)) then
  return Match
else
  return Nonmatch
end if
Knowl 12 — Active Learning Framework for Duplicate Record Detection
model/method
Active learning frameworks for duplicate record detection (such as ALIAS) minimize manual labeling effort by selectively querying human annotators only on ambiguous record pairs located in the uncertain reject region.

Because random sampling of record pairs produces an overwhelming majority of obvious non-duplicates, an active learner uses a preliminary classifier trained on a small labeled seed set to score unlabeled record pairs. Candidate pairs for which the classifier has high certainty (either clear matches or clear nonmatches) are automatically categorized without human intervention. The system selectively presents only those pairs with high classification uncertainty to human experts for labeling. These newly labeled boundary pairs provide maximum information gain to iteratively update and refine the duplicate detection classifier.

Coverage note — Deliberately omitted descriptions of third-party software package architectures (Febrl, TAILOR, BigMatch, WizSame) and standard standalone string metrics (Levenshtein edit distance, Smith-Waterman, affine gaps) that are background literature rather than original conceptual frameworks synthesized in this survey.

References

1.A. Chatterjee and A. Segev, “Data Manipulation in Heterogeneous Databases,” ACM SIGMOD Record, vol. 20, no. 4, pp. 64-68, Dec. 1991.
2.IEEE Data Eng. Bull., S. Sarawagi, ed., special issue on data cleaning, vol. 23, no. 4, Dec. 2000.
3.J. Widom, “Research Problems in Data Warehousing,” Proc. 1995 ACM Conf. Information and Knowledge Management (CIKM ’95), pp. 25-30, 1995.
4.A.Z. Broder, S.C. Glassman, M.S. Manasse, and G. Zweig, “Syntactic Clustering of the Web,” Proc. Sixth Int’l World Wide Web Conf. (WWW6), pp. 1157-1166, 1997.
5.J. Cho, N. Shivakumar, and H. Garcia-Molina, “Finding Replicated Web Collections,” Proc. 2000 ACM SIGMOD Int’l Conf. Management of Data (SIGMOD ’00), pp. 355-366, 2000.
6.R. Mitkov, Anaphora Resolution, first ed. Longman, Aug. 2002.
7.A. McCallum, “Information Extraction: Distilling Structured Data from Unstructured Text,” ACM Queue, vol. 3, no. 9, pp. 48-57, 2005.
8.H.B. Newcombe, J.M. Kennedy, S. Axford, and A. James, “Automatic Linkage of Vital Records,” Science, vol. 130, no. 3381, pp. 954-959, Oct. 1959.
9.H.B. Newcombe and J.M. Kennedy, “Record Linkage: Making Maximum Use of the Discriminating Power of Identifying Information,” Comm. ACM, vol. 5, no. 11, pp. 563-566, Nov. 1962.
10.H.B. Newcombe, “Record Linking: The Design of Efficient Systems for Linking Records into Individual and Family Histories,” Am. J. Human Genetics, vol. 19, no. 3, pp. 335-359, May 1967.
11.B.J. Tepping, “A Model for Optimum Linkage of Records,” J. Am. Statistical Assoc., vol. 63, no. 324, pp. 1321-1332, Dec. 1968.
12.I.P. Fellegi and A.B. Sunter, “A Theory for Record Linkage,” J. Am. Statistical Assoc., vol. 64, no. 328, pp. 1183-1210, Dec. 1969.
13.H.B. Newcombe, Handbook of Record Linkage. Oxford Univ. Press, 1988.
14.M.A. Hernández and S.J. Stolfo, “Real-World Data Is Dirty: Data Cleansing and the Merge/Purge Problem,” Data Mining and Knowledge Discovery, vol. 2, no. 1, pp. 9-37, Jan. 1998.
15.S. Sarawagi and A. Bhamidipaty, “Interactive Deduplication Using Active Learning,” Proc. Eighth ACM SIGKDD Int’l Conf. Knowledge Discovery and Data Mining (KDD ’02), pp. 269-278, 2002.
16.Y.R. Wang and S.E. Madnick, “The Inter-Database Instance Identification Problem in Integrating Autonomous Systems,” Proc. Fifth IEEE Int’l Conf. Data Eng. (ICDE ’89), pp. 46-55, 1989.
17.W.W. Cohen, H. Kautz, and D. McAllester, “Hardening Soft Information Sources,” Proc. Sixth ACM SIGKDD Int’l Conf. Knowledge Discovery and Data Mining (KDD ’00), pp. 255-259, 2000.
18.M. Bilenko, R.J. Mooney, W.W. Cohen, P. Ravikumar, and S.E. Fienberg, “Adaptive Name Matching in Information Integration,” IEEE Intelligent Systems, vol. 18, no. 5, pp. 16-23, Sept./Oct. 2003.
19.R. Kimball and J. Caserta, The Data Warehouse ETL Toolkit: Practical Techniques for Extracting, Cleaning, Conforming, and Delivering Data. John Wiley & Sons, 2004.
20.IEEE Data Eng. Bull., E. Rundensteiner, ed., special issue on date transformation, vol. 22, no. 1, Jan. 1999.
21.A. McCallum, D. Freitag, and F.C.N. Pereira, “Maximum Entropy Markov Models for Information Extraction and Segmentation,” Proc. 17th Int’l Conf. Machine Learning (ICML ’00), pp. 591-598, 2000.
22.V.R. Borkar, K. Deshmukh, and S. Sarawagi, “Automatic Segmentation of Text into Structured Records,” Proc. 2001 ACM SIGMOD Int’l Conf. Management of Data (SIGMOD ’01), pp. 175-186, 2001.
23.E. Agichtein and V. Ganti, “Mining Reference Tables for Automatic Text Segmentation,” Proc. 10th ACM SIGKDD Int’l Conf. Knowledge Discovery and Data Mining (KDD ’04), pp. 20-29, 2004.
24.C. Sutton, K. Rohanimanesh, and A. McCallum, “Dynamic Conditional Random Fields: Factorized Probabilistic Models for Labeling and Segmenting Sequence Data,” Proc. 21st Int’l Conf. Machine Learning (ICML ’04), 2004.
25.V. Raman and J.M. Hellerstein, “Potter’s Wheel: An Interactive Data Cleaning System,” Proc. 27th Int’l Conf. Very Large Databases (VLDB ’01), pp. 381-390, 2001.
26.M. Perkowitz, R.B. Doorenbos, O. Etzioni, and D.S. Weld, “Learning to Understand Information on the Internet: An Example-Based Approach,” J. Intelligent Information Systems, vol. 8, no. 2, pp. 133-153, Mar. 1997.
27.T. Dasu, T. Johnson, S. Muthukrishnan, and V. Shkapenyuk, “Mining Database Structure; or, How to Build a Data Quality Browser,” Proc. 2002 ACM SIGMOD Int’l Conf. Management of Data (SIGMOD ’02), pp. 240-251, 2002.
28.V.I. Levenshtein, “Binary Codes Capable of Correcting Deletions, Insertions and Reversals,” Doklady Akademii Nauk SSSR, vol. 163, no. 4, pp. 845-848, 1965, original in Russian—translation in Soviet Physics Doklady, vol. 10, no. 8, pp. 707-710, 1966.
29.G. Navarro, “A Guided Tour to Approximate String Matching,” ACM Computing Surveys, vol. 33, no. 1, pp. 31-88, 2001.
30.G.M. Landau and U. Vishkin, “Fast Parallel and Serial Approximate String Matching,” J. Algorithms, vol. 10, no. 2, pp. 157-169, June 1989.
31.S.B. Needleman and C.D. Wunsch, “A General Method Applicable to the Search for Similarities in the Amino Acid Sequence of Two Proteins,” J. Molecular Biology, vol. 48, no. 3, pp. 443-453, Mar. 1970.
32.E.S. Ristad and P.N. Yianilos, “Learning String Edit Distance,” IEEE Trans. Pattern Analysis and Machine Intelligence, vol. 20, no. 5, pp. 522-532, May 1998.
33.M.S. Waterman, T.F. Smith, and W.A. Beyer, “Some Biological Sequence Metrics,” Advances in Math., vol. 20, no. 4, pp. 367-387, 1976.
34.T.F. Smith and M.S. Waterman, “Identification of Common Molecular Subsequences,” J. Molecular Biology, vol. 147, pp. 195-197, 1981.
35.S.F. Altschula, W. Gisha, W. Millerb, E.W. Meyersc, and D.J. Lipmana, “Basic Local Alignment Search Tool,” J. Molecular Biology, vol. 215, no. 3, pp. 403-410, Oct. 1990.
36.R. Baeza-Yates and G.H. Gonnet, “A New Approach to Text Searching,” Comm. ACM, vol. 35, no. 10, pp. 74-82, Oct. 1992.
37.S. Wu and U. Manber, “Fast Text Searching Allowing Errors,” Comm. ACM, vol. 35, no. 10, pp. 83-91, Oct. 1992.
38.J.C. Pinheiro and D.X. Sun, “Methods for Linking and Mining Heterogeneous Databases,” Proc. Int’l Conf. Knowledge Discovery and Data Mining (KDD ’98), pp. 309-313, 1998.
39.M.A. Jaro, “Unimatch: A Record Linkage System: User’s Manual,” technical report, US Bureau of the Census, Washington, D.C., 1976.
40.W.E. Winkler and Y. Thibaudeau, “An Application of the Fellegi-Sunter Model of Record Linkage to the 1990 US Decennial Census,” Technical Report Statistical Research Report Series RR91/09, US Bureau of the Census, Washington, D.C., 1991.
41.J.R. Ullmann, “A Binary n-Gram Technique for Automatic Correction of Substitution, Deletion, Insertion, and Reversal Errors in Words,” The Computer J., vol. 20, no. 2, pp. 141-147, 1977.
42.E. Ukkonen, “Approximate String Matching with q-Grams and Maximal Matches,” Theoretical Computer Science, vol. 92, no. 1, pp. 191-211, 1992.
43.K. Kukich, “Techniques for Automatically Correcting Words in Text,” ACM Computing Surveys, vol. 24, no. 4, pp. 377-439, Dec. 1992.
44.E. Sutinen and J. Tarhio, “On Using q-Gram Locations in Approximate String Matching,” Proc. Third Ann. European Symp. Algorithms (ESA ’95), pp. 327-340, 1995.
45.L. Gravano, P.G. Ipeirotis, H.V. Jagadish, N. Koudas, S. Muthukrishnan, and D. Srivastava, “Approximate String Joins in a Database (Almost) for Free,” Proc. 27th Int’l Conf. Very Large Databases (VLDB ’01), pp. 491-500, 2001.
46.L. Gravano, P.G. Ipeirotis, H.V. Jagadish, N. Koudas, S. Muthukrishnan, L. Pietarinen, and D. Srivastava, “Using q-Grams in a DBMS for Approximate String Processing,” IEEE Data Eng. Bull., vol. 24, no. 4, pp. 28-34, Dec. 2001.
47.A.E. Monge and C.P. Elkan, “The Field Matching Problem: Algorithms and Applications,” Proc. Second Int’l Conf. Knowledge Discovery and Data Mining (KDD ’96), pp. 267-270, 1996.
48.W.W. Cohen, “Integration of Heterogeneous Databases without Common Domains Using Queries Based on Textual Similarity,” Proc. 1998 ACM SIGMOD Int’l Conf. Management of Data (SIGMOD ’98), pp. 201-212, 1998.
49.L. Gravano, P.G. Ipeirotis, N. Koudas, and D. Srivastava, “Text Joins in an RDBMS for Web Data Integration,” Proc. 12th Int’l World Wide Web Conf. (WWW12), pp. 90-101, 2003.
50.R.C. Russell Index, U.S. Patent 1,261,167, http://patft.uspto. gov/netahtml/srchnum.htm, Apr. 1918.
51.R.C. Russell Index, U.S. Patent 1,435,663, http://patft.uspto. gov/netahtml/srchnum.htm, Nov. 1922.
52.R.L. Taft, “Name Search Techniques,” Technical Report Special Report No. 1, New York State Identification and Intelligence System, Albany, N.Y., Feb. 1970.
53.L.E. Gill, “OX-LINK: The Oxford Medical Record Linkage System,” Proc. Int’l Record Linkage Workshop and Exposition, pp. 15-33, 1997.
54.L. Philips, “Hanging on the Metaphone,” Computer Language Magazine, vol. 7, no. 12, pp. 39-44, Dec. 1990, http://www.cuj.com/documents/s=8038/cuj0006philips/.
55.L. Philips, “The Double Metaphone Search Algorithm,” C/C++ Users J., vol. 18, no. 5, June 2000.
56.N. Koudas, A. Marathe, and D. Srivastava, “Flexible String Matching against Large Databases in Practice,” Proc. 30th Int’l Conf. Very Large Databases (VLDB ’04), pp. 1078-1086, 2004.
57.R. Agrawal and R. Srikant, “Searching with Numbers,” Proc. 11th Int’l World Wide Web Conf. (WWW11), pp. 420-431, 2002.
58.W.E. Yancey, “Evaluating String Comparator Performance for Record Linkage,” Technical Report Statistical Research Report Series RRS2005/05, US Bureau of the Census, Washington, D.C., June 2005.
59.S. Tejada, C.A. Knoblock, and S. Minton, “Learning Domain-Independent String Transformation Weights for High Accuracy Object Identification,” Proc. Eighth ACM SIGKDD Int’l Conf. Knowledge Discovery and Data Mining (KDD ’02), 2002.
60.T. Hastie, R. Tibshirani, and J.H. Friedman, The Elements of Statistical Learning. Springer Verlag, Aug. 2001.
61.M.A. Jaro, “Advances in Record-Linkage Methodology as Applied to Matching the 1985 Census of Tampa, Florida,” J. Am. Statistical Assoc., vol. 84, no. 406, pp. 414-420, June 1989.
62.A.P. Dempster, N.M. Laird, and D.B. Rubin, “Maximum Likelihood from Incomplete Data via the EM Algorithm,” J. Royal Statistical Soc., vol. B, no. 39, pp. 1-38, 1977.
63.W.E. Winkler, “Improved Decision Rules in the Felligi-Sunter Model of Record Linkage,” Technical Report Statistical Research Report Series RR93/12, US Bureau of the Census, Washington, D.C., 1993.
64.W.E. Winkler, “Methods for Record Linkage and Bayesian Networks,” Technical Report Statistical Research Report Series RRS2002/05, US Bureau of the Census, Washington, D.C., 2002.
65.K. Nigam, A. McCallum, S. Thrun, and T.M. Mitchell, “Text Classification from Labeled and Unlabeled Documents Using EM,” Machine Learning, vol. 39, nos. 2/3, pp. 103-134, 2000.
66.N.S.D. Du Bois Jr., “A Solution to the Problem of Linking Multivariate Documents,” J. Am. Statistical Assoc., vol. 64, no. 325, pp. 163-174, Mar. 1969.
67.R.O. Duda and P.E. Hart, Pattern Classification and Scene Analysis. Wiley, 1973.
68.V.S. Verykios, G.V. Moustakides, and M.G. Elfeky, “A Bayesian Decision Model for Cost Optimal Record Matching,” VLDB J., vol. 12, no. 1, pp. 28-40, May 2003.
69.V.S. Verykios and G.V. Moustakides, “A Generalized Cost Optimal Decision Model for Record Matching,” Proc. 2004 Int’l Workshop Information Quality in Information Systems, pp. 20-26, 2004.
70.M. Cochinwala, V. Kurien, G. Lalk, and D. Shasha, “Efficient Data Reconciliation,” Information Sciences, vol. 137, nos. 1-4, pp. 1-15, Sept. 2001.
71.L. Breiman, J.H. Friedman, R.A. Olshen, and C.J. Stone, Classification and Regression Trees. CRC Press, July 1984.
72.T. Joachims, “Making Large-Scale SVM Learning Practical,” Advances in Kernel Methods—Support Vector Learning, B. Schölkopf, C.J.C. Burges, and A.J. Smola, eds., MIT Press, 1999.
73.A.E. Monge and C.P. Elkan, “An Efficient Domain-Independent Algorithm for Detecting Approximately Duplicate Database Records,” Proc. Second ACM SIGMOD Workshop Research Issues in Data Mining and Knowledge Discovery (DMKD ’97), pp. 23-29, 1997.
74.N. Bansal, A. Blum, and S. Chawla, “Correlation Clustering,” Machine Learning, vol. 56, nos. 1-3, pp. 89-113, 2004.
75.W.W. Cohen and J. Richman, “Learning to Match and Cluster Large High-Dimensional Data Sets for Data Integration,” Proc. Eighth ACM SIGKDD Int’l Conf. Knowledge Discovery and Data Mining (KDD ’02), 2002.
76.A. McCallum and B. Wellner, “Conditional Models of Identity Uncertainty with Application to Noun Coreference,” Advances in Neural Information Processing Systems (NIPS ’04), 2004.
77.P. Singla and P. Domingos, “Multi-Relational Record Linkage,” Proc. KDD-2004 Workshop Multi-Relational Data Mining, pp. 31-48, 2004.
78.H. Pasula, B. Marthi, B. Milch, S.J. Russell, and I. Shpitser, “Identity Uncertainty and Citation Matching,” Advances in Neural Information Processing Systems (NIPS ’02), pp. 1401-1408, 2002.
79.D.A. Cohn, L. Atlas, and R.E. Ladner, “Improving Generalization with Active Learning,” Machine Learning, vol. 15, no. 2, pp. 201-221, 1994.
80.S. Tejada, C.A. Knoblock, and S. Minton, “Learning Object Identification Rules for Information Integration,” Information Systems, vol. 26, no. 8, pp. 607-633, 2001.
81.W.W. Cohen, “Data Integration Using Similarity Joins and a Word-Based Information Representation Language,” ACM Trans. Information Systems, vol. 18, no. 3, pp. 288-321, 2000.
82.D. Dey, S. Sarkar, and P. De, “Entity Matching in Heterogeneous Databases: A Distance Based Decision Model,” Proc. 31st Ann. Hawaii Int’l Conf. System Sciences (HICSS ’98), pp. 305-313, 1998.
83.S. Guha, N. Koudas, A. Marathe, and D. Srivastava, “Merging the Results of Approximate Match Operations,” Proc. 30th Int’l Conf. Very Large Databases (VLDB ’04), pp. 636-647, 2004.
84.R.K. Ahuja, T.L. Magnanti, and J.B. Orlin, Network Flows: Theory, Algorithms, and Applications, first ed. Prentice Hall, Feb. 1993.
85.R. Ananthakrishna, S. Chaudhuri, and V. Ganti, “Eliminating Fuzzy Duplicates in Data Warehouses,” Proc. 28th Int’l Conf. Very Large Databases (VLDB ’02), 2002.
86.S. Chaudhuri, V. Ganti, and R. Motwani, “Robust Identification of Fuzzy Duplicates,” Proc. 21st IEEE Int’l Conf. Data Eng. (ICDE ’05), pp. 865-876, 2005.
87.E.-P. Lim, J. Srivastava, S. Prabhakar, and J. Richardson, “Entity Identification in Database Integration,” Proc. Ninth IEEE Int’l Conf. Data Eng. (ICDE ’93), pp. 294-301, 1993.
88.H. Galhardas, D. Florescu, D. Shasha, E. Simon, and C.-A. Saita, “Declarative Data Cleaning: Language, Model, and Algorithms,” Proc. 27th Int’l Conf. Very Large Databases (VLDB ’01), pp. 371-380, 2001.
89.V.S. Verykios, A.K. Elmagarmid, and E.N. Houstis, “Automating the Approximate Record Matching Process,” Information Sciences, vol. 126, nos. 1-4, pp. 83-98, July 2000.
90.A. Blum and T. Mitchell, “Combining Labeled and Unlabeled Data with Co-Training,” COLT ’98: Proc. 11th Ann. Conf. Computational Learning Theory, pp. 92-100, 1998.
91.P. Cheeseman and J. Sturz, “Bayesian Classification (Autoclass): Theory and Results,” Advances in Knowledge Discovery and Data Mining, pp. 153-180, AAAI Press/The MIT Press, 1996.
92.M.G. Elfeky, A.K. Elmagarmid, and V.S. Verykios, “TAILOR: A Record Linkage Tool Box,” Proc. 18th IEEE Int’l Conf. Data Eng. (ICDE ’02), pp. 17-28, 2002.
93.P. Ravikumar and W.W. Cohen, “A Hierarchical Graphical Model for Record Linkage,” 20th Conf. Uncertainty in Artificial Intelligence (UAI ’04), 2004.
94.I. Bhattacharya and L. Getoor, “Latent Dirichlet Allocation Model for Entity Resolution,” Technical Report CS-TR-4740, Computer Science Dept., Univ. of Maryland, Aug. 2005.
95.A. McCallum, K. Nigam, and L.H. Ungar, “Efficient Clustering of High-Dimensional Data Sets with Application to Reference Matching,” Proc. Sixth ACM SIGKDD Int’l Conf. Knowledge Discovery and Data Mining (KDD ’00), pp. 169-178, 2000.
96.S. Chaudhuri, K. Ganjam, V. Ganti, and R. Motwani, “Robust and Efficient Fuzzy Match for Online Data Cleaning,” Proc. 2003 ACM SIGMOD Int’l Conf. Management of Data (SIGMOD ’03), pp. 313-324, 2003.
97.R. Baxter, P. Christen, and T. Churches, “A Comparison of Fast Blocking Methods for Record Linkage,” Proc. ACM SIGKDD ’03 Workshop Data Cleaning, Record Linkage, and Object Consolidation, pp. 25-27, 2003.
98.A. Soffer, D. Carmel, D. Cohen, R. Fagin, E. Farchi, M. Herscovici, and Y.S. Maarek, “Static Index Pruning for Information Retrieval Systems,” Proc. 24th Ann. Int’l ACM SIGIR Conf. Research and Development in Information Retrieval, (SIGIR ’01), pp. 43-50, 2001.
99.N. Mamoulis, “Efficient Processing of Joins on Set-Valued Attributes,” Proc. 2003 ACM SIGMOD Int’l Conf. Management of Data (SIGMOD ’03), pp. 157-168, 2003.
100.J. Zobel, A. Moffat, and K. Ramamohanarao, “Inverted Files versus Signature Files for Text Indexing,” ACM Trans. Database Systems, vol. 23, no. 4, pp. 453-490, Dec. 1998.
101.S. Sarawagi and A. Kirpal, “Efficient Set Joins on Similarity Predicates,” Proc. 2004 ACM SIGMOD Int’l Conf. Management of Data (SIGMOD ’04), pp. 743-754, 2004.
102.D. Koller and M. Sahami, “Hierarchically Classifying Documents Using Very Few Words,” Proc. 14th Int’l Conf. Machine Learning (ICML ’97), pp. 170-178, 1997.
103.W.E. Yancey, “Bigmatch: A Program for Extracting Probable Matches from a Large File for Record Linkage,” Technical Report Statistical Research Report Series RRC2002/01, US Bureau of the Census, Washington, D.C., Mar. 2002.
104.W.E. Winkler, “Overview of Record Linkage and Current Research Directions,” Technical Report Statistical Research Report Series RRS2006/02, US Bureau of the Census, Washington, D.C., 2006.
105.IEEE Data Eng. Bull., N. Koudas, ed., special issue on data quality, vol. 29, no. 2, June 2006.
106.W.E. Winkler, “The State of Record Linkage and Current Research Problems,” Technical Report Statistical Research Report Series RR99/04, US Bureau of the Census, Washington, D.C., 1999.

Citation

MLA

Elmagarmid, A. K., et al. “Duplicate Record Detection: A Survey”. IEEE Transactions on Knowledge and Data Engineering, vol. 19, no. 1, 2007, pp. 1–6, https://doi.org/10.1109/tkde.2007.250581.

APA

Elmagarmid, A. K., Ipeirotis, P. G., & Verykios, V. S. (2007). Duplicate Record Detection: A Survey. IEEE Transactions on Knowledge and Data Engineering, 19(1), 1–16. https://doi.org/10.1109/tkde.2007.250581

Chicago

Elmagarmid, A. K., P. G. Ipeirotis, and V. S. Verykios. 2007. “Duplicate Record Detection: A Survey”. IEEE Transactions on Knowledge and Data Engineering 19 (1): 1–16. https://doi.org/10.1109/tkde.2007.250581.

Harvard

Elmagarmid, A.K., Ipeirotis, P.G. and Verykios, V.S. (2007) “Duplicate Record Detection: A Survey”, IEEE Transactions on Knowledge and Data Engineering, 19(1), pp. 1–16. Available at: https://doi.org/10.1109/tkde.2007.250581.

Vancouver

1. Elmagarmid AK, Ipeirotis PG, Verykios VS (2007) Duplicate Record Detection: A Survey. IEEE Transactions on Knowledge and Data Engineering 19:1–16

BibTeX

@article{Elmagarmid_2007, title={Duplicate Record Detection: A Survey}, volume={19}, ISSN={1041-4347}, url={http://dx.doi.org/10.1109/tkde.2007.250581}, DOI={10.1109/tkde.2007.250581}, number={1}, journal={IEEE Transactions on Knowledge and Data Engineering}, publisher={Institute of Electrical and Electronics Engineers (IEEE)}, author={Elmagarmid, Ahmed K. and Ipeirotis, Panagiotis G. and Verykios, Vassilios S.}, year={2007}, month=Jan, pages={1–16} }

Metadata:Crossref

Access the Paper

This paper is available from its original source. Click below to access the PDF.

Open PDF

Duplicate Record Detection: A Survey

Abstract

Topics

Keywords

Table of Contents

Knowls

Knowl 1 — Formal Framework and Vector Representation for Duplicate Record Detection

Knowl 2 — Bayes Decision Rule for Minimum Classification Error in Record Linkage

Knowl 3 — Bayes Decision Rule for Minimum Cost under Asymmetric Misclassification

Knowl 4 — Fellegi-Sunter Decision Model with Reject Region for Clerical Review

Knowl 5 — Du Bois Model for Handling Missing Values in Comparison Vectors

Knowl 6 — Jaro and Jaro-Winkler String Distance Metrics

Knowl 7 — Soundex Phonetic Encoding Algorithm

Knowl 8 — Sorted Neighborhood Method and Multipass Merge-Purge Algorithm

Knowl 9 — Canopy Clustering Method for Efficient Candidate Pair Filtering

Knowl 10 — SoftTF-IDF Hybrid Similarity Metric

Knowl 11 — Early Termination of Multi-Field Record Comparisons

Knowl 12 — Active Learning Framework for Duplicate Record Detection

References

Citation

BibTeX

Access the Paper