Sampled angles in high-dimensional spaces

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

47 Downloads (Pure)

Abstract

Similarity search using metric indexing techniques is largely a solved problem in low-dimensional spaces. However techniques based only on the triangle inequality property start to fail as dimensionality increases.

Since proper metric spaces allow a finite projection of any three objects into a 2D Euclidean space, the notion of angle can be validly applied among any three (but no more) objects. High dimensionality is known to have interesting effects on angles in vector spaces, but to our knowledge this has not been studied in more general metric spaces. Here, we consider the use of angles among objects in combination with distances.

As dimensionality becomes higher, we show that the variance in sampled angles reduces. Furthermore, sampled angles also become correlated with inter-object distances, giving different distributions between query solutions and non-solutions. We show the theoretical underpinnings of this observation in unbounded high-dimensional Euclidean spaces, and then examine how the pure property is reflected in some real-world high dimensional spaces. Our experiments on both generated and real world datasets demonstrate that these observations can have an important impact on the tractability of search as dimensionality increases.
Original languageEnglish
Title of host publicationSimilarity Search and Applications
Subtitle of host publication13th International Conference, SISAP 2020, Copenhagen, Denmark, September 30–October 2, 2020, Proceedings
EditorsShin'ichi Satoh, Lucia Vadicamo, Arthur Zimek, Fabio Carrara, Ilaria Bartolini, Martin Aumüller, Björn Þór Jónsson, Rasmus Pagh
Place of PublicationCham
PublisherSpringer
Pages233-247
ISBN (Electronic)9783030609368
ISBN (Print)9783030609351
DOIs
Publication statusPublished - 2020
Event13th International Conference on Similarity Search and Applications, SISAP 2020 - Virtual
Duration: 30 Sept 20202 Oct 2020
http://www.sisap.org/2020/

Publication series

NameLecture Notes in Computer Science (Information Systems and Applications, incl. Internet/Web, and HCI)
PublisherSpringer
Volume12440
ISSN (Print)0302-9743

Conference

Conference13th International Conference on Similarity Search and Applications, SISAP 2020
Abbreviated titleSISAP 2020
Period30/09/202/10/20
Internet address

Keywords

  • Metric search
  • High dimensional space

Fingerprint

Dive into the research topics of 'Sampled angles in high-dimensional spaces'. Together they form a unique fingerprint.

Cite this