Random Binary Search Trees for approximate nearest neighbour search in binary spaces
Michał Paweł Komorowski , Tomasz Trzciński
AbstractApproximate nearest neighbour (ANN) search is one of the most important problems in numerous computer science applications, including data mining, machine learning and computer vision. In this paper, we address the problem of ANN for high-dimensional binary vectors and we propose a simple yet powerful search method that is based on Random Binary Search Trees (RBST). Our method is validated on a dataset of 1.25M binary local feature descriptors obtained from a real-life image-based localisation system provided by Google as a part of Project Tango (now known as ARCore). The results of an extensive evaluation of our method performed on this dataset against the state-of-the-art ANN algorithms, such as Locality Sensitive Hashing, Uniform LSH and Multi-probe LSH, show the superiority of our method in terms of retrieval precision with a performance boost of over 20%.
|Journal series||Applied Soft Computing, ISSN 1568-4946|
|Publication size in sheets||1|
|Keywords in English||Approximate nearest neighbour searchBinary vectorsRandom Binary Search TreesLocality sensitive hashing|
|Score||= 200.0, 28-08-2020, ArticleFromJournal|
|Publication indicators||= 0; = 1; = 4.0; : 2018 = 2.369; : 2018 = 4.873 (2) - 2018=4.858 (5)|
|Citation count*||4 (2020-08-19)|
* presented citation count is obtained through Internet information analysis and it is close to the number calculated by the Publish or Perish system.