Quick Overview of

Entity Extraction and Matching

Acknowledgement: Slides from ‘Principles of Data Integration Book by Anhai…

 Extraction Types
 Extracting from textual documents
– Extracting entities
– Extracting attributes
– Extracting relationships

 Extracting from template-based Web pages

– Wrapper-based extraction

 Extracting from pdf, Excel tables, images, etc.

 Other specialized types of extraction

– E.g., extracting a table

2
 IE from Text
For years, Microsoft
Corporation CEO Bill Select Name
Gates was against open From PEOPLE
source. But today he Where Organization = ‘Microsoft’
appears to have changed
his mind. "We can be
open source. We love the PEOPLE
concept of shared Name Title Organization
source," said Bill Veghte, Bill Gates CEO Microsoft
a Microsoft VP. "That's a Bill Veghte VP Microsoft
super-important shift for Richard Stallman Founder Free Soft..
us in terms of code
access.“

Richard Stallman, Bill Gates

founder of the Free
Software Foundation, Bill Veghte 3
countered saying… (from Cohen’s IE tutorial, 2003)
Two Main Approaches for Entity Extraction
 Hand-crafted rules
– Regexes
– Dictionary based
 Learning-based approaches

4
Dictionary based approach
 Goal: build a simple person-name extractor
– input: a set of Text Documents D, a list of names
– output: all mentions of names in D

 Simplified Person-Name extraction

– for each name e.g., David Smith
– generate variants: “David Smith”, “D. Smith”, “Smith, D.”, etc.
– clean the occurrences

Ambiguity may occur

 “Apple iPad Mini 16GB – Black”
 “Apple Juice by Minute Maid, 1 Gallon”

5
Extraction Accuracy Measured in Precision, Recall, F-1

6
 How Do We Do Extraction in
Practice?

 We want to extract person names from 1M documents

using a dictionary + regex approach
 How do we do this?

7
How Do We Do Extraction in Practice?

13
 Requirement Analysis Stage
 A common requirement
– P must be greater than a threshold, say 92%
– R must be as high as possible
 Why?
– Low precision results are often unusable
– Can throw human efforts into increasing R

9
 Development Stage
 Need to develop a good extractor
– Satisfies the app requirements
 Focus first on accuracy, then worry about time etc later
 For accuracy
– Two key concepts: development set and test set
– These are labeled sets
– Development set is used for creating, refining, debugging extractor
• Can be reused multiple times
– Test set is used for computing accuracy of extractor

10
A Typical Idealized Dev Process

11
 How to use the Dev Set?
 Things we want to do with the dev set
– Use it to create/refine/extend extractor E
– Use it to do a rough estimate of E’s accuracy and pinpoint problems with E

12
Now apply E to the rest of the documents
 Classification
Learning-Based IE
 An Example of Classification
 Let’s classify employees into good bachelor and bad
bachelor
– A table of employees
– Must label some
– Must create features and convert each example into a feature vector
– Learn a decision tree based on that

 Key concepts:
– Label, positive examples, negative examples
– Features, feature vector
– Training data, testing data
– A classification model, classification algorithm, hypothesis
– Training a classifier, applying a classifier
– Cross validation
– Examples of classification algorithms: decision tree, Naïve Bayesian,
SVM, random forest, neural networks
Feature Vectors, Training, & Testing

23
How to Use the Dev Set?

24
Overview of Entity Matching
 Illustrating Example: Entity Matching
S
R

Table A Table B
Name City State Name City State
Dave
Madison WI
Smith David D. Smith Madison WI

Joe Wilson San Jose CA Daniel W.

Middleton WI
Smith
Dan Smith Middleton WI
 Illustrating Example: Entity Matching
 Two fundamental steps: blocking and matching

Table A
Name City State

a1 Dave Smith Madison WI

a2 Joe Wilson San Jose CA

a3 Dan Smith Middleton WI (a1, b1) (a1, b1) +
block on (a1, b2) (a1, b2) -
match
Table B state = state (a3, b1) (a3, b1) -
Name City State (a3, b2) (a3, b2) +

