DOCUMENT RESUME
TM 015 738

ED 325 505
AUTHOR
TITLE

Winkler, William E.
String Comparator Metrics and Enhanced Decision Rulesin the Fellegi-Sunter Model of Record Linkage.

PUB DATENOTE
PUB TYPE

90
8p.

EDRS PRICEDESCRIPTORS

MF01/PC01 Plus Postage.
Census Figures; *Comparative Analysis; Computer Usesin Education; *Decision Making; Equations(Mathematics); Evaluation Methods; *Mathematical
Models; Research Methodology
Decision Rules; *Fellegi Sunter Model of Record
Linkage; *String Comparator Metrics

IDENTIFIERS

Reports - Evaluative/Feasibility (142)

ABSTRACT
To locate matches across pairs of lists without
unique identifiers it is sometimes necessary to compare strings ofletters. String comparators are used in production computer matchingsoftware during the Post Enumeration Survey for the 1990 U.S. census.
A string comparator metric is described that partial]y accounts for:(1) typographical variation in strings such as first name or surname;(2) decision rules that use the string comparator; and (3)improvements in empirical matching results. The string comparator
metric for comparing partially agreeing strings extends the Jaro
string comparator. How general methods of accounting for partial
agreement fit with the Fellegi-Sunter (I. P. Fellegi and A. B.
Sunter, 1969) model of record linkage is described. A formal methodof modeling how to adjust matching weights between pure agreement andpure disagreement is presented. The procedure is illustrated forfiles for which the truth of matches is known. It is demonstrated
that the theoretical rules of Fellegi and Sunter are still valid whengeneral weighting adjustments accounting for partial agreement are
performed. Eight tables contain illustrative data. (SLD)

Reproductions supplied by EDRS are the best that can be mPde
from the original document.

U.S. DEPARTMENT OF SOUCATION
Office al Educational ssssrcli and Improvement"PERMISSION TO REPRODUCE THIS
MATERIAL HAS BEEN GRANTED BY

EDUCATIONAL RESOURCES INFORMATIONCENTER (ERIC)WA LIAM E. Ummtrg

is document hes been reproduced ea
received horn th penal O orEaruciroOncognate% it
0 Minor changes Rove been made to improve
reproduction quality
Points of view or opinions stated in th4 <Meta-

TO THE EDUCATIONAL RESOURCESINFORMATION CENTER (ERIC) "ment do not neasseenly represent official
OERI position or policy

STRING COMPARATOR METRICS AND ENHANCED DECISION RULES IN THE
FELLEGI-SUNTER MODEL OF RECORD LINKAGE

William E. Winkler, U.S. Bureau of the Census
Stat. Research Div., Rm. 3000-4, Washington, DC 20223

2

String Comparator Metrics and Enhanced Decision Rules in theFellegi-Sunter Model of Record Linkage

William E. Winkler, U.S. Bureau of the Census*
Stat. Research Div., Rm 3000-4, Washington, DC 20223

ABSTRACTThis paper describes a string comparator metric thatpartially accounts for typographical variation in
strings such as first name or surname, decision rulesthat utilize the string comparator, and improvementsin empirical matching results. The string comparators

are used in production computer matching software
during the Post Enumeration Survey for the 1990
Census.

The Post Enumeration Survey will use

capture/recapture and other statistical techniques to
produce a set of adjusted Census counts.

metrics for comparing partially agreeing strings that
extend the Jaro string comparator (see e.g., Winkler
1985). It formally shows how general methods ofaccounting for partial agreement fit in with theFellegi-Sunter (1969) model of record linkage. It
provides a formal method of modelling how to adjust
matching weights between pure agreement and puredisagreement. The methods are dependent on having
a representative set of matching pairs.
The second section of the paper consists of fourparts. The first part provides brief background on theFellegi-Sunter model of record linkage. In the second

INTRODUCTION
Locating matches across a pair of lists not having
unique identifiers such as a social security number isoften difficult. Typically available identifiers such aspart, we show how partial agreement relates tofirst name, last name, and various demographic,

the specific string ummparator and methods formodelling how it is used in adjusting matching1.

