Supermetric search with the four-point property

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

Research output: Chapter in Book/Report/Conference proceedingConference contribution book

5 Citations (Scopus)

Abstract

Metric indexing research 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 such 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 4-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 as, in terms of metric search, they are significantly more tractable. We show some stronger geometric guarantees deriving from the four-point property which can be used in indexing to great effect, and show results for two of the SISAP benchmark searches that are substantially better than any previously published.
LanguageEnglish
Title of host publication9th International Conference on Similiarty Search and Applications
PublisherSpringer-Verlag
Pages51-64
Number of pages14
Volume9939
ISBN (Print)9783319467580
DOIs
Publication statusPublished - 24 Oct 2016
EventSISAP 2016 - 9th International Conference on Similarity Searches and Applications - Tokyo, Japan
Duration: 24 Oct 201626 Oct 2016

Publication series

NameLecture Notes in Computing Science
PublisherSpringer-Verlag
ISSN (Print)0302-9743

Conference

ConferenceSISAP 2016 - 9th International Conference on Similarity Searches and Applications
CountryJapan
CityTokyo
Period24/10/1626/10/16

Keywords

  • metric search
  • Hilbert embedding
  • four-point property

Cite this

Connor, R., Vadicamo, L., Cardillo, F. A., & Rabitti, F. (2016). Supermetric search with the four-point property. In 9th International Conference on Similiarty Search and Applications (Vol. 9939, pp. 51-64). [2] (Lecture Notes in Computing Science). Springer-Verlag. https://doi.org/10.1007/978-3-319-46759-7
Connor, Richard ; Vadicamo, Lucia ; Cardillo, Franco Alberto ; Rabitti, Fausto. / Supermetric search with the four-point property. 9th International Conference on Similiarty Search and Applications. Vol. 9939 Springer-Verlag, 2016. pp. 51-64 (Lecture Notes in Computing Science).
@inproceedings{f2d2b1790eb045b89b568623806402f1,
title = "Supermetric search with the four-point property",
abstract = "Metric indexing research 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 such 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 4-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 as, in terms of metric search, they are significantly more tractable. We show some stronger geometric guarantees deriving from the four-point property which can be used in indexing to great effect, and show results for two of the SISAP benchmark searches that are substantially better than any previously published.",
keywords = "metric search, Hilbert embedding, four-point property",
author = "Richard Connor and Lucia Vadicamo and Cardillo, {Franco Alberto} and Fausto Rabitti",
note = "The final publication is available at Springer via http://dx.doi.org/[DOI to be inserted on publication]",
year = "2016",
month = "10",
day = "24",
doi = "10.1007/978-3-319-46759-7",
language = "English",
isbn = "9783319467580",
volume = "9939",
series = "Lecture Notes in Computing Science",
publisher = "Springer-Verlag",
pages = "51--64",
booktitle = "9th International Conference on Similiarty Search and Applications",

}

Connor, R, Vadicamo, L, Cardillo, FA & Rabitti, F 2016, Supermetric search with the four-point property. in 9th International Conference on Similiarty Search and Applications. vol. 9939, 2, Lecture Notes in Computing Science, Springer-Verlag, pp. 51-64, SISAP 2016 - 9th International Conference on Similarity Searches and Applications, Tokyo, Japan, 24/10/16. https://doi.org/10.1007/978-3-319-46759-7

Supermetric search with the four-point property. / Connor, Richard; Vadicamo, Lucia; Cardillo, Franco Alberto; Rabitti, Fausto.

9th International Conference on Similiarty Search and Applications. Vol. 9939 Springer-Verlag, 2016. p. 51-64 2 (Lecture Notes in Computing Science).

Research output: Chapter in Book/Report/Conference proceedingConference contribution book

TY - GEN

T1 - Supermetric search with the four-point property

AU - Connor, Richard

AU - Vadicamo, Lucia

AU - Cardillo, Franco Alberto

AU - Rabitti, Fausto

N1 - The final publication is available at Springer via http://dx.doi.org/[DOI to be inserted on publication]

PY - 2016/10/24

Y1 - 2016/10/24

N2 - Metric indexing research 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 such 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 4-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 as, in terms of metric search, they are significantly more tractable. We show some stronger geometric guarantees deriving from the four-point property which can be used in indexing to great effect, and show results for two of the SISAP benchmark searches that are substantially better than any previously published.

AB - Metric indexing research 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 such 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 4-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 as, in terms of metric search, they are significantly more tractable. We show some stronger geometric guarantees deriving from the four-point property which can be used in indexing to great effect, and show results for two of the SISAP benchmark searches that are substantially better than any previously published.

KW - metric search

KW - Hilbert embedding

KW - four-point property

UR - http://www.sisap.org/2016/

UR - http://www.springer.com/gb/computer-science/lncs

UR - http://www.springer.com/gb/book/9783319467580

U2 - 10.1007/978-3-319-46759-7

DO - 10.1007/978-3-319-46759-7

M3 - Conference contribution book

SN - 9783319467580

VL - 9939

T3 - Lecture Notes in Computing Science

SP - 51

EP - 64

BT - 9th International Conference on Similiarty Search and Applications

PB - Springer-Verlag

ER -

Connor R, Vadicamo L, Cardillo FA, Rabitti F. Supermetric search with the four-point property. In 9th International Conference on Similiarty Search and Applications. Vol. 9939. Springer-Verlag. 2016. p. 51-64. 2. (Lecture Notes in Computing Science). https://doi.org/10.1007/978-3-319-46759-7