Investigating binary partition power in metric query

Richard Connor, Al Dearle, Lucia Vadicamo

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

1 Downloads (Pure)

Abstract

It is generally understood that, as dimensionality increases, the minimum cost of metric query tends from 𝑂(log 𝑛) to 𝑂(𝑛) in both space and time, where 𝑛 is the size of the data set. With low dimensionality, the former is easy to achieve; with very high dimensionality, the latter is inevitable. We previously described BitPart as a novel mechanism suitable for performing exact metric search in “high(er)” dimensions. The essential tradeoff of BitPart is that its space cost is linear with respect to the size of the data, but the actual space required for each object may be small as log2 𝑛 bits, which allows even very large data sets to be queried using only main memory. Potentially the time cost still scales with 𝑂(log 𝑛). Together these attributes give exact search which outperforms indexing structures if dimensionality is within a certain range. In this article, we reiterate the design of BitPart in this context. The novel contribution is an in-depth examination of what the notion of “high(er)” means in practical terms. To do this we introduce the notion of exclusion power, and show its application to some generated data sets across different dimensions.
Original languageEnglish
Title of host publicationSEBD 2022
Subtitle of host publicationproceedings of the the 30th Italian Symposium on Advanced Database Systems
EditorsGiuseppe Amato, Valentina Bartalesi, Devis Bianchini, Claudio Gennaro, Riccardo Torlone
Place of PublicationOnline
PublisherCEUR-WS
Pages415-426
Number of pages12
Volume3194
Publication statusPublished - 22 Aug 2022
EventItalian Symposium on Advanced Database Systems (SEBD 2022) - Tirrenia (Pisa), Italy
Duration: 19 Jun 2022 → 22 Jun 2022
Conference number: 30
https://sebd2022.isti.cnr.it/

Publication series

NameItalian Symposium on Advanced Database Systems
PublisherCEUR-WS
Volume3194
ISSN (Print)1613-0073

Conference

ConferenceItalian Symposium on Advanced Database Systems (SEBD 2022)
Abbreviated titleSEBD 2022
Country/TerritoryItaly
CityTirrenia (Pisa)
Period19/06/22 → 22/06/22
Internet address

Keywords

  • Similarity search
  • Exclusion power
  • Metric search
  • Metric indexing

Fingerprint

Dive into the research topics of 'Investigating binary partition power in metric query'. Together they form a unique fingerprint.

Cite this