Investigating binary partition power in metric query

Richard Connor, Al Dearle, Lucia Vadicamo

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

2 Downloads (Pure)


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
Number of pages12
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

Publication series

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


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


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


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

Cite this