Database Reference
In-Depth Information
j
= ) and
given as part of the query predicate. The answer of a similarity join is composed of the concatenation
of tuples from
R
1
and
R
2
whose values
s
i
from attribute
S
j
and
s
m
from attribute
S
k
meet the join predicate.
There are basically three types of similarity joins, as follows.
an attribute
S
k
from the relation
R
2
, taken from the domains of attributes
S
j
and
S
k
(that is,
S R
[ (),
δ
ξ
]
S
Rq
j
q
k
•
Range join -
Ä
retrieves the pairs
of tuples <
t
i
, t
m
> from
R
1
and
R
2
whose values
s
i
from attribute
S
j
and
s
m
from attribute
S
k
satisfies
δ(
s
i
,s
m
) ≤
ξ
. An example is: “Select the European landscapes that differ from American landscapes
by at most 5 units”, represented as
: given a maximum query distance
ξ
, the query
R
⊗
R
1
2
europeanimage R
q
[ (),
δ
5
]
americanimage
ericanLandscapes
,
considering that both American and European landscapes are elements from the images domain.
EuropeanLandscapes
⊗
Am
S kCN
[ (),
δ
k S
]
kCNq
j
q
k
•
k
-Closest Neighbors join -
Ä
re-
trieves the
k
closest pairs of tuples <
t
i
, t
m
> from
R
1
and
R
2
, according to the distance function
δ
.
An example is: “Select the 20 most similar pairs of European and American landscapes”, repre-
sented as
: given an integer value
k
≥ 1, the query
R
⊗
R
1
2
europeanimage kCN
q
⊗
[ (),
δ
20
]
americanimag
e
EuropeanLandscapes
AmericanLandscapes
;
S kNN
[ (),
δ
k S
]
kNNq
j
q
k
•
k
-Nearest Neighbors join -
Ä
re-
trieves pairs of tuples <
t
i
, t
m
> from
R
1
and
R
2
, such that there are
k
pairs for each value
s
i
from
attribute
S
j
together with its nearest values
s
m
from attribute
S
k
, according to the distance function
δ
. An example is: “Select the 10 European landscapes that are the most similar to each American
landscape”, represented as
: given an integer value
k
≥ 1, the query
R
⊗
R
1
2
europeanimage kNN
q
⊗
[ (),
δ
10
]
americanimag
e
EuropeanLandscapes
AmericanLandscapes
.
The
k
-Nearest neighbor join is not commutative.
Figures 2 (e), (f) and (g) present an illustration of the three types of similarity joins described previ-
ously. In these figures, the white circles represent elements of the attribute
S
j
and the gray circles represent
elements of the attribute
S
k
.
Every similarity operator allows a number of variations, such as retrieving the most dissimilar ele-
ments instead of the most similar, and taking into account occurrences of ties in
k
-limited predicates.
Predicates can also be limited by both
k
and
ξ
, so the most restrictive condition is the one that applies.
Indexing Methods for Multimedia
From a system's perspective, not only the semantics must be fulfilled but also performance and usability
aspects are fundamental to the acceptance of an application, which are also gaps to be bridged (Deserno et
al., 2009]. Despite the fact that the queries described in the 'Similarity Queries' section can be answered
running a sequential search in the database, this is not the most appropriate strategy to be used in large
databases, once the computational cost involved can be very high. Therefore, another important issue to
