Database Reference
In-Depth Information
4
Query Types
There are two fundamental query types in string processing: Selections
and Joins. There are two fundamental query strategies: All-matches
and Top-
k
matches.
4.1 Selection Queries
All-match selection queries return all data strings whose similarity with
the query string is larger than or equal to a user specified threshold.
Definition 4.1 (All-Match Selection Query).
Given a string sim-
ilarity function Θ, a set of strings
S
, a query string
v
, and a positive
threshold
θ
, identify the answer set
A
=
{
s
∈
S
:Θ(
v,s
)
≥
θ
}
.
Top-
k
selection queries return, among all strings in the data, the
k
strings with the largest similarity to the query.
Definition 4.2 (Top-
k
Selection Query).
Given a string similarity
function Θ, a set of strings
S
, a query string
v
, and a positive integer
k
,
290
