Database Reference
In-Depth Information
Algorithm 8.3.5:
JoinQuery(
N
1
,N
2
,θ
)
if
N
1
and
N
2
are leaf nodes
for each
s
∈
N
1
and
r
∈
N
2
do
if
Edit Distance Verification
(
s, r, θ
)
do
do
Insert (
s, r
) into the result
else
for
child node
N
i
of
N
1
and child node
N
j
of
N
2
for all
intervals [
s
l
,s
u
]
N
i
,
[
r
l
,r
u
]
∈
∈
N
j
do
if
LB
([
s
i
,s
i
]
,
[
s
j
,s
j
])
do
do
≤
θ
do
JoinQuery
(
N
i
,N
j
,θ
)
Table 8.2. Necessary properties with respect to query type and dis-
tance function.
Range
Top-
k
All-Match Join
Edit Distance
P8.1,P8.2
P8.1,P8.2
P8.1,P8.3
Normalized E.D.
P8.1,P8.2,P8.4
P8.1,P8.2,P8.4
P8.1,P8.3,P8.4
structure seamlessly supports both edit distance and normalized edit
distance, if the underlying string order is consistent with these prop-
erties. We summarize the necessary properties the mapping function
φ
needs to have in order to be able to support the three types of string
similarity queries based on edit distance and normalized edit distance
in Table 8.2.
8.3.2.1
Dictionary order
Dictionary Order
is the most straightforward choice for the string
order. Dictionary order obeys comparability, lower bounding, and
pairwise lower bounding. It does not satisfy length bounding. There-
fore, it can be used to index on edit distance for range, top-
k
, and
all-match join queries.
Given an alphabet Σ, there is a pre-defined order on all letters in
Σ, i.e.,
. We simply assume that the index of
σ
i
in Σ
can be calculated by the permutation function
π
(
σ
i
). Then, we map the
{
σ
1
,σ
2
,...,σ
|
Σ
|
}
