Data Matching Algorithms: Engineering Multi-Algorithm Record Linkage Systems

Selecting, combining and evaluating string similarity and phonetic algorithms for entity matching.

Data matching is often reduced to a deceptively simple problem: compare two values, calculate a similarity score and decide whether they represent the same entity.

Production record linkage is considerably more complex.

A person name, organisation name, postal address, telephone number and email address have different structures, distributions and failure modes. Typographical errors, character transpositions, abbreviations, token reordering, transliteration and phonetic variation all require different comparison strategies.

The engineering challenge is therefore not simply:

Which data matching algorithm is best?

A more useful question is:

Which comparison function should be applied to each attribute, under which conditions, and how should the resulting evidence be combined into a matching decision?

This is the principle behind multi-algorithm record linkage and the approach used by WinPure AdaptiveMatch™.

Record Linkage as a Classification Problem

Consider two records, rir_i and rjr_j. The objective of a matching system is to determine whether they refer to the same underlying entity.

At its simplest:

M(ri,rj)∈{0,1}M(r_i,r_j) \in \{0,1\}

where 1 represents a match and 0 represents a non-match.

The decision is rarely based on a single value. Instead, individual attributes are compared using one or more comparison functions:

sk=fk(rik,rjk)s_k = f_k(r_{ik},r_{jk})

where fkf_k is the comparison function applied to attribute kk.

For a customer dataset, the resulting comparison vector might contain evidence from name, date of birth, address, email and telephone fields:

S=(sname,sdob,saddress,semail,sphone)S=(s_{name},s_{dob},s_{address},s_{email},s_{phone})

The important point is that there is no requirement for every fkf_k to be the same function.

In fact, there are good reasons why they should not be.

Why a Single Similarity Algorithm Is Usually Insufficient

Different attributes exhibit different types of variation.

Consider the following pairs:

Applying the same character similarity function and threshold to every example ignores the semantics of the underlying attributes.

This distinction becomes important because similarity algorithms encode assumptions about the types of errors they are designed to tolerate.

Character-Level Similarity

Edit-distance algorithms are among the most widely used techniques for approximate string matching.

Levenshtein Distance

Levenshtein distance measures the minimum number of insertions, deletions and substitutions required to transform one string into another.

For strings aa and bb, the dynamic-programming recurrence can be represented as:

