Supermetric search with the four-point property

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

*Corresponding author for this work

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

12 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 space 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.

Original languageEnglish
Title of host publicationSimilarity Search and Applications - 9th International Conference, SISAP 2016, Proceedings
EditorsErich Schubert, Michael E. Houle, Laurent Amsaleg
PublisherSpringer-Verlag
Pages51-64
Number of pages14
ISBN (Print)9783319467580
DOIs
Publication statusPublished - 1 Jan 2016
Event9th International Conference on Similarity Search and Applications, SISAP 2016 - Tokyo, Japan
Duration: 24 Oct 201626 Oct 2016

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume9939 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference9th International Conference on Similarity Search and Applications, SISAP 2016
Country/TerritoryJapan
CityTokyo
Period24/10/1626/10/16

Fingerprint

Dive into the research topics of 'Supermetric search with the four-point property'. Together they form a unique fingerprint.

Cite this