6 SIMILARITY SEARCH
at reducing the number of distance computations are discussed in Section 7,
useful metric space transformations are presented in Section 8, and concepts of
approximate similarity search are explained in Section 9. Finally, Section 10
provides a collection of analytic tools and approaches especially developed for
metric index structures.
!• The Distance Searching Problem
Searching has always been one of the most prominent data processing op-
erations. However, exact-match retrieval, typical for traditional databases, is
neither feasible nor meaningful for data types in the present digital age. The
reason is that the constantly expanding data of modem digital collections lacks
structure and precision. Because of
this,
what constitutes a match to a request
is often different from that implied in more traditional, well-established areas.
A very useful, if not necessary, search paradigm is to quantify the proxim-
ity, similarity, or dissimilarity of a query object versus the objects stored in a
database to be searched. Roughly speaking, objects that are near a given query
object form the query response set. A useful abstraction for nearness is pro-
vided by the mathematical notion of metric space [Kelly, 1955]. We consider
the problem of organizing and searching large datasets from the perspective of
generic or arbitrary metric spaces, sometimes conveniently labelled distance
spaces. In general, the search problem can be described as follows:
PROBLEM 1.1 Let V he a
domain,
d a distance measure on
T>,
and (P, d) a
metric space. Given a set X C Vofn elements, preprocess or structure the
data so that proximity queries are answered
efficiently.
From a practical point of
view,
X can be seen as a file (a dataset or a collection)
of objects that takes values from the domain V, with d
as
the proximity measure,
i.e., the distance function defined for an arbitrary pair of objects from V. Though
several types of similarity queries exist and others are expected to appear in
the future, the basic types are known as the similarity range and the nearest
neighbor(s) queries.
In a distance space, the only possible operation on data objects is the com-
putation of a distance function on pairs of objects which satisfies the triangle
inequality. In contrast, objects in a
coordinate
space - coordinate space being a
special case of metric space - can be seen as vectors. Such spaces satisfy some
additional properties that can be exploited in storage (index) structure designs.
Naturally, the distance between vectors can be computed, but each vector can
also be uniquely located in coordinate space. Further, vector representation
allows us to perform operations like vector addition and subtraction. Thus, new
vectors can be constructed from prior vectors. For more information, see e.g.,
[Gaede and Günther, 1998, Böhm et al., 2001] for surveys of techniques that
exploit the properties of coordinate space.
我的内容管理
收起
我的收益 登录查看自己的收益
我的积分
登录查看自己的积分
我的C币
登录后查看C币余额
我的收藏 
我的下载 
下载帮助 