b1 David D. Smith Madison WI

b2 Daniel W. Middleton WI
Smith
 Current Research / System Building Agenda for Entity Matching
Research
Focus on these two steps
• Develop algorithms
•Maximize accuracy, minimize cost
Assume other steps are trivial

Build stand-alone
monolithic systems

Blocker 1 Matcher 1
Blocker 2 Matcher 2
… …
 EM in practice is significantly more complex
– A messy, iterative, multiple-step process
– Many steps perceived trivial are actually quite difficult to do
– Even if we let a human user be in charge of the whole EM process, he/she often doesn’t know what to do
 How is EM Done Today in Practice?
1M tuples

block match
1M tuples
(using supervised learning)
B

 Development stage
– finds an accurate workflow, using data samples
 Production stage
– executes workflow on entirety of data
– focuses on scalability
 Development Stage
no
A (-,-) (-,-) +
A’
blocker
(-,-)
matcher
(-,-) +
quality yes
sample (-,-) (-,-) -
X (-,-) V (-,-) - check
B’ (-,-) (-,-) +
B
S
A’ (-,-)
blocker Cx sample (-,-)
X (-,-)
B’
label
cross-validate G
matcher U
A’ 0.89 F1 (-,-) +
blocker Cy (-,-) -
Y 0.93 F1 (-,-) +
B’ cross-validate
matcher V

Select the best blocker: X, Y Select the best matcher: U, V

 Production Stage

(-,-) (-,-) +
(-,-) (-,-) -
A (-,-) (-,-) +
(-,-) (-,-) +
blocker X matcher V
(-,-) (-,-) -
(-,-) (-,-) +
B (-,-) (-,-) -
(-,-) (-,-) +

Must worry about scaling, quality monitoring, exception handling, …

 Methods for
Data Matching and Cleansing

Slides taken from Anhai’s book on Data Integration

 Introduction
 Find strings that refer to same real-world entities
– “Venketesh Vishwanathan” and “Venktesh Vishvanathan”
– “Room-108, Student Residence, IIITD, Delhi 20” and “Room# 108, IIIT-D,
Okhla Phase 3, New Delhi 110020”

 Play critical roles in Data Integration tasks

– Schema matching, data matching, information extraction

 Similarity measures
– Sequence-based: edit distance, Needleman-Wunch, affine gap, Smith-
Waterman, Jaro, Jaro-Winkler
– Set-based: overlap, Jaccard, TF/IDF
– Hybrid: generalized Jaccard, soft TF/IDF, Monge-Elkan
– Phonetic: Soundex

 Scaling up string matching

– Inverted index, size filtering, prefix filtering, position filtering, bound filtering
 Problem Description

• Given two sets of strings X and Y

• Find all pairs xεX and yεY that refer to the same real-world entity
• We refer to (x,y) as a match
• Example

• Two major challenges: accuracy & scalability

26
Accuracy Challenges

• Matching strings often appear quite differently

• Typing and OCR errors: David Smith vs. Davod Smith
• Different formatting conventions: 10/8 vs. Oct 8
• Custom abbreviation, shortening, or omission:
Harpreet Kaur vs Hary Singh Kaur,
Debjoot Vohara vs Deb Vhora
Daniel Walker Herbert Smith vs. Dan W. Smith
• Different names, nick names: William Smith vs. Bill Smith
• Shuffling parts of strings: Dept. of Computer Science, IIIT
Delhi vs. Computer Science Dept., IIIT-D

27
Accuracy Challenges

• Solution:
• Use a similarity measure s(x,y) ε [0,1]
• The higher s(x,y), the more likely that x and y match
• Declare x and y matched if s(x,y) ≥ t
• Distance measure/cost measure have also been used
• smaller values  higher similarities

28
Scalability Challenges

Applying s(x,y) to all pairs is impractical

• Quadratic in size of data
Solution: apply s(x,y) to only most promising pairs, using a method

