High-dimensional simplexes for supermetric search

Richard Connor*, Lucia Vadicamo, Fausto Rabitti

*Corresponding author for this work

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

15 Citations (Scopus)

Abstract

In a metric space, triangle inequality implies that, for any three objects, a triangle with edge lengths corresponding to their pairwise distances can be formed. The n-point property is a generalisation of this where, for any (n+1) objects in the space, there exists an n-dimensional simplex whose edge lengths correspond to the distances among the objects. In general, metric spaces do not have this property; however in 1953, Blumenthal showed that any semi-metric space which is isometrically embeddable in a Hilbert space also has the n-point property. We have previously called such spaces supermetric spaces, and have shown that many metric spaces are also supermetric, including Euclidean, Cosine, Jensen-Shannon and Triangular spaces of any dimension. Here we show how such simplexes can be constructed from only their edge lengths, and we show how the geometry of the simplexes can be used to determine lower and upper bounds on unknown distances within the original space. By increasing the number of dimensions, these bounds converge to the true distance. Finally we show that for any Hilbert-embeddable space, it is possible to construct Euclidean spaces of arbitrary dimensions, from which these lower and upper bounds of the original space can be determined. These spaces may be much cheaper to query than the original. For similarity search, the engineering tradeoffs are good: we show significant reductions in data size and metric cost with little loss of accuracy, leading to a significant overall improvement in exact search performance.

Original languageEnglish
Title of host publicationSimilarity Search and Applications - 10th International Conference, SISAP 2017, Proceedings
EditorsFelix Borutta, Peer Kroger, Thomas Seidl, Christian Beecks
PublisherSpringer-Verlag
Pages96-109
Number of pages14
ISBN (Print)9783319684734
DOIs
Publication statusPublished - 2017
Event10th International Conference on Similarity Search and Applications, SISAP 2017 - Munich, Germany
Duration: 4 Oct 20176 Oct 2017

Publication series

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

Conference

Conference10th International Conference on Similarity Search and Applications, SISAP 2017
Country/TerritoryGermany
CityMunich
Period4/10/176/10/17

Keywords

  • Dimensionality reduction
  • Metric embedding
  • Metric search
  • Supermetric space

Fingerprint

Dive into the research topics of 'High-dimensional simplexes for supermetric search'. Together they form a unique fingerprint.

Cite this