### Abstract

Language | English |
---|---|

Number of pages | 36 |

Journal | Information Systems |

Early online date | 31 Jan 2018 |

DOIs | |

Publication status | E-pub ahead of print - 31 Jan 2018 |

### Keywords

- similarity search
- metric space
- supermetric space
- metric indexing
- four-point property
- Hilbert exclusion

### Cite this

*Information Systems*. https://doi.org/10.1016/j.is.2018.01.002

}

*Information Systems*. https://doi.org/10.1016/j.is.2018.01.002

**Supermetric search.** / Connor, Richard; Vadicamo, Lucia; Cardillo, Franco Alberto; Rabitti, Fausto.

Research output: Contribution to journal › Article

TY - JOUR

T1 - Supermetric search

AU - Connor, Richard

AU - Vadicamo, Lucia

AU - Cardillo, Franco Alberto

AU - Rabitti, Fausto

PY - 2018/1/31

Y1 - 2018/1/31

N2 - 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 em- bedding 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 mathemat- ics 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, Cosine2, 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.

AB - 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 em- bedding 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 mathemat- ics 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, Cosine2, 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.

KW - similarity search

KW - metric space

KW - supermetric space

KW - metric indexing

KW - four-point property

KW - Hilbert exclusion

UR - https://arxiv.org/abs/1707.08361

UR - https://www.sciencedirect.com/science/journal/03064379

U2 - 10.1016/j.is.2018.01.002

DO - 10.1016/j.is.2018.01.002

M3 - Article

JO - Information Systems

T2 - Information Systems

JF - Information Systems

SN - 0306-4379

ER -