FindCands
For each string x ε X
use method FindCands to find a candidate set Z  Y
for each string y ε Z
if s(x,y) ≥ t then return (x,y) as a matched pair

We discuss ways to implement FindCands later

29
Outline

• Problem description
• Similarity measures
• Sequence-based: edit distance, Needleman-Wunch, affine gap,
Smith-Waterman, Jaro, Jaro-Winkler
• Set-based: overlap, Jaccard, Sorensen-Dice, TF/IDF
• Similarity-based: Ratcliff-Obershelp similarity
• Phonetic: Soundex
• Scaling up string matching
• Inverted index, size filtering, prefix filtering, position filtering.

30
Edit Distance

• Also known as Levenshtein distance

• d(x,y) computes minimal cost of transforming x into y,
using a sequence of operators, each with cost 1
• Delete a character
• Insert a character
• Substitute a character with another
• Example: x = David Smiths, y = Davidd Simth,
d(x,y) = 4, using following sequence
• Inserting a character d (after David)
• Substituting m by i
• Substituting i by m
• Deleting the last character of x, which is s 31
Edit Distance

• Models common editing mistakes

• Inserting an extra character, swapping two characters, etc.
• So smaller edit distance  higher similarity
• Can be converted into a similarity measure
• s(x,y) = 1 - d(x,y) / [max(length(x), length(y))]
• Example
• s(David Smiths, Davidd Simth) = 1 – 4 / max(12, 12) = 0.67

32
Computing Edit Distance using Dynamic
Programming
• Define x = x1x2… xn, y = y1y2… ym
• d(i,j) = edit distance between x1x2… xi and y1y2… yj, the ith and jth
prefixes of x and y
• Recurrence equations

33
Example

• x = dva, y = dave
y0 y1 y2 y3 y4 y0 y1 y2 y3 y4
d a v e d a v e x=d–va

x0 0 1 2 3 4 x0 0 1 2 3 4 y=dave
x1 d 1 0 1 x1 d 1 0 1 2 3
substitute a with e
x2 v 2 x2 v 2 1 1 1 2 insert a (after d)
x3 a 3 x3 a 3 2 1 2 2

34
The Jaro Measure

• Mainly for comparing short strings, e.g., first/last names

• To compute jaro(x,y)
• find common characters xi and yj such that
• xi = yj and |i-j| ≤ min {|x|,|y|}/2
• intuitively, common characters are identical and positionally
“close to each other”
• if the i-th common character of x does not match the i-th
common character of y, then we have a transposition
• return jaro(x,y) = 1 / 3[c/|x| + c/|y| + (c – t/2)/c], where c is the
number of common characters, and t is the number of
transpositions

35
The Jaro Measure: Examples

• x = jon, y = john
• c = 3 because the common characters are j, o, and n
• t=0
• jaro(x,y) = 1 / 3(3/3 + 3/4 + 3/3) = 0.917
• contrast this to 0.75, the similarity score of x and y using edit
distance
• x = jon, y = ojhn
• c = 3 because the common characters are j, o, and n
• t=2
• common char sequence in x is jon
• common char sequence in y is ojn
• jaro(x,y) = 0.81 36
The Jaro-Winkler Measure

• Captures cases where x and y have a low Jaro score,

but share a prefix  still likely to match
• Computed as
• jaro-winkler(x,y) = (1 – PL*PW)*jaro(x,y) + PL*PW
• PL = length of the longest common prefix
• PW is a weight given to the prefix

• Exercise: Compute the edit distance between

“Vishwanathan” and “Vishvnahtan” using Levenshtein, Jaro
and Jaro-Winkler. Here PW=0.1

37
Outline

