Skip header navigation

University of Stirling

×

Conference Proceeding

Supermetric search with the four-point property

Citation
Connor R, Vadicamo L, Cardillo FA & Rabitti F (2016) Supermetric search with the four-point property. In: Amsaleg L, Houle M & Schubert E (eds.) Similarity Search and Applications. SISAP 2016. Lecture Notes in Computer Science, 9939. International Conference on Similarity Search and Applications, SISAP 2016, Tokyo, Japan, 24.10.2016-26.10.2016. Cham, Switzerland: Springer, pp. 51-64. https://doi.org/10.1007/978-3-319-46759-7_4

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.

StatusPublished
Author(s)Connor, Richard; Vadicamo, Lucia; Cardillo, Franco Alberto; Rabitti, Fausto
Title of seriesLecture Notes in Computer Science
Number in series9939
Publication date31/12/2016
Publication date online27/09/2016
URLhttp://hdl.handle.net/1893/27672
PublisherSpringer
Place of publicationCham, Switzerland
ISSN of series0302-9743
ISBN978-3-319-46758-0
ConferenceInternational Conference on Similarity Search and Applications, SISAP 2016
Conference locationTokyo, Japan
Dates
Scroll back to the top