Example (edit distance)
r=1
query = “spire”, r = 1
peer 1
1 pier
d(“spire”, “parse”)
“shakespeare”)
“spare”)
=
=
> 35 +1
= 317 
1
piper
| d(“spire”, “parse”)
“spare”) –
d(“pier”, “spare”)
d(“parse”,
“spare”)| =| =
“parse”)
= | 31 – 024 | = 13 >
 31 +1
1
r=5
r=3
fare
tier
1
spier spire
pie
4
2
spare
3
2
parse
2
3
spore
paris
N0
(spare,5,0), (shakespeare,5,0) …
N1
r=5
shakespeare
N2
(pier,1,4) (parse,3,2) …
N3
(pier,0) (tier,1) (spier,1)
(pie,1) (piper,1) (peer,1)
…
N4
(parse,0) (spore,3) (fare,2)
(spire,3) (paris,2)
Sistemi Informativi LS
23