Skip to content

Research at St Andrews

BitPart: exact metric search in high(er) dimensions

Research output: Contribution to journalArticlepeer-review


School/Research organisations


We define BitPart (Bitwise representations of binary Partitions), a novel exact search mechanism intended for use in high-dimensional spaces. In outline, a fixed set of reference objects is used to define a large set of regions within the original space, and each data item is characterised according to its containment within these regions. In contrast with other mechanisms only a subset of this information is selected, according to the query, before a search within the re-cast space is performed. Partial data representations are accessed only if they are known to be potentially useful towards the calculation of the exact query solution.

Our mechanism requires Ω(N log N ) space to evaluate a query, where N is the cardinality of the data, and therefore does not scale as well as previously defined mechanisms with low-dimensional data. However it has recently been shown that, for a nearest neighbour search in high dimensions, a sequential scan of the data is essentially unavoidable. This result has been suspected for a long time, and has been referred to as the curse of dimensionality in this context.

In the light of this result, the compromise achieved by this work is to make the best possible use of the available fast memory, and to offer great potential for parallel query evaluation. To our knowledge, it gives the best compromise currently known for performing exact search over data whose dimensionality is too high to allow the useful application of metric indexing, yet is still sufficiently low to give at least some traction from the metric and supermetric properties.


Original languageEnglish
Article number101493
Number of pages14
JournalInformation Systems
Early online date4 Feb 2020
Publication statusPublished - Jan 2021

    Research areas

  • Similarity search, Metric space, Metric indexing, Metric search, Four-point property

Discover related content
Find related publications, people, projects and more using interactive charts.

View graph of relations

Related by author

  1. On the application of convex transforms to metric search

    Connor, R., Dearle, A., Mic, V. & Zezula, P., Oct 2020, In: Pattern Recognition Letters. 138, p. 563-570

    Research output: Contribution to journalArticlepeer-review

  2. Sampled angles in high-dimensional spaces

    Connor, R. & Dearle, A., 2020, Similarity Search and Applications: 13th International Conference, SISAP 2020, Copenhagen, Denmark, September 30–October 2, 2020, Proceedings. Satoh, S., Vadicamo, L., Zimek, A., Carrara, F., Bartolini, I., Aumüller, M., Jónsson, B. Þ. & Pagh, R. (eds.). Cham: Springer, p. 233-247 (Lecture Notes in Computer Science (Information Systems and Applications, incl. Internet/Web, and HCI); vol. 12440).

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

  3. Modelling string structure in vector spaces

    Connor, R., Dearle, A. & Vadicamo, L., 9 Jul 2019, Proceedings of the 27th Italian Symposium on Advanced Database Systems: Castiglione della Pescaia (Grosseto), Italy, June 16th to 19th, 2019. Mecella, M., Amato, G. & Gennaro, C. (eds.). Sun SITE Central Europe, 12 p. 45. (CEUR Workshop Proceedings; vol. 2400).

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

  4. Querying metric spaces with bit operations

    Connor, R. & Dearle, A., 2018, Similarity Search and Applications: 11th International Conference, SISAP 2018, Lima, Peru, October 7-9, 2018, Proceedings. Marchand-Maillet, S., Silva, Y. N. & Chávez, E. (eds.). Cham: Springer, p. 33-46 14 p. (Lecture Notes in Computer Science; vol. 11223).

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

  5. Mediated Information Flow

    Dearle, A. & Connor, R., 17 Mar 2005, IPC No. G06F15/16, Patent No. US2005060380

    Research output: Patent

Related by journal

  1. Re-ranking via local embeddings: a use case with permutation-based indexing and the nSimplex projection

    Vadicamo, L., Gennaro, C., Falchi, F., Chávez, E., Connor, R. & Amato, G., Jan 2021, In: Information Systems. 95, 18 p., 101506.

    Research output: Contribution to journalArticlepeer-review

  2. Supermetric search

    Connor, R., Vadicamo, L., Cardillo, F. A. & Rabitti, F., Feb 2019, In: Information Systems. 80, p. 108-123 16 p.

    Research output: Contribution to journalArticlepeer-review

  3. A bounded distance metric for comparing tree structure

    Connor, R., Simeoni, F., Iakovos, M. & Moss, R., 1 Jun 2011, In: Information Systems. 36, 4, p. 748-764 17 p.

    Research output: Contribution to journalArticlepeer-review

ID: 265772781