Receive a 20% Discount on All Purchases Directly Through IGI Global's Online Bookstore

Ana Valeria Villegas (Universidad Nacional de San Luis, Argentina), Carina Mabel Ruano (Universidad Nacional de San Luis, Argentina) and Norma Edith Herrera (Universidad Nacional de San Luis, Argentina)

Source Title: Handbook of Research on Innovations in Database Technologies and Applications: Current and Future Trends

Copyright: © 2009
|Pages: 9
DOI: 10.4018/978-1-60566-242-8.ch077

Chapter Preview

TopSearching 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.

The idea behind the pivot-based algorithms is as follows. At indexing time, *k* pivots {*p _{1}*,

LCS Distance: A distance function that applies to chains and returns the length of the common maximum subsequence between two chains.

Pagination Method: Method to store a data structure on disk pages in order to control the number of disk accesses to the secondary storage during search.

Metric Space: A universe of objects together with a distance function that measures the similarities between the elements in the universe.

Disk Page: A fixed-size portion of secondary storage corresponding to the amount of data transferred in a single access.

Disk Access: A disk page reading or writing operation.

Metric Database: A finite subset of a metric space.

Similarity Query: Searching for database elements that are close or similar to a given query object.

I/O Cost: Number of disk page reads or writes.

Indexing Algorithm: A procedure to build beforehand a data structure or index designed to speed up searches.

Search this Book:

Reset