• Problem description
• Similarity measures
• Sequence-based: edit distance, Needleman-Wunch, affine gap,
Smith-Waterman, Jaro, Jaro-Winkler
• Set-based: overlap, Jaccard, Sorensen-Dice, TF/IDF
• Similarity-based: Ratcliff-Obershelp similarity
• Phonetic: Soundex
• Scaling up string matching
• Inverted index, size filtering, prefix filtering, position filtering,
bound filtering
49
Set-based Similarity Measures
• View strings as sets or multi-sets of tokens
• Use set-related properties to compute similarity scores
• Find the similar tokens in both sets. More the number of common
tokens, more is the similarity between the sets.
• Common methods to generate tokens
• consider words delimited by space
• possibly stem the words (depending on the application) [catch, catchy,
catcher,..)
• remove common stop words (e.g., the, and, of)
• e.g., given “david smith”  generate tokens “david” and “smith”
• consider n-grams, substrings of length n
• e.g., “david smith”  the set of 3-grams are {##d, #da, dav, avi, …, h##}

• special character # is added to handle the start and end of string.

The Overlap Measure

• Let Bx = set of tokens generated for string x

• Let By = set of tokens generated for string y
• O(x,y) = |Bx ⋂ By|
• returns the number of common tokens
• E.g., x = dave, y = dav
• Bx = {#d, da, av, ve, e#}, By = {#d, da, av, v#}
• O(x,y) = 3

40
The Jaccard Measure

• J(x,y) = |Bx ⋂ By|/|Bx ⋃ By|

• E.g., x = dave, y = dav
• Bx = {#d, da, av, ve, e#}, By = {#d, da, av, v#}
• J(x,y) = 3/6
• Very commonly used in practice

41
The TF/IDF Measure: Motivation

• uses the TF/IDF notion commonly used in IR

• two strings are similar if they share distinguishing terms
• e.g., x = Apple Corporation, CA
y = IBM Corporation, CA
z = Apple Corporation
• s(x,y) > s(x,z) using edit distance or Jaccard measure, so x is
matched with y  incorrect
• TF/IDF measure can recognize that Apple is a distinguishing
term, whereas Corporation and CA are far more common 
correctly match x with z

42
Term Frequencies and
Inverse Document Frequencies
• Each string is converted into a bag of terms called a
document
• Define term frequency tf(t,d) = number of times term t
appears in document d
• Define inverse document frequency idf(t) = N / Nd, number
of documents in collection divided by number of documents
that contain t
• A higher value of IDF means that the occurrence of the term is more
distinguishing.
• note: in practice, idf(t) is often defined as log(N / Nd), here we will use
the above simple formula to define idf(t)
43
Example

44
Feature Vectors

• Each document d is converted into a feature vector vd

• vd has a feature vd(t) for each term t
• value of vd(t) is a function of TF and IDF scores
• here we assume vd(t) = tf(t,d) * idf(t)

45
TF/IDF Similarity Score

46
Outline

• Problem description
• Similarity measures
• Sequence-based: edit distance, Needleman-Wunch, affine gap,
Smith-Waterman, Jaro, Jaro-Winkler
• Set-based: overlap, Jaccard, Sorensen-Dice, TF/IDF
• Similarity-based: Ratcliff-Obershelp similarity
• Phonetic: Soundex
• Scaling up string matching
• Inverted index, size filtering, prefix filtering, position filtering,
bound filtering

47
Sequence based -- Ratcliff-Obershelp similarity

1. Find the longest common substring from the two strings.

2. Remove that part from both strings, and split at the same location.
This breaks the strings into two parts, one left and another to the
right of the found common substring.
3. Now take the left part of both strings and call the function again to
find the longest common substring.
4. Repeat this for the right part.
5. Repeat Steps 1 to 4 recursively until the size of any broken part is
less than a default value.

The similarity score = 2*the number of characters found in common/

the total number of characters in the two strings
48
Example
S1 = M A T H E M A T I C S
S1: MKUESHMOHANIA
S2 = M A T E M A T I C A
S2: MUKHESHMOHANIYA

Step 1: Common substring - E M A T I C

S1 = M A T H E M A T I C S
S2 = M A T E M A T I C A

Step 2: Left String 1: M A T H Left String 2: M A T

Right String 1: S Right String 2: A

Step 3: Common substring in left string: M A T

S1 = M A T H E M A T I C S
S2 = M A T E M A T I C A
Step 4: None
Step 5: Algorithm terminates

Similarity score = 2*9/(11+10) = 0.857 61

Outline

• Problem description
• Similarity measures
• Sequence-based: edit distance, Needleman-Wunch, affine gap,
Smith-Waterman, Jaro, Jaro-Winkler
• Set-based: overlap, Jaccard, Sorensen-Dice, TF/IDF
• Similarity-based: Ratcliff-Obershelp similarity
• Phonetic: Soundex

• Scaling up string matching

• Inverted index, size filtering, prefix filtering, position filtering,
bound filtering

50
Phonetic Similarity Measures

• Match strings based on their sound, instead of

appearances
• Very effective in matching names, which often appear in
different ways that sound the same
• e.g., Banarjee, Benerji, Banergi; Meyer, Meier, Myir , Mier, and Mire;
Smith, Smithe, and Smythe
• Soundex is most commonly used

51
The Soundex Measure
• Used primarily to match surnames
• maps a surname x into a 4-letter code
• two surnames are judged similar if share the same code
• Algorithm to map x into a code:
• Step 1: keep the first letter of x, subsequent steps are
performed on the rest of x
• Step 2: remove all occurences of W and H. Replace the
remaining letters with digits as follows:
• replace B, F, P, V with 1, C, G, J, K, Q, S, X, Z with 2, D, T with 3, L with 4, M, N
with 5, R with 6
• Step 3: replace sequence of identical digits by the digit itself
• Step 4: Drop all non-digit letters, return the first four letters as the
Soundex code 65
The Soundex Measure
• Example: x = Ashcraft
• after Step 2: A226a13,
• after Step 3: A26a13,
• Step 4 converts this into A2613, then returns A261
• Soundex code is padded with 0 if there is not enough digits
• Example: Robert and Rupert map into R163
• Soundex fails to map Gough and Goff, and Jawornicki
and Yavornitzky
• designed primarily for Caucasian names, but found to work well
for names of many different origins
• does not work well for names of East Asian origins
• which uses vowels to discriminate, Soundex ignores vowels
53
Outline

• Problem description
• Similarity measures
• Sequence-based: edit distance, Needleman-Wunch, affine gap,
Smith-Waterman, Jaro, Jaro-Winkler
• Set-based: overlap, Jaccard, Sorensen-Dice, TF/IDF
• Similarity-based: Ratcliff-Obershelp similarity
• Phonetic: Soundex
• Scaling up string matching
• Inverted index, size filtering, prefix filtering, position filtering

54
Computing similarity between two strings/record/documents -
- Naïve Solution

• All pair-wise comparison between A and B

For x in A: A, B: table
x, y: record as set
For y in B:
If sim(x,y) > t, return (x,y);

• Nested-loop: |A||B| comparisons

• The sim() evaluation may be costly

55
Naïve Solution Example
A B
ID Content ID Content
1 {Lake, Mendota} 4 {Lake, Monona, University}
2 {Lake, Monona, Area} 5 {Monona, Research, Area}
3 {Lake, Mendota, Monona, Dane} 6 {Lake, Mendota, Monona, Area}

O(x,y) > 2 ?

O(x,y) ID=4 ID=5 ID=6

ID=1 1 0 2
ID=2 2 2 3
ID=3 2 1 3

56
Naïve Solution Example
A B
ID Content ID Content
1 {Lake, Mendota} 4 {Lake, Monona, University}
2 {Lake, Monona, Area} 5 {Monona, Research, Area}
3 {Lake, Mendota, Monona, Dane} 6 {Lake, Mendota, Monona, Area}

J(x,y) > 0.6 ?

J(x,y)) ID=4 ID=5 ID=6

ID=1 0.25 0 0.5
ID=2 0.5 0.4 0.75
ID=3 0.2 0.16 0.6

57
 Scalability Challenges

• Applying s(x,y) to all pairs is impractical

• Quadratic in size of data
• Solution: apply s(x,y) to only most promising pairs, using a
method FindCands
• For each string x ε X
• use method FindCands to find a candidate set Z  Y for
each string y ε Z
• if s(x,y) ≥ t then return (x,y) as a matched pair
• This is often called a blocking solution
• We now discuss ways to implement FindCands
• using Jaccard and overlap measures for now
58
2-Step Framework

• Step 1: “Blocking”
• Using Index/heuristics/filtering/etc, reduce # of candidates to
compare
• Step 2: sim() only within candidate sets
For x in A:
Using Foo, find a candidate set C in B
For y in C:
If sim(x,y) > t, return (x,y);

59
Variants for “Foo”

• “Foo”: How to identify candidate set C

• Fast
• Accurate: no false positives/negatives
• Many Variants for “Foo”
• Inverted Index
• Size filtering
• Prefix Index
• Prefix + Inverted Index
• Position Index

60
Inverted Index over Strings [Sarawagi et al, SIGMOD 04]

• Convert each string yεY into a document, build an

inverted index over these documents
• Given term t, use the index to quickly find documents
of Y that contain t

61
Inverted Index [Sarawagi et al, SIGMOD 04]
A B
ID Content ID Content
1 {Lake, Mendota} 4 {Lake, Monona, University}
2 {Lake, Monona, Area} 5 {Monona, Research, Area}
3 {Lake, Mendota, Monona, Dane} 6 {Lake, Mendota, Monona, Area}

Inverted Index (IDX) for A Inverted Index (IDX) for B

Token in A ID List Token in B ID List
Area 2 Area 5, 6
Dane 3 Lake 4, 6
Lake 1, 2, 3 Mendota 6
Mendota 1, 3 Monona 4, 5, 6
Monona 2, 3 Research 5
University 4
76
Inverted Index [Sarawagi et al, SIGMOD 04]
A B
ID Content ID Content
1 {Lake, Mendota} 4 {Lake, Monona, University}
2 {Lake, Monona, Area} 5 {Monona, Research, Area}
3 {Lake, Mendota, Monona, Dane} 6 {Lake, Mendota, Monona, Area}

For x in A: Inverted Index (IDX) for B

Using IDX, find a candidate set C in B
Token in B ID List
For y in C:
If sim(x,y) > t, return (x,y); Area 5
Lake 4, 6
ID=1: {Lake, Mendota} Mendota 6
Monona 4, 5, 6
ID=2: …
Candidate set C: Research 5
ID=3: … {4,6} + {6} = {4, 6}
University 4
63
Inverted Index [Sarawagi et al, SIGMOD 04]
A B
ID Content ID Content
1 {Lake, Mendota} 4 {Lake, Monona, University}
2 {Lake, Monona, Area} 5 {Monona, Research, Area}
3 {Lake, Mendota, Monona, Dane} 6 {Lake, Mendota, Monona, Area}

For x in A: Inverted Index (IDX) for B

Using IDX, find a candidate set C in B
Token in B ID List
For y in C:
If sim(x,y) > t, return (x,y); Area 5
Lake 4, 6
ID=1: {Lake, Mendota} Mendota 6
Monona 4, 5, 6
ID=2: … ID Freq.
Candidate set C: Research 5
4 1
ID=3: …
O(x,y) > 2 6 University
2 4
64
Limitations

• The inverted list of some terms (e.g., stop words) can

be very long  costly to build and manipulate such lists
• Requires enumerating all pairs of strings that share at
least one term. This set can still be very large in
practice.

65
Size Filtering [Arasu et al,VLDB 06]

• Retrieves only strings in Y whose sizes make them

match candidates
• given a string xε X, infer a constraint on the size of strings in Y
that can possibly match x
• uses a B-tree index to retrieve only strings that satisfy size
constraints
• E.g., for Jaccard measure J(x,y) = |x ⋂ y| / |x ⋃ y|
• assume two strings x and y match if J(x,y) ≥ t
• 1/J(x,y) ≥ 1 ≥ |y|/|x| ≥ 1 ≥ J(x,y)
• can show that given a string xε X, only strings y such that
• |x|/t ≥ |y| ≥ |x|*t can possibly match x
66
Example

,6

• Consider x = {lake, mendota}. Suppose t = 0.8

• If yε Y matches x, we must have
• 2/0.8 = 2.5 ≥ |y| ≥ 2* 0.8 = 1.6
• no string in Set Y satisfies this constraint  no match
67
 Prefix Filtering [Chaudhuri et al, ICDE 06]

• Key idea: if two sets share many terms  large subsets of them
also share terms
• Consider overlap measure O(x,y) = |x ⋂ y|
• if |x ⋂ y| ≥ k  any subset x’  x of size at least |x| - (k – 1) must
overlap y
• For J(x,y), any subset x’  x of size at least |x| - (k– 1) must overlap y,
г
where k = |x|*t˥
• To exploit this idea to find pairs (x,y) such that O(x,y) ≥ k
• given x, construct subset x’ of size |x| - (k – 1)
• use an inverted index to find all y that overlap x’
68
 Example

• Consider matching using O(x,y) ≥ 2

• x2 = {lake, monona, area}, let x2’ = {lake, monona}
• Use inverted index to find {y4, y6} which overlaps with x2’.

69
 Prefix-Inverted Index:
Selecting the Subset Intelligently [Bayardo et al,WWW 07]

• Recall that in Prefix Filtering we select a subset x’ of x and check

its overlap with the entire set y
• We can do better by selecting a particular subset x’ and
checking its overlap with only a particular subset y’ of y
• How?
• impose an ordering O over the universe of all possible terms in increasing
frequency
• reorder the terms in each x ε X and y ε Y according to O
• select subset x’ that contains the first n terms of x as the prefix of
size n of x
• if |x ⋂ y| ≥ k, then x’ and y’ must overlap, where x’ is the prefix
of size |x| - (k – 1) of x and y’ is the prefix of size |y| - (k – 1) of y.
70
 Prefix + Inverted Index [Bayardo et al,WWW 07]

A B
ID Content ID Content
1 {Lake, Mendota} 4 {Lake, Monona, University}
2 {Lake, Monona, Area} 5 {Monona, Research, Area}
3 {Lake, Mendota, Monona, Dane} 6 {Lake, Mendota, Monona, Area}

Token ID List TF Order

Inverted Index (IDX)
for both A and B Area 2, 5, 6 3 4
Dane 3 1 1
Lake 1, 2, 3, 4, 6 5 6
Create a universal order: Mendota 1, 3, 6 3 5
Put rare tokens front Monona 2, 3, 4, 5, 6 5 7
Research 5 2
Order: Dane > Research > Uni versity > Area > Mendota > L ake > Monona
University 14 1 3
Prefix + Inverted Index [Bayardo et al,WWW 07]

Ordered A Ordered B
ID Content ID Content
1 {Mendota, Lake} 4 {University, Lake, Monona}
2 {Area, Lake, Monona} 5 {Research, Area, Monona}
3 {Dane, Mendota, Lake, Monona} 6 {Area, Mendota, Lake, Monona}

Order: Dane > Research > University > Area > Mendota > Lake > Monona
Prefix + Inverted Index [Bayardo et al,WWW 07]

Ordered A Ordered B
ID Content ID Content
1 {Mendota, Lake} 4 {University, Lake, Monona}
2 {Area, Lake, Monona} 5 {Research, Area, Monona}
3 {Dane, Mendota, Lake, Monona} 6 {Area, Mendota, Lake, Monona}

O(x,y) > 2
Prefix Inverted Index for B
Prefix(x)=|x|-(k-1)=|x|-1
Token in B ID List
Area 5, 6
Lake 4, 6
ID=1: {Mendota, Lake} Mendota 6
Research 5
ID=2: …
Candidate set C: {6} University 4
ID=3: …
Prefix + Inverted Index [Bayardo et al,WWW 07]

Ordered A Ordered B
ID Content ID Content
1 {Mendota, Lake} 4 {University, Lake, Monona}
2 {Area, Lake, Monona} 5 {Research, Area, Monona}
3 {Dane, Mendota, Lake, Monona} 6 {Area, Mendota, Lake, Monona}

O(x,y) > 2
Prefix Inverted Index for B
Prefix(x)=|x|-(k-1)=|x|-1
Token in B ID List
Area 5
Lake 4, 6
ID=1: …
Mendota 6
ID=2: {Area, Lake, Monona} Research 5
Candidate set C: University 4
ID=3: …
{5} + {4,6} = {4,5,6}
Prefix + Inverted Index [Bayardo et al,WWW 07]

Ordered A Ordered B
ID Content ID Content
1 {Mendota, Lake} 4 {University, Lake, Monona}
2 {Area, Lake, Monona} 5 {Research, Area, Monona}
3 {Dane, Mendota, Lake, Monona} 6 {Area, Mendota, Lake, Monona}

O(x,y) > 2
Prefix Inverted Index for B
Prefix(x)=|x|-(k-1)=|x|-1
Token in B ID List
ID=1: … Area 5
Lake 4, 6
ID=2: …
Mendota 6
ID=3: {Dane, Mendota, Research 5
Lake, Monona}
Candidate set C: University 4
{6} + {4,6} = {4,6}
if |x ⋂ y| ≥ k, then x’ and y’ must overlap, where x’ is the prefix of
size |x| - (k – 1) of x and y’ is the prefix of size |y| - (k – 1) of y.

Proof:

Prefix Suffix

Suppose x’⋂y’=Φ  x’⋂y”≠Φ (otherwise |x⋂y|≥k will not hold)

∃u: uεx’ and uεy” and similarly ∃v: vεy’ and vεx”
uεx’ and vεx” , u<v in the ordering O
But vεy’ and uεy”, means v<u –> contradiction 76
This x’ overlaps with y’
 Selecting the Subset Intelligently

• Algorithm
• reorder terms in each x ε X and y ε Y in increasing order of their
frequencies
• for each y ε Y, create y’, the prefix of size |y| - (k – 1) of y
• build an inverted index over all prefixes y’
• for each x ε X, create x’, the prefix of size |x| - (k – 1) of x, then
use above index to find all y such that x’ overlaps with y’

77
 Position Index [Xiao et al,WWW 08]
Further limits the set of candidate matches by deriving an upper bound on
the size of overlap between x and y
Order: Dane > Research > University > Area > Mendota > Lake > Monona

• x: {Dane, Research, Area, Mendota, Lake}

• y: {Research, Area, Mendota, Lake, Monona}
• O(x,y) > 4 ?

• Prefix(x) = Prefix(y) = 5 – (4 -1) = 2
• x: {Dane, Research, Area, Mendota, Lake}
• y: {Research, Area, Mendota, Lake, Monona}
• “Research” is a common prefix  (x,y) is a candidate pair using a
Prefix Filtering + Inverted Index method
•  need to compute sim(x,y)
• Estimation of max overlap = overlap in prefixes + min of unseen tokens
= 1 + min(3,3) = 4 > k  No need to compute sim(x,y) ! 78
Summary
• String matching is pervasive in data integration
• Two key challenges:
• what similarity measure and how to scale up?
• Similarity measures
• Sequence-based: edit distance, Needleman-Wunch, affine gap,
Smith-Waterman, Jaro, Jaro-Winkler
• Set-based: overlap, Jaccard, Sorensen-Dice, TF/IDF
• Similarity-based: Ratcliff-Obershelp similarity
• Phonetic: Soundex
• Scaling up string matching
• Inverted index, size filtering, prefix filtering, position filtering.
Acknowledgment

Slides in the scalability section are adapted from

[Link]

94