economic, or address components may not uniquely
identify matches because of legitimate variations.
Some types of legitimate variations in identifiers
generally require a priori knowledge that allows rapid,
accurate utilization. Such variations might take theforms Mrs W M Smith and Elizabeth Smith.
Typographical variations such as Elizabeth Smith
versus Elzbath Smoth are a special case of legitimate
variations. They are more easily dealt with if suitable
methods of comparing strings are available and are
the only variations that we will consider in this paper.

If Si and S2 are two strings, a suing comparator`I, merely maps the pair (51,S2) to the closed interval[0,1]. A string comparator is not necessarily a metricin the mathematical sense and the restriction of its
range to [0,1] is done primarily for convenience.

general likelihood ratios and associated information-_
theoretic decision rules. The empirical data base isdescribed in the third part. The fourth part presents

weights between pure agreement and disagreement.
The third section contains empirical results basedon files for which the truth of matches is known. The
first subsection shows how specific weight adjustment

curves are modelled for strings such as last name.
The second subsection contains matching results thatshow the improvements due string comparators. The
improvements are placed in the context of all techniques implemented in current production computer
matching software that increase matching efficacy.

The fourth section provides discussion of thequality of the empirical data bases used in theanalyses and the limitations of the existing string
compatator/weight adjustment method.
The fmal section is a summary.

Generally, we want Fairs of strings that agree exactly

to be assigned value 1, pairs of strings that agree
almost exactly (in some sensc) to have values close to1, and strings that entitely disagree (in some sense) tohave value 0.

BACKGROUND
2.1. Fellegi-Sunter Model of Record Linkage
The Fellegi-Sunter Model uses a decision-theoretic
approach establishing the validity of principles fust2.

A simple example of a string comparator is aused in practice by Newcombe (Newcombe et al.

function that assigns value 1 to a pair of strings that

1959, also 1988). To give an overview, we describe

agree exactly or agree exactly on a code such as

the model in terms of ordered pairs in a productSoundex and, otherwise, assigns value 0. Anotherexample would be a properly normalized DamerauLevenstein metric that accounts for the number of
insertions and deletions it takes to get from one string
to another (see e.g., Winkler 1985).
This paper provides a class of string comparator

space. The description closely follows Fellegi andSunter (1969, pp. 1184-1187).

There are two populations A and

B

whose

elements will be denoted by a and b. We assume
that some elements are common to A and B.
Consequently the set of ordered pairs

comparison is erroneously linked. It has probability

AXB = ((a,b): aeA, beB)

P(A,IU) = E u(y)P(A,Iy)is the union of two disjoint sets of matchesyer
M = ((a,b): a=b, aEA, beB)

A Type II error occurs if a matched comparison iserroneously not linked. It has probability

and nonmatches

P(A,IM) = E m(y)?(A,Iy)

U = ((a,b): ab, aeA, beB ).

yer
The records corresponding to members of A and
B are denoted by a(a) and B(b), respectively. The
comparison vector y associated with the records isdefined by:Fellegi and Sunter (1969) define a linkage rule Lo,with associated decisions A,, A2, and A,, that is
optimal in the following sense:

Theorem (Fellegi-Sunter 1969). Let L' be alinkage rule with associated decisions A,', A2', andifct(a),B(b)]fy l[a(a).13(b)],y2[a(a)4(b)],...,y K[a(a)40)]A,

Each of the y', i = 1,

K, represents a specificcould represent
For instance, ycomparison.
agreement/disagreement on sex. Also, y2 could
represent the comparison that two surnames agree andtake a specific value or that they disagree.
Where confusion does not arise, the function y on
AXB will be denoted by 1(a,B), 1(a,b), or y. The
set of all possible realizations of y is denoted by r.

The conditional probability of

1(a,b)

given(a,b)EM ism(y)P Na(a),13(b))I(a,b)eM )such that it has the same error probabilities

P(A,'IM) = P(A,IM) and P(A, '111) = P(A,IU) as Lo.
Then Lo is optimal in that P(A2IU) P(A2'IU) andP(A2IM)

P(A21M).

In other words, if L' is any competitor of Lohaving the same Type I and Type II error rates(which are both conditional probabilities), then theconditional probabilities (either on set U or M) of
not making a decision under rule L' are always
greater than under L.
2.2 General Partial Agreement
If the set of matches M were known, then we
could model how partial agreement affects matchingweights as follows:

P (y[a(a),B(b)) ) P[(a,b)IM].

(Lon

1. Partition the closed interval (0,1) into a disjointcollection of subintervals (lck0 for i =N. For convenk ace, chose lc = (i-1)/N
N. If i = 0, thenand ko,,) = i/N for i = 1,
we include 0 in the interval (k,,k(1,1)].
2. For each field j and for each i 1, N, use the

Similarly we denote the conditional probability of y

1,given (a,b)EU by u(y).

Wo observe a vector of information Xa,b)associated with pair (a,b) and wish to designate apair as a link (denote the decision by A1), a possible
link (decision Az), cc a nonlink (decision A,). A
linkage rule L is defmed as a mapping from r, theratio
POP(yka.b* Oci,lcii.01 I M)

comparison space, onto a set of random decisionfunctions D = (d(y)) whered(y)P(4,(ya.b))e arvico4 I U),(2.1)

as the value of the adjusted weight curve for interval (koko,o). Here 'V is the string comparator, yi is a comparison of the jth field, (a,b)
is an arbitrary pair, M is the set of matches, andU the set of nonmatches.
3. If, for a fixed field j, the curves (step functions)
given by (2.1) are approximately the same forseveral data sets, then find a single piecewise
linear curve as the approximation for each of
them.

(KAIFY),KAA).P(AslY)); TET

and3

KAN) z 1.
i=1

There are two types of error associated with alinkage rule. A Tvoe I error occurs if an unmatched

4

The piecewise linear curve will have the agreement

weight as its highest value and the disagreement
weight as its lowest value. We use the newly

characters unassigned. Each suing has the same
number of assigned characters.

The number of transpositions is computed as

estimated curve on files for which the set of matches

follows: The first assigned character on one string

M is not known.
If the string comparators and associated methods
for modelling ratios (2.1) are reasonably accurate,then the resultant decision niles are optimal in theis compared to the first assigned character on theother suing. If the characters are not the same, halfof a transposition has occurred. Then the second
assigned character on one string is compared to thesecond assigned character on the other string, etc.

sense of Fellegi and Sunter (1969, Theorem).
2.3. Empirical Data Bases

The emprical files are the 1988 Dress Rehearsal
Census and Post Enumeration Survey (PES). The
geographic regions consisted of portions of St Louis,
MO, Columbia, MO, and rural Washington state.
Fields available for matching are first name, middle
initial, last name, house number, street name, ruralroute number, postal box number, conglomerated
addiess, telephone number, age, sex, marital status,
relationship to head of household, and race.
Individuals in the PES are generally only computer
matched with those individuals in the Census that arein the same block cluster.

A block cluster may

consist of a Census block or several blocks.
2.4. Suing Comparator Metrics
Jam (see e.g., Winkler 1985, 19259, Winkler and

The number of mismatched characters is divided by
two to yield the number of transpositions.
If two strings agree on a character-by-character

basis, then the Jam string comparator cr is set to
W1+W2+W which is the maximum value that Cr
can assume. The minimum value that the
can
which
occurswhen
thetwostrings
assume is 0,
have no characters in common (subject to the above
definition of common).
For present matching applications, W1, W2, andW,

are arbitrarily set to

1/3.

The new string

comparator metric basically modifies the basic string
comparator according to whether the first few

characters in the strings being compared agree. Specifically, for i = 1, 2, 3, 4,

Thibaudeau 1990) introduced a suing comparator
measure that gives values of partial agreement

0:11 =:11 +between two strings. The suing comparator accounts

if the firsti

0.1(1 - (1,)

characters agree.

for length of suings and partially wcounts for theIf w and w are the estimated agreement andtypes of errors typically made in alphanumeric strings

disagreement weights for a specific field, respectively,
then the Jam adjusted matching weight w, used in
the total weight calculation is given by

by human beings.

It is used in adjusting exact

agreement weights when two strings do not agree ona character-by-character basis.
Specifically, if c > 0,
Jaro string comparator is

w = 1 w,

if 4:, = 1, andmax ( w,-(w,-w.).(1-0).(9/2), Yid)
If 0 5 41. < 1.

cro = Wic/d + W2c/r +where

W, = weight associated with characters in
the first of two files,
W2 = weight associated with characters inthe second of two files,
W, = weight associated with transpositions,d = length of string in firstr = length of string in second file,
T = number of transpositions ofcharacters, andc = number of characters in common inpair of strings.
If c 0, then cro = O.
Two characters are considered in common only ifthey are no further apart than
(mt2 - 1) where m = max(d,r).
Characters incommon from two strings are assigned; remaining

The constant 9/2 controls how quickly decreases
in partial agreement values force the adjusted weightto the di.igreement weight

Instead of assuming that the same adjustment
procedure works for different fields such as first
name, last name. and house number, procedures formodelling the weight adjustment as a piecewise linear
function were developed. The procedures necessitate
having representative sets of pairs for which the truthof matches is known. The new adjusted weights w,
take the form

w, =

w,
if 0, b,max(w,-(wa-wd).(1-0,).(al), we)if b2 5 4:0 < bl,max ( w,-(w.-wd).(1-0.).(a2), we}

if cD, < b2.

5

(2.2)

on the specific type of string (such as first n applied.
Generally, al < al. The specific constants used are
given in Table 4 of section 3.1.

Table 2.

Table 1 provides examples of string comparator
values for pairs of last names and for pairs of firstnant :s. The abroms-abrams example with string
comparator value .9333 in contrast to the lampley-

campley with value .9048 shows that the string
comparator gives a higher value to the pair thatdiffers by a single character further from the rust
The martha-marhta example with value.9667 in contrast to the jonathon-jonathan example
with value .9583 shows that transposition of two

position.

characters causes less of a downweighting thandiffering by one character.

Table 1.

Values of String
Comparator d)shackleford
cunningham
campellnichleson
masseyabromagallowaylampleydixonfrederickmicheleshackelford
cunnigham
campbellnichulson
massieabramscalloway
campley
dicksonfredric
michellejesse

jessiemarthajonathanmarhtajonathonjuliesJeraldine
yvettetanya
dwaynejuluisgeraldine
yevett
tonya
duane

.9848
.9833
.9792
.9630
.9444
.9333
.9167
.9048
.8533
.9815
.9792
.9722
.9667
.9583
.9333
.9246
.9111
.8933
.8578

RESULTSThe results of calculating the ratio (2.1) for various
values of (b. for the rust name are given in Table 2
and for the last name in Table 3. The weights in thelast three columns correspond to disjoint iatervals of3.

the form (k1,k21 where k2 is given in column one.
Within a table, we observe that each of the curres has
roughly the same shape and the same starting andending values.
Using the constants associated with first name from

Table 4, the piecewise linear curve (2.2) for rustname approximates each of the weighting curves (stepfunctions) in Table 2. The constants and curves
azsociated with other fields such as Last name andhouse number are obtained in a similar manner.

String Comparator
Values and weights
First Name
StL

.62
.64
.66
.68
.70
.72
.74
.76
.78
.60
.82
.84
.86
.88
.90
.92
.94
.96
.98
.00

Table 3.

-4.52
-3.13
-2.87
-2.44
-0.92
-1.02
0.14
-0.22
0.88
0.83
2.10
2.25
2.31
3.05
3.46
3.77
4.27
4.42
5.48
4.62

NA
-3.40
-1.91
-2.50
-1.53
-1.61
-0.19
-0.96
0.27
0.63
2.14
1.72
2.93
2.53
3.19
3.09
3.56
5.03
5.04
4.58

Wash
-3.16
-3.06
-1.38
-2.39
-2.08
-0.43
0.28
-0.17
2.05
0.84
2.09
2.42
3.78
3.41
2.73
3.58
3.31
4.58
4.34
4.86

String Comparator
Values and Weights
Last Name
StL

.62
.64
.66
.68
.70
.72
.74
.76
.78
.80
.82
.84
.86
.88
.90
.92
.94
.96
.98
.00

Weights
Col

-5.35
-5.18
-5.21
-3.88

NA
-4.18
-3.76
-1.64
-1.53
-1.49
-0.47
0.02
0.10
1.08
1.08
1.14
1.13
1.29
1.63
1.35

Weights
Col
-5.57
-4.28
NA
-4.38
NA
NA
-2.95
-3.88
-2.85
-1.20
-0.65
0.45
0.36
1.07
1.00
0.69
1.40
1.22
1.52
1.08

Wash

NA
NA
NA
-3.19
NA
-3.70
-2.23
-1.55
0.11

-0.92
0.42
-0.46
0.04
0.31
1.43
1.33
1.40
1.11
1.70
0.70

Table 4. Constants Used in PieceWise Linear Weight
Ad'ustments
Field

a,

a2

b,

b,

first
last
house #

1.5
3.0
4.5

3.0
4.5
7.5

.92
.96
.98

.75
.88
.83

Weight adjustments are only performed for valuesof cD greater than 0.60. Values below 0.60 are
generally associated with pairs of strings associatedwith nonmatches in U.
The Jam weight adjustment is used for the street
field and any other fields that were not modelled.

improvement in matches can occur when string
comparators are first used (from param to param21.
The basic reason is that disagreements (on acharacter-by-character basis) are replaced by partial
agreements. Improvements due to the new string
comparators and weighting adjustments (from em toem2) are quite minor.

Table 5. Computer Categories
Various Procedures
10291 True Matches
12072 Records, St Louis
Pairs Agree on Cluster andFirst Character Surname 1/

The street field weighting adjustment was modelled in-computer designationmatchclericala manner similar to the last name, first name, andhouse numbers. The Jaro weighting adjustment isconservative because it generally downweights more
severely than the new curves and, thus, has less of atendency to assign greater than the full disagreement
weight to disagreeing strings.
3.2. Matching Comparison

truth->

A comparison of matching results is given in
Tables 5, 6, and 7 for St Louis, Columbia, and

em
em2
freq

Washington, respectively. To understand the tables,
we need describe the types of matching procedures.
The simplest procedure, crude, merely uses an ad hoc
guess for matching parameters and does not use string
comparators.
The next, param, does not use string comparators
but does estimate the probabilities m(y) and u(y).
Such probabilities are often estimated through an
iterative procedure that involves manual review ofmatching results and successive reuse of thereestimated parameters. The third type, Daram2, uses
the same pmbabilities as param and the basic string
cmnpratom.
The fourth type, em, uses an EM-Algorithm forestimating matching parameters (see e.g., Winkler
1988, Thibaudeau 1990) and uses the basic Jam string
comparator. The fifth type, en_ S., uses the EMderived weights and the new string comparator andnew weight adjustments. The fmal type, freg,
replaces simple agree/disagree weights for first nameand last name with frequency-based weights (see e.g.,
Winkler 1989) and also makes adjustments for joint
dependencies of agreements on first name, sex, andage.
In each table, the number of matches is determinedby a false match rate of 0.002. The crude and paramtypes are allowed to rise slightly above the 0.002
level because they genendly have higher error levels.
By examining the tables we observe that a dramatic

matchlnon-

matchlnon-'matchlmacch

crude

310/

1

93 44/7 94

paramparam27899/ 169276/ 23
9587/ 23
9639/ 24
9801/ 24

1863/198
545/191271/192
215/189
52/ 94

1/

Approximately 400 true matches
disagree on first character ofsurname and are nct eligible
for inclusion in the table.

Table 6. Computer Categories
Various Procedures
6984 True Matches
7649 Records, Columbia
Pairs Agree on Cluster andFirst Character Surname 1/
computer designation
clericalmatch
truth->
crude
param
param2
em
em2
freq
1/

matchlnon-

matchlnon-'match'match72429/6449/ 226655/ 136719/ 136762/ 136792/ 114327/119327/ 92
135/ 35
78/ 22
37/ 20
6/

9

Approximately 180 true matches
disagree on first character ofsurname and are not eligible forinclusion ir the table.

a

d

.

Table 7. Computer Categories
Various Procedures
1950 True Matches
2214 Records, Washington
Pairs Agree on Cluster andFirst Character Surname 1/
computer designation
clericalmatch
truth->

matchInonImatch

crude
param
param2
em
em2

freq
1/

1307/
1250/
1765/
1749/
1795/
1892/

'match
98
88
41

3
4

7/

9

5
4
4

Table 8. Proportional Agreement by
String Comparator Values
Key Fields by Geography

matchlnon564/
614/
134/
149/
107/

3

agreeing on a character-by-character basis (0=1.0)
are approximately 76 percent for first name andapproximately 86 percent for last name (Table 8).

First
On=1.0(bnkO .6

DISCUSSION
4.1. Quality of Empirical Data Bases
Because of the relatively large number ofidentifying fields for matching, all results in section
32 are relatively better than might be expected ingeneral matching applications. Also, having two key
4.

Col

Wash

0.75
0.93

0.82
0.94

0.75
0.93

0.85
0.95

0.88
0.96

0.86
0.96

Last
cron=1.029
29

Approximately 40 true matches
disagree on first character ofsurname and are not eligible
for inclusion in the table.

StL(bnkO .6

SUMMARY
This paper contains a new string comparator thatpartially accounts for minor typographical variation
when two strings are compared. The theoreticaldecision rules of Fellegi and Sunter (1969) am still_valid when general weighting adjustments accounting
for partial agreement are performed.
5.

*This paper reports general results of research by
Census Bureau staff. The views expressed are
attributable to the author and do not necessarilyreflect those of the Census Bureau.

fields such as first name and last name withtypographical variation sufficiently severe forassignment of full disagreement weight to a true
match is very rare (below 0.1 percent). The data are,however, representative of the type of data that will

be encountered during the 1990 Post Enumeration
S urvey .

The data are suitable for evaluating matchingprocedures because essentially all matches were foundand correctly identified. The identification is withcodes specifying to which record a record is matched.

All basic identifying information was carefully
checked and rechecked. In particular, no matches
were found among the set of code-identified
nonmatches using a variety of procedures.
4.2. General String Comparator Metrics
For matching applications of files having
significantly different characteristics (i.e., matching
fields) from those of the files of this paper, string
comparator weighting adjustments may have to be
remodelled.

In all matching situations, it seems likely thatmodelling partial agreement should improve matchingefficacy because the proportions of exact agreementon key matching fields can be quite low. For thefiles of this paper, the proportions of true matches

REFERENCES
Fellegi, I. P., and Sunter, A B. (1969), "A Theory for
Record Linkage," JASA 40 1183-1210.
Thibaudeau, Y. (1990), "Improving the Performanceof Comput3r Matching Algc. ithms thmugh Fetter
Choices of Parameters," paper presented a the
Annual ASA Meeting in kiaheim, Califoria.
Winkler, W. E. (1985), "Pre .ir ..cessing of Lists andString Comparison," in Record Linkash, techniques-1985, edited by W. Alvey and B. Kilss, U.S.
Internal Revenue Service, Publication 1299 (2-86),
181-187.
Winkler, W. E. (1988), "Using the EM Algorithm for
Weight Computation in the Fellegi-Sunter Model ofRecord Linkage," ASA 1988 Proceedings of theSection ori Survey Research Methods, 667-671.
Winkler, W. E. (1989), "Frequency-based Matching in
the Fellegi-Sunter Model of Record Linkage," ASA
1989 Proc. of the Section on Survey Research
Methods 788-793.
Winkler, W. E. and Thibaudeau, Y. (1990), "An
Application of the Fellegi-Sunter Model of Record
Linkage to the 1990 U.S. Census," technical report.

Appendix

END
U.S.

Dept.

of Education

Office of Education
Research andImprovement(OERI)

ERIC

Date Filmed
March 29,

1991

16