Searching for database elements that are close or similar to a given query element is a problem that has a vast number of applications in many branches of computer science, and it is known as proximity search or similarity search. This type of search is a natural extension of the exact searching due to the fact that the databases have included the ability to store new data types such as images, sound, text, and so forth.
TopIntroduction
Searching for database elements that are close or similar to a given query element is a problem that has a vast number of applications in many branches of computer science, and it is known as proximity search or similarity search. This type of search is a natural extension of the exact searching due to the fact that the databases have included the ability to store new data types such as images, sound, text, and so forth.
Similarity search in nontraditional databases can be formalized using the metric space model (Baeza Yates, 1997; Chavez, Navarro, Baeza-Yates, & Marroquín, 2001; Chávez, & Figueroa, 2004). A metric space is a pair (X, d) where X is a universe of objects and d: X x X→ R+ is a distance function that quantifies the similarities among the elements in X. This function d satisfies the properties required to be a distance function:
- •
∀ x, y ∈ X, d(x,y) ≥ 0 (positiveness)
- •
∀ x, y ∈ X, d(x,y) =d(y,x) (symmetry)
- •
∀ x, y, z ∈ X, d(x,y) ≤ d(x,z)+ d(z,y) (triangle inequality)
A finite subset U ⊆ X, which will be called a database, is the set of objects where the search takes place.
A typical query in a metric database to retrieve similar objects is the range query, denoted by (q, r)d. Given a query q ∈ X and a tolerance radius r, a range query retrieves all elements from the database that are within a distance r to q; that is (q, r)d={ x / x ∈ U ∧ d(x, q) ≤ r}.
Range queries can be trivially answered by examining the entire database U. Unfortunately, this is generally very costly in real applications. In order to avoid this situation, the database is preprocessed by using an indexing algorithm. An indexing algorithm is an off-line procedure whose aim is to build a data structure or index designed to save distance computations at query time.
The metric spaces indexing algorithms are based on, first, partitioning the space into equivalence classes and, second, a subsequent indexation of each class. Afterward, at query time, some of these classes can be discarded using the index and an exhaustive search takes place only on the remaining classes. The difference among the existing indexing algorithms is the way they build up the equivalence relation. Basically, two groups can be distinguished: pivot-based algorithms and local partitioning algorithms.
Pivot-Based Algorithms
The idea behind the pivot-based algorithms is as follows. At indexing time, k pivots {p1, p2,..., pk} are selected from X and each database element u is mapped to a k-dimensional vector, which represents the respective distances to the pivots, that is, ϕ(u) = (d(u,p1), d(u,p2), ..., d(u,pk)). When a range query (q, r)d is issued, the triangle inequality is used together with the pivots in order to filter out elements in the database, without actually evaluating each distance to the query q. To do this, ϕ(q) = (d(q,p1), d(q,p2), ..., d(q,pk)) is computed; if |d(q,pi)-d(u,pi)| > r holds for any pivot pi, then, by the triangle inequality, we know that d(q,u)>r without actually evaluating d(q,u). Only those elements that cannot be discarded using this rule are actually compared against q.