A Pagination Method for Indexes in Metric Databases

A Pagination Method for Indexes in Metric Databases

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)
DOI: 10.4018/978-1-60566-242-8.ch077
OnDemand PDF Download:
$37.50

Abstract

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.
Chapter Preview
Top

Introduction

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 XR+ 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, yX, d(x,y) ≥ 0 (positiveness)

  • x, yX, d(x,y) =d(y,x) (symmetry)

  • x, y, zX, 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 qX 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 / xUd(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.

Key Terms in this Chapter

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.

Complete Chapter List

Search this Book:
Reset