Projects per year
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.
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 language | English |
---|---|
Title of host publication | Similarity search and applications |
Subtitle of host publication | 15th International conference, SISAP 2022, Bologna, Italy, October 5–7, 2022, proceedings |
Editors | Tomáš Skopal, Fabrizio Falchi, Jakub Lokoč, Maria Luisa Sapino, Ilaria Bartolini, Marco Patella |
Place of Publication | Cham |
Publisher | Springer, Cham |
Pages | 104-117 |
Number of pages | 14 |
ISBN (Electronic) | 9783031178498 |
ISBN (Print) | 9783031178481 |
DOIs | |
Publication status | Published - 29 Sept 2022 |
Event | International Conference on Similarity Search and Applications, SISAP 2022 - Bologna, Italy Duration: 5 Oct 2022 → 7 Oct 2022 Conference number: 15 https://www.sisap.org/2022/ |
Publication series
Name | Lecture notes in computer science |
---|---|
Volume | 13590 |
ISSN (Print) | 0302-9743 |
ISSN (Electronic) | 1611-3349 |
Conference
Conference | International Conference on Similarity Search and Applications, SISAP 2022 |
---|---|
Abbreviated title | SISAP 2022 |
Country/Territory | Italy |
City | Bologna |
Period | 5/10/22 → 7/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.Projects
- 1 Active
-
ADR UK Programme: University of Edinburgh 2022-2026 ADR UK Programme
Dearle, A. (PI), Akgun, O. (CoI) & Kirby, G. N. C. (CoI)
Economic & Social Research Council
1/04/22 → 31/03/26
Project: Standard