Supermetric search

Richard Connor, Lucia Vadicamo, Franco Alberto Cardillo, Fausto Rabitti

Research output: Contribution to journalArticle

3 Citations (Scopus)

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 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.
LanguageEnglish
Number of pages36
JournalInformation Systems
Early online date31 Jan 2018
DOIs
Publication statusE-pub ahead of print - 31 Jan 2018

Keywords

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

Cite this

Connor, R., Vadicamo, L., Cardillo, F. A., & Rabitti, F. (2018). Supermetric search. Information Systems. https://doi.org/10.1016/j.is.2018.01.002
Connor, Richard ; Vadicamo, Lucia ; Cardillo, Franco Alberto ; Rabitti, Fausto. / Supermetric search. In: Information Systems. 2018.
@article{188a816404c44974b494c941f722ae5b,
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 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.",
keywords = "similarity search, metric space, supermetric space, metric indexing, four-point property, Hilbert exclusion",
author = "Richard Connor and Lucia Vadicamo and Cardillo, {Franco Alberto} and Fausto Rabitti",
year = "2018",
month = "1",
day = "31",
doi = "10.1016/j.is.2018.01.002",
language = "English",
journal = "Information Systems",
issn = "0306-4379",

}

Connor, R, Vadicamo, L, Cardillo, FA & Rabitti, F 2018, 'Supermetric search' Information Systems. https://doi.org/10.1016/j.is.2018.01.002

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

In: Information Systems, 31.01.2018.

Research output: Contribution to journalArticle

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 -

Connor R, Vadicamo L, Cardillo FA, Rabitti F. Supermetric search. Information Systems. 2018 Jan 31. https://doi.org/10.1016/j.is.2018.01.002