D(i,j)=min⁡{D(i−1,j)+1D(i,j−1)+1D(i−1,j−1)+cD(i,j)=\min \begin{cases} D(i-1,j)+1\\ D(i,j-1)+1\\ D(i-1,j-1)+c \end{cases}

where c=0c=0 when the characters are equal and c=1c=1 otherwise.

This works well for many typographical variations but does not inherently understand the semantics of the strings being compared.

It also illustrates an important distinction between distance and similarity. A raw edit distance of two characters means something very different for a four-character string than for a forty-character string. Implementations commonly normalise distance when a comparable similarity score is required.

Damerau-Levenshtein

Damerau-Levenshtein extends the edit model to include character transpositions.

For example:

Brian → Brain

A transposition-aware algorithm can represent this differently from an algorithm that must model the change as multiple independent edits.

The distinction matters when adjacent character reversals are common in the source data.

Jaro and Jaro-Winkler

Jaro similarity considers matching characters and transpositions within a defined matching window.

Jaro-Winkler extends this by increasing similarity when strings share a common prefix.

That property can make Jaro-Winkler particularly useful for person-name matching, where early characters often carry useful information.

However, the same prefix weighting that benefits one attribute type may be undesirable for another.

This is precisely why the question should not be “Is Jaro-Winkler better than Levenshtein?” without first defining the data and error model.

Smith-Waterman-Gotoh

Smith-Waterman approaches comparison as a local sequence-alignment problem. The Gotoh optimisation introduces affine gap penalties, distinguishing between opening and extending a gap.

This makes it possible to model contiguous insertions or deletions differently from multiple unrelated character errors.

The technique is computationally more sophisticated than simple edit distance, but may provide useful behaviour where local alignment is more informative than whole-string transformation.

WinPureFuzzy™

WinPureFuzzy™ is WinPure’s proprietary fuzzy data matching algorithm and forms one of the comparison methods available within AdaptiveMatch™.

Its purpose is not to replace every other similarity function.

Instead, WinPureFuzzy™ provides a general-purpose fuzzy comparison capability that can be applied to suitable attributes and incorporated into broader matching rules alongside exact, phonetic and other algorithmic comparisons.

This distinction is important.

A similarity algorithm produces evidence about two values. It does not necessarily determine whether two complete records represent the same entity.

For example, a strong fuzzy similarity between two surnames may provide useful evidence. The matching decision can become substantially stronger when supported by additional agreement on date of birth, postcode, email address or other identifying attributes.

AdaptiveMatch therefore treats algorithm selection as part of rule construction rather than assuming that one similarity score should determine entity identity.

Token-Based Comparison

Character-level algorithms can perform poorly when strings contain similar tokens in different positions.

Consider:

Advanced Data Systems Ltd

and:

Data Systems Advanced Ltd

The semantic content is highly similar, but the character sequence has changed substantially.

Token-based approaches can normalise or reorder tokens before performing the underlying comparison.

This can be valuable for organisation names and other multi-token fields where ordering is inconsistent.

However, token sorting also removes information.

If token order itself is discriminative, normalising it can increase the probability of false matches.

As with edit distance, token-based comparison is therefore not intrinsically “better.” It represents another error model that is appropriate for particular data characteristics.

String similarity and phonetic matching measure different forms of variation and can be combined as complementary evidence within a data matching rule.

Phonetic Matching Is a Different Class of Comparison

Phonetic algorithms address a fundamentally different problem.

Rather than measuring character similarity directly, they encode strings according to an approximation of their pronunciation.

If:

P(x)=P(y)P(x)=P(y)

this does not imply:

x=yx=y

It indicates that the phonetic encoding function has mapped the values into the same or comparable representation.

This is useful for variations such as:

Steven ↔ Stephen

or surnames whose spelling has changed across systems, languages or generations.

AdaptiveMatch supports multiple phonetic approaches, including:

• Soundex
• Double Metaphone
• Kölner Phonetik
• Daitch-Mokotoff
• NYSIIS
• Caverphone 2

These algorithms should not be treated as interchangeable.

Soundex, for example, was designed around English-language surname patterns. Daitch-Mokotoff was developed to better handle Slavic and Yiddish surnames. Kölner Phonetik targets German names, while algorithms such as NYSIIS and Caverphone use different transformation rules and linguistic assumptions.

Consequently, “use phonetic matching” is not a sufficiently precise matching strategy.

The appropriate question is which phonetic representation is suitable for the population and attribute being compared?

Combining String and Phonetic Evidence

A useful matching system does not necessarily have to choose between fuzzy and phonetic comparison.

They can represent separate pieces of evidence.

Conceptually, a name comparison might produce:

string_similarity =
    WinPureFuzzy(recordA.Name, recordB.Name)
phonetic_match =
    DoubleMetaphone(recordA.Name) ==
    DoubleMetaphone(recordB.Name)
postcode_match =
    recordA.Postcode == recordB.Postcode

The final record-level decision can then depend on the combination of these signals.

This also provides better control over false positives.

Phonetic encodings intentionally compress the representation of names. Multiple distinct strings can therefore map to the same code. Treating phonetic equivalence as definitive identity can produce collisions.

Supporting evidence from other attributes can make the resulting rule substantially more discriminative.

Moving from Algorithms to Matching Rules

A multi-field matching configuration can be represented conceptually as:

R={(fk,tk,wk,mk)}k=1nR=\{(f_k,t_k,w_k,m_k)\}_{k=1}^{n}

where:

• fkf_k is the comparison algorithm;
• tkt_k is the acceptance threshold;
• wkw_k represents the contribution of the field;
• mkm_k represents the matching mode.

A configuration might therefore resemble:

This is fundamentally different from applying:

FuzzyMatch(all_fields, 85%)

across an entire dataset.

The rule contains assumptions about both the meaning of each attribute and the type of variation expected within it.

Adaptive Algorithm Selection

As matching systems become more configurable, another problem appears: configuration complexity.

A dataset containing dozens of candidate matching attributes can create a large configuration space involving algorithms, thresholds, phonetic options, matching types and rule weighting.

AdaptiveMatch™ addresses this by using information about the data and its semantic type to help determine an appropriate matching configuration.

Conceptually:

The underlying principle is straightforward: matching configuration should adapt to the data rather than requiring every dataset to conform to a fixed global matching strategy.

Technical users can still explicitly configure algorithms where domain knowledge justifies a different decision.

This is particularly important because automated selection should be treated as configuration assistance rather than an assertion that an algorithm can infer every organisation’s definition of identity.

Thresholds, Precision and Recall

Threshold selection introduces another optimisation problem.

For a labelled matching dataset:

Precision=TPTP+FPPrecision=\frac{TP}{TP+FP}

and:

Recall=TPTP+FNRecall=\frac{TP}{TP+FN}

Reducing a similarity threshold will typically increase the number of candidate matches accepted. This may improve recall while increasing false positives.

Increasing the threshold may improve precision while introducing additional false negatives.

The optimum depends on the application.

In some systems, incorrectly merging two independent entities can be considerably more damaging than leaving a duplicate unresolved.

This can be represented as a cost-sensitive objective:

min⁡(CFPFP+CFNFN)\min(C_{FP}FP+C_{FN}FN)

where CFPC_{FP} and CFNC_{FN} represent the application-specific costs of false-positive and false-negative decisions.

Consequently, maximising F1 is not necessarily the correct optimisation target for every entity-matching problem.

Matching at Scale

Algorithm accuracy is only one dimension of a production matching system.

A naïve all-pairs comparison across nn records requires:

n(n−1)2\frac{n(n-1)}{2}

candidate comparisons.

For one million records, that represents:

499,999,500,000499,999,500,000

possible record pairs.

Executing multiple sophisticated similarity algorithms against every pair is clearly impractical.

Production architectures therefore need to consider candidate generation, indexing, blocking or equivalent search-space reduction techniques before expensive comparison functions are executed.

Algorithm selection also has computational consequences.

A simple exact comparison, edit-distance calculation, phonetic transformation and local sequence alignment do not have identical CPU or memory characteristics.

A matching strategy therefore needs to optimise not only statistical quality but also computational efficiency.

Benchmarking Matching Algorithms Properly

Algorithm comparisons based on a handful of hand-selected names provide very little evidence about production performance.

A more defensible evaluation requires a labelled dataset containing known matches and non-matches.

The test pipeline should ideally include:

Ground Truth
    ↓
Candidate Generation
    ↓
Comparison Algorithms
    ↓
Threshold Sweep
    ↓
Classification
    ↓
TP / FP / TN / FN
    ↓
Precision / Recall
    ↓
Runtime and Resource Measurement

For AdaptiveMatch, a useful benchmark would compare both individual algorithms and complete matching strategies:

The objective should not be to prove that one algorithm universally wins.

It should be to determine which configuration produces the required balance of precision, recall and computational performance for a particular dataset.

The Engineering Case for Adaptive Matching

There is unlikely to be a universally optimal string-matching algorithm because record linkage is not a single similarity problem.

It is a collection of comparison problems operating across attributes with different semantics, distributions and error characteristics.

Levenshtein can model character edits. Damerau-Levenshtein can account for transpositions. Jaro-Winkler can emphasise common prefixes. Token-based methods can address reordered terms. Phonetic algorithms can identify pronunciation-related variation. WinPureFuzzy™ provides WinPure’s proprietary fuzzy comparison capability.

The more important engineering question is how these techniques should be selected and combined.

AdaptiveMatch™ is designed around this principle.

Instead of assuming that every column should use the same algorithm, matching mode and threshold, AdaptiveMatch allows comparison strategies to be selected at the attribute level and combined into more expressive matching rules. Where appropriate, it can automatically determine suitable configurations based on the characteristics and semantic type of the data while retaining explicit control for technical users.

The result is a shift away from asking:

“Which fuzzy matching algorithm should we use?”

towards the more useful question:

“What combination of comparison functions provides the strongest evidence that these two records represent the same entity?”

For production record linkage, that is the problem the matching architecture ultimately needs to solve.

Frequently Asked Questions

Written by

Team WinPure

The WinPure Team shares official updates on our products, features, and company news. From new releases and enhancements to behind-the-scenes developments, this space keeps you informed on how WinPure continues to deliver secure, reliable, and innovative data quality solutions.