Database Reference
In-Depth Information
Similarity Evaluation
Similarity evaluation requires a sequence of computational tasks that results in a value quantifying how
close two multimedia objects are. In the philosophical and the psychological literature, the notion of
similarity space
states that the mind embodies a representational hyperspace. In this space, dimensions
represent ways in which objects can be distinguished, points represent possible objects and distances
between points are inversely proportional to the perceived similarity between those objects (Gauker, 2007).
When dealing with multimedia data, the driving rules of the similarity space that correspond to the
human perception is fairly unknown yet. Different users can have different perceptions of a same image
or movie depending on their intent and background. Moreover, usually the similarity between two pairs
of objects does not always follow the same measurement, the perceived distances may vary according
to the user intent in the moment.
The similarity evaluation process is usually quite complex and specialized, thus a great deal of ap-
proaches is encountered in the literature. We will organize the building blocks of this process around an
abstraction of the similarity space concept. It is assumed that a multimedia data can be modeled through
a set of features summarizing its content, which is usually called the data's feature vector, although the
features do not need to compose a vector space (e.g. complex objects of a same dataset can have feature
vectors of varying sizes). The features along with the distance functions constitute a
descriptor
, which
determines the similarity value (Torres et al., 2009). If we interpret each pair
<feature vector-distance
function>
as a similarity space instance, the whole set of possible instances forms our abstraction of the
human similarity space, in which the instances are switched according to the user perception at each instant.
Therefore, at the base level, it is only necessary to have the feature vector and the distance function to
compute the similarity. Although having a manner to compute the similarity suffices to answer similarity
queries (see 'Similarity Queries' section), we will discuss herein the internals of similarity evaluation.
In some domains, to choose the right combination is not a problem. For instance, geoprocessing
applications usually treat similarity as the distance among objects in the Earth's surface (e.g. return the
restaurants that are at most 1 mile from me, return the closest hospital to a given kindergarten). In this
case, the (spatial) features of the elements are well-defined (their geographical coordinates) and the
function used to compute the proximity is mainly restricted to the Euclidean distance or a shortest path
algorithm if the routes are modeled as a graph. On the other hand, for multimedia data it is mandatory
to identify which pair
<feature vector-distance function>
forms the space that closely represents the
user interpretation in each situation. Assessing the best combination between them improves the query
precision (Bugatti et al., 2008).
The challenge is to identify the similarity space instance that best fits the user expectation. This
“ideal” instance is usually called the semantic (similarity) space (He et al., 2002). There are many
fields and techniques employed to pursue this challenge, as shown in Figure 1. This illustration is not
intended to be exhaustive, but to include the most usual concepts regarding similarity. We highlight in
this figure that several concepts directly affect the components of a similarity space instance, such as
feature extraction, selection and transformation and feature/partial distance weighting. Every modifica-
tion promoted by any of these elements produces a new alternative instance. On a higher level are the
techniques, algorithms and external information that are employed to define how each of these elements
will be addressed to accomplish the user needs. In this level are: data processing algorithms, knowledge
discovery techniques, relevance feedback, machine learning and others.
