High-dimensional simplexes for metric search

Richard Connor, Lucia Vadicamo, Fausto Rabitti

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

5 Citations (Scopus)

Abstract

In a metric space, triangle inequality implies that, for any three objects, a triangle with edge lengths corresponding to their pair- wise 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 prop- erty; 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.
LanguageEnglish
Title of host publicationSimilarity Search and Applications
Subtitle of host publication10th International Conference, SISAP 2017, Munich, Germany, October 4-6, 2017, Proceedings
EditorsChristian Beecks, Peer Kröger, Thomas Seidl
Place of PublicationCham
PublisherSpringer
Pages96-109
Number of pages14
Volume10609
ISBN (Print)9783319684734
DOIs
Publication statusPublished - 4 Oct 2017
EventSISAP 2017: 10th International Conference on Similarity Search and Applications - Munich, Germany
Duration: 4 Oct 20176 Oct 2017

Publication series

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

Conference

ConferenceSISAP 2017
CountryGermany
CityMunich
Period4/10/176/10/17

Fingerprint

Hilbert spaces
Geometry
Costs

Keywords

  • supermetric space
  • metric search
  • metric embedding
  • dimensionality reduction
  • distance geometry

Cite this

Connor, R., Vadicamo, L., & Rabitti, F. (2017). High-dimensional simplexes for metric search. In C. Beecks, P. Kröger, & T. Seidl (Eds.), Similarity Search and Applications: 10th International Conference, SISAP 2017, Munich, Germany, October 4-6, 2017, Proceedings (Vol. 10609, pp. 96-109). (Lecture Notes in Computer Science; Vol. 10609). Cham: Springer. https://doi.org/10.1007/978-3-319-68474-1_7
Connor, Richard ; Vadicamo, Lucia ; Rabitti, Fausto. / High-dimensional simplexes for metric search. Similarity Search and Applications: 10th International Conference, SISAP 2017, Munich, Germany, October 4-6, 2017, Proceedings. editor / Christian Beecks ; Peer Kröger ; Thomas Seidl. Vol. 10609 Cham : Springer, 2017. pp. 96-109 (Lecture Notes in Computer Science).
@inproceedings{2344508b9466496d8df46e42157ca754,
title = "High-dimensional simplexes for metric search",
abstract = "In a metric space, triangle inequality implies that, for any three objects, a triangle with edge lengths corresponding to their pair- wise 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 prop- erty; 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.",
keywords = "supermetric space, metric search, metric embedding, dimensionality reduction, distance geometry",
author = "Richard Connor and Lucia Vadicamo and Fausto Rabitti",
note = "The final publication is available at link.springer.com via https://doi.org/10.1007/978-3-319-68474-1_7",
year = "2017",
month = "10",
day = "4",
doi = "10.1007/978-3-319-68474-1_7",
language = "English",
isbn = "9783319684734",
volume = "10609",
series = "Lecture Notes in Computer Science",
publisher = "Springer",
pages = "96--109",
editor = "Christian Beecks and Peer Kr{\"o}ger and Thomas Seidl",
booktitle = "Similarity Search and Applications",

}

Connor, R, Vadicamo, L & Rabitti, F 2017, High-dimensional simplexes for metric search. in C Beecks, P Kröger & T Seidl (eds), Similarity Search and Applications: 10th International Conference, SISAP 2017, Munich, Germany, October 4-6, 2017, Proceedings. vol. 10609, Lecture Notes in Computer Science, vol. 10609, Springer, Cham, pp. 96-109, SISAP 2017, Munich, Germany, 4/10/17. https://doi.org/10.1007/978-3-319-68474-1_7

High-dimensional simplexes for metric search. / Connor, Richard; Vadicamo, Lucia; Rabitti, Fausto.

Similarity Search and Applications: 10th International Conference, SISAP 2017, Munich, Germany, October 4-6, 2017, Proceedings. ed. / Christian Beecks; Peer Kröger; Thomas Seidl. Vol. 10609 Cham : Springer, 2017. p. 96-109 (Lecture Notes in Computer Science; Vol. 10609).

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

TY - GEN

T1 - High-dimensional simplexes for metric search

AU - Connor, Richard

AU - Vadicamo, Lucia

AU - Rabitti, Fausto

N1 - The final publication is available at link.springer.com via https://doi.org/10.1007/978-3-319-68474-1_7

PY - 2017/10/4

Y1 - 2017/10/4

N2 - In a metric space, triangle inequality implies that, for any three objects, a triangle with edge lengths corresponding to their pair- wise 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 prop- erty; 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.

AB - In a metric space, triangle inequality implies that, for any three objects, a triangle with edge lengths corresponding to their pair- wise 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 prop- erty; 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.

KW - supermetric space

KW - metric search

KW - metric embedding

KW - dimensionality reduction

KW - distance geometry

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

U2 - 10.1007/978-3-319-68474-1_7

DO - 10.1007/978-3-319-68474-1_7

M3 - Conference contribution book

SN - 9783319684734

VL - 10609

T3 - Lecture Notes in Computer Science

SP - 96

EP - 109

BT - Similarity Search and Applications

A2 - Beecks, Christian

A2 - Kröger, Peer

A2 - Seidl, Thomas

PB - Springer

CY - Cham

ER -

Connor R, Vadicamo L, Rabitti F. High-dimensional simplexes for metric search. In Beecks C, Kröger P, Seidl T, editors, Similarity Search and Applications: 10th International Conference, SISAP 2017, Munich, Germany, October 4-6, 2017, Proceedings. Vol. 10609. Cham: Springer. 2017. p. 96-109. (Lecture Notes in Computer Science). https://doi.org/10.1007/978-3-319-68474-1_7