Title: Supermetric Search,
Abstract: Metric search is concerned with the efficient evaluation of queries in metric
spaces. In general,a large space of objects is arranged in such a way that,
when a further object is presented as a query, those objects most similar to
the query can be efficiently found. Most mechanisms rely upon the triangle
inequality property of the metric governing the space. The triangle inequality
property is equivalent to a finite embedding property, which states that any
three points of the space can be isometrically embedded in two-dimensional
Euclidean space. In this paper, we examine a class of semimetric space which is
finitely four-embeddable in three-dimensional Euclidean space. In mathematics
this property has been extensively studied and is generally known as the
four-point property. All spaces with the four-point property are metric spaces,
but they also have some stronger geometric guarantees. We coin the term
supermetric space as, in terms of metric search, they are significantly more
tractable. Supermetric spaces include all those governed by Euclidean, Cosine,
Jensen-Shannon and Triangular distances, and are thus commonly used within many
domains. In previous work we have given a generic mathematical basis for the
supermetric property and shown how it can improve indexing performance for a
given exact search structure. Here we present a full investigation into its use
within a variety of different hyperplane partition indexing structures, and go
on to show some more of its flexibility by examining a search structure whose
partition and exclusion conditions are tailored, at each node, to suit the
individual reference points and data set present there. Among the results
given, we show a new best performance for exact search using a well-known
benchmark.