On the expected exclusion power of binary partitions for metric search

Lucia Vadicamo*, Alan Dearle, Richard Connor

*Corresponding author for this work

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

Abstract

The entire history and, we dare say, future of similarity search is governed by the underlying notion of partition. A partition is an equivalence relation defined over the space, therefore each element of the space is contained within precisely one of the equivalence classes of the partition. All attempts to search a finite space efficiently, whether exactly or approximately, rely on some set of principles which imply that if the query is within one equivalence class, then one or more other classes either cannot, or probably do not, contain any of its solutions.

In most early research, partitions relied only on the metric postulates, and logarithmic search time could be obtained on low dimensional spaces. In these cases, it was straightforward to identify multiple partitions, each of which gave a relatively high probability of identifying subsets of the space which could not contain solutions. Over time the datasets being searched have become more complex, leading to higher dimensional spaces. It is now understood that even an approximate search in a very high-dimensional space is destined to require O(n) time and space.

Almost entirely missing from the research literature however is any analysis of exactly when this effect takes over. In this paper, we make a start on tackling this important issue. Using a quantitative approach, we aim to shed some light on the notion of the exclusion power of partitions, in an attempt to better understand their nature with respect to increasing dimensionality.
Original languageEnglish
Title of host publicationSimilarity search and applications
Subtitle of host publication15th International conference, SISAP 2022, Bologna, Italy, October 5–7, 2022, proceedings
EditorsTomáš Skopal, Fabrizio Falchi, Jakub Lokoč, Maria Luisa Sapino, Ilaria Bartolini, Marco Patella
Place of PublicationCham
PublisherSpringer, Cham
Pages104-117
Number of pages14
ISBN (Electronic)9783031178498
ISBN (Print)9783031178481
DOIs
Publication statusPublished - 29 Sept 2022
EventInternational Conference on Similarity Search and Applications, SISAP 2022 - Bologna, Italy
Duration: 5 Oct 20227 Oct 2022
Conference number: 15
https://www.sisap.org/2022/

Publication series

NameLecture notes in computer science
Volume13590
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

ConferenceInternational Conference on Similarity Search and Applications, SISAP 2022
Abbreviated titleSISAP 2022
Country/TerritoryItaly
CityBologna
Period5/10/227/10/22
Internet address

Keywords

  • Metric search
  • Binary partitioning
  • Exclusion power
  • Curse of dimensionality

Fingerprint

Dive into the research topics of 'On the expected exclusion power of binary partitions for metric search'. Together they form a unique fingerprint.

Cite this