Picture map of Europe with pins indicating European capital cities

Open Access research with a European policy impact...

The Strathprints institutional repository is a digital archive of University of Strathclyde's Open Access research outputs. Strathprints provides access to thousands of Open Access research papers by Strathclyde researchers, including by researchers from the European Policies Research Centre (EPRC).

EPRC is a leading institute in Europe for comparative research on public policy, with a particular focus on regional development policies. Spanning 30 European countries, EPRC research programmes have a strong emphasis on applied research and knowledge exchange, including the provision of policy advice to EU institutions and national and sub-national government authorities throughout Europe.

Explore research outputs by the European Policies Research Centre...

Supermetric search with the four-point property

Connor, Richard and Vadicamo, Lucia and Cardillo, Franco Alberto and Rabitti, Fausto (2016) Supermetric search with the four-point property. In: 9th International Conference on Similiarty Search and Applications. Lecture Notes in Computing Science, 9939 . Springer-Verlag, pp. 51-64. ISBN 9783319467580

[img]
Preview
Text (Connor-etal-SISAP2016-Supermetric-search-with-the-four-point-property)
Connor_etal_SISAP2016_Supermetric_search_with_the_four_point_property.pdf - Accepted Author Manuscript

Download (1MB) | Preview

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.