Approximate Queries on String Collections
Xi h Y
Xiaochun
Yang
Institute of Computer Software and Theory
School of Information Science and Engineering
Northeastern University, CHINA
yangxc@mail.neu.edu.cn
ang c@mail ne ed cn
1Outline• What is approximate query?
• Q
Q-gramgram based algorithms• Our research results– VGRAM [VLDB’07]– Gram selection [SIGMOD’08][]

2

Example: a movie database

The user doesn’t know the exact spelling!
StarKeanu Reeves
Samuel Jackson
Schwarzenegger
Samuel Jackson

Title
The Matrix
Iron man
The Terminator
The manYear19992008
19842006

Genre
Sci-FiSci-Fi
SciFi
Sci-FiCrime
3

Gap between Queries and Data
Errors in the query
The user doesn’t remember a string exactly
The user unintentionally types a wrong string
Limited input device
Query: Schwarrzenger.

…

Data : Schwarzenegger…

4

Data integration and cleansing
Errors in the database:
Data often is not clean by itself, especially true in data
integration and cleansing
Typos, Web data, OCR

Relation R

Relation SStar
Keanu Reeves

StarKeanu Reeves

Samuel Jackson
Schwarzenegger

Samuel L. Jackson

Samuel Jackson

Samuel L. Jackson

Schwarzeneggergg5

Search engineg

6

Spell checking

77Approximate query• Approximate search• Approximate join

8Approximate searchCollection of strings sSearch
Query qSamule Jackson

StarKeanu Reeves
Samuel Jackson
Schwarzenegger
S
SamuellJ
Jacksonk…

Output: strings s that satisfy Sim(q,s)≤δ
9Approximate join
Collection R

Collection S

Jenny Stamatopoulou

Panos Ipirotis

John Paul McDougal

Jonh Smith

Aldridge Rodriguez
Panos Ipeirotis⋈…
Jenny Stamatopulou

John Smith

John P. McDougalg…

…

…

Al Dridge Rodriguez

Output: string pair that satisfy Sim(r,s)≤δ
10

Similarity functions• Edit distance• Jaccard similarity• Hamming distance• Cosine similarity• …

11Performance is a big issue• Answer queries interactively• Many queries on a server

Response timeThroughput

5ms/query
200 queries/second

20ms/query
50 queries/second12Outline• What is approximate query?
• Q
Q-gramgram based algorithms• Our research results– VGRAM [VLDB’07]– Gram selection [SIGMOD’08][]

13

“q-grams”
q grams of strings

universal

2-gramsV(s,q)(un, ni, iv, ve, er, rs, sa, al)String with length L → L - q + 1 q-grams
14

Similarity between gram sets

Set Sim JoinG
Gram
set

R

…

…

… microsoft
…
…
…

…

G
Gram
set

S

…

…

… mcrosoft
…
…
…

…

15

q-gram based
b d iinverted
d li
lists index
i d

id
0
1
2
3
4

strings
rich
stick
stich
stuck
static2-grams

atchhck
ic
ri
stta
ti
t
tu
uc

4
0

2

1
0
0
1
4
1
3
3

3
1

2

4

2

3

4

2

416

Approximate query processing• Query:Q“ hti k” ED(shtick,“shtick”,
ED( hti k ?)≤1# of common grams >= 3
sh ht ti ic ck

id
012
34strings
rich
stick
stich
stuck
static2-grams

atchhck
ic
ri
stta
ti
ttu
uc

40

2

100
1
41
3
3

3
12

4

2

34

2

4
17

22-grams
grams ->
> 33-grams?
grams?
• Query:Q“ hti k” ED(shtick,“shtick”,
ED( hti k ?)≤1
sht hti tic ick

id
0
1
2
34strings
rich
3-grams
stick
stich
stuck
staticati
ichick
ric
sta
sti
stu
tat
tic
tucuck# of common grams >= 140104134133222418

Observation 1: skew distributions of gram frequencies• DBLP: 276,699
276 699 article titles• Popular 5-grams: ation (>114K times), tions, ystem, catio

19

Observation 2: dilemma of choosing “q”• Increasing
Ii “q”“ ” causing:
iid0
1
2
3
4

– Longer grams Shorter lists– Smaller # of common grams of similar strings
4atchh20strings
ck13rich
ic0
1
242-grams
stick
ri0stichst4
2
31stuckta4staticti
1
24ttu
3uc
320

Motivation• Small index size (memory)• Small running time
– Scan matched inverted lists– Calculate ED(query, candidate)21

What we got?
• VLDB 2007
– VGRAM: Improving
pg Performance of Approximate
ppQueries on String Collections Using VariableLength
g Grams• SIGMOD 2008
– Cost-BasedC
B dV
Variable-Length-Grami bl LhG
SSelectionl ifor String Collections to Support
AApproximate
iQueries
Q i Effi
Efficientlyi l22

VGRAM: Main idea [VLDB07]• Grams withi h variable
i bl lengths
lh (between(bqmin anddqmax)– zebra• ze(123)– corrasion• co(5213), cor(859), corr(171)• Advantages– Reduce index size ☺
– Reducing running time ☺
– Adoptable by many algorithms ☺
23

Challenges• Generating variable-length grams?
• Constructing a high-quality
high quality gram dictionary?
• Relationship between string similarity and theirgram-set similarity?
i il i• Adopting
p g VGRAM in existingg algorithms?
g24

Challenge 1: String

Variable-length
Variablelength grams?

• Fixed-length
Fi d l th 2-grams
2universal• Variable-length grams[2 4] gram dictionary[2,4]-gramuniversal

niiivrsalunii
vers

25

RRepresenting
i gram didictionaryias a triei• Fixed-length
Fi d l th 2-grams
2universal• Variable-length grams[2 4] gram dictionary[2,4]-gramuniversal

nii
ivr
salunii
vers

26

Challenge 2: Constructing gram dictionary• selecting
l ti grams– Pruning trie using a frequency threshold T (e.g., 2)

27

Challenge 2: Constructing gram dictionary• selectingl ti grams– Pruning trie using a frequency threshold T (e.g., 2)

28

Final gram dictionary

Final grams

29

• VGRAM– Main idea
– Decomposing strings to grams– Choosing good grams–Effect of edit operations on grams– Adopting vgram in existing algorithms• Experiments

30

Challenge 3: Edit operation’s effect on grams

universal

Fixed length: qk operations could affect k * q grams

31

Deletion affects variable-length grams

Not affectedi-qmax+1

AffAffecteddi
Deletione et o

Not affectedi+qmax- 132

Grams affected by a deletion
AffAffected?
d?

i-qmax+1iDeletioni+qmax- 1[2,4]-grams

Deletion

universal
Aff t d?
Affected?

niivr
salunivers

33

# off grams affected
ff t d bby eachh operationti

Deletion/substitution

Insertion

0 1 1 1 1 2 1 2 2 2 1 1 1 2 1 1 1 1 0_u_n_i_v_e_r_s_a_l_34

# off grams affected
ff t d b
by k operationsti• k-Max: Summation of k largest values
NAG(s 2)=3+3=6
NAG(s,2)
3+3 6

12

32

3211biinding

Too pessimistic?
35

Tightening NAG(s,k)
NAG(s k) [SIGMOD[SIGMOD’08]08]• Dynamic programming: tightening NAG(s,k)– Subproblems: NAG(s[1,j],NAG(s[1 j] i)

opi
String s1j36

Dynamic programming• Recurrence function

B[ j ]

opi-1opi
String s1opi
j37

Dynamic programming

k=0
k=1
k=20001232321

1biinding0110220330340
350
350
350
35

NAG vector
38

Lower bound on # of common grams
Fi d length
Fixedlh (q)( )universalIf ed(s1,s2) <= k, then their # of common grams >=:(|s1|- q + 1) – k * q

Variable lengths:g# of ggrams of s1 – NAG(s1,k)
( , )
39

Challenge 4: adopting VGRAM
Easily adoptable by many algorithms
Basic interfaces:• String s grams• String s1,s1 s2 such that ed(s1,s2)
ed(s1 s2) <<= kmin # of their common grams
grams

stringgram dictionary

VGRAMllowerbboundd40

Example: algorithm using inverted lists• Query:Q““shtick”,h i k” ED(ED(shtick,h i k ?)≤1?) 1
shhttick

2-grams
2grams

…
ckic
…
ti
…

2-4
24 grams
Lower bound = 3

10

3
1

2

1

2

4

id
0
1
2
3
4

4

strings
rich
stick
stich
stuck
static…
ckiicich…
tictick
…

1
10

3
4
2

2
14

Lower bound = 141

Gram selection [SIGMOD[SIGMOD’08]
08]
C tb
Cost-basedd quantitative
tit ti approach
hAnalyze and estimate query performance when
adding each gram
Automatically find high-quality grams

Stringcollection

High quality gram
Gramdictionary42

Outline• Effects of adding a gram on index and queries• Cost-based
Cost based construction of gram dictionary• Experiments

43Effects on inverted lists
Gram dictionary
abbbc

add gram abc

Gram dictionary
abbc
abc

string--abc---ab---bc--

44

Effects on query performance• Decrease query’s inverted list
• Change lower bound• Change # of candidates

45Effects on query
query’ss inverted lists
Gram dictionary
abbbc

add gram abc

Gram dictionary
abbc
abc

Query Q- - - - - a- b- c- - - - - -Adding a new gram abc will not change or decrease
the query’s inverted lists

46

Effects on lower bound• Query: Q, ED(Q, ?)≤1
Query Q- - - - a b c d - - - - -Query Q- - - - a b c d - - - - -47

•

id strings
1 bingoEffects on lower bound2 bioinngbi i
3 bitingin
4 bitingg
Query: “bingon”, ED(bingon, ?)≤1
5 boing
6 going

Dictionar
yGram set: VG(Q)

D0{bi, in, ng, go, on}g) {{bi,, ing,g, go,g , on}}D1 ((+ ing)
D2 (+ bin) {bin, ing, go, on}|VG(Q)| NAG(Q,1) Lower bound54422232248

Effects on # of candidates• Change lower boundchange # of candidates
Gram dictionaryabGram dictionary
abbc

add ggram abc

bc
abc

Query Q- - - - a b c d - - - -- - - - a b c d - - - -49

id1
Effects of queries 2
34
56

QueryQbi
bingonbitting

Dictionary

Gram set
VG(Q)D0
D1 (+ ing)i )D2 (+ bin)D0
D1 (+ ing)
D2 (+ bin){bi, in, ng, go, on}{bi ing,{bi,igo, on}}{bin, ing, go, on}{bi, it, tt, ti, in, ng}{bi, it, tt, ti, ing }{bi, it, tt, ti, ing }strings
bingo
bi i
bioinng
bitingin
bitinggboing
going

Scanned Candidates
list size

19
11
8
21
13
12

1,2,3,4,61346
1,3,4,6
1,6
3,4
3,4
1,3,4 50

Outline• Effects of adding a gram on index and queries•
Cost-based construction of ggram dictionaryy• Experiments

51

C t t a gram diConstructdictionaryti[VLDB’07]

qmin=2qmax=452

C
Cost-basebconstruction
i [SIGMOD’08]

qmin=253

id123456strings
bingo
bioinng
bitingin
bitingboingggoing

Construct a gram dictionary
qmin=2n1bn2nn19
1 1n8o tn20 n 21
2 2n3oi

1233 3 44 421
234gion 9 n 10…

n 11

3 3nn 121234562132
435465no tin4n5tngon 13 n 14 n 15 n 16
3 3^
…4 4…

n6 n7iin 17 n 18
3 34 4654

Experiments -- Data sets

Data set

Stringg#Article Titles 277,000
Movie Titles 855,000
Actor Names 1,200,000

LengthgRange
g of # of
Min Max Avg injected edit
operations
6 207 66
[1,6]
8 249 35
[1,3]
4 74 17[1,2]

Environment:
GNU C++,C++ Dell GX620 PC with an Intel Pentium 2
2.40Hz40Hz Dual Core CPU,CPU
2GB memory, 250GB disk, Ubuntu (Linux) O.S.
55
Index structure were assumed to be in memoryImproving algorithm ProbeCount[VLDB’07]

Dataset 1: Person name56

Improving algorithm ProbeCluster[VLDB’07]

Dataset 1: Person name57

Improving algorithm PartEnum[VLDB’07]

Dataset 1: Person name58Comparison with algorithm Prune[SIGMOD’08]

Dataset: 1M article titles
Prune: qmin=5, qmax=7, T=2000, LargeFirst policy
GramGen: 1% sampling ratio, 2000 queries, (qmin=5 automatically determined)

59

Comparison with algorithm Prune[SIGMOD’08]

Prune: qmin=5, qmax=7, T=2000, LargeFirst policy
GramGen: 1% sampling ratio, 2000 queries, (qmin=5 automatically determined)

60

Conclusions• VGRAM + gram selection– variable-lengthva ab e e g– high-quality• Adoptable
Ad t bl ini existingi ti algorithms
l ith– Reduce index size
– Reduce running time61How to do research• UUse scientifici tifi methodth d62

How to do research• Real application -- Make your approach useful63How to do research
Work hardMk a diff
Makedifference

Enjoy your work

64

How to do research• Focus on detail• Be efficient• Beat the problem to death!

65Can we run faster?

66

Thank youy67