Random Binary Trees for Approximate Nearest Neighbour Search in Binary Space

2017/08/09 by Michal Komorowski, Komorowski, Michal, Tomasz Trzcinski +1
Computer Science · #Computer Vision and Pattern Recognition (cs.CV) #FOS: Computer and information sciences #cs.CV

paper · pdf · doi:10.48550/arxiv.1708.02976

The final publication is available at Springer via https://doi.org/10.1007/978-3-319-69900-4_60

arxiv created 2019/03/24 · arxiv updated 2019/03/26

Abstract

Approximate nearest neighbour (ANN) search is one of the most important problems in computer science fields such as data mining or computer vision. In this paper, we focus on ANN for high-dimensional binary vectors and we propose a simple yet powerful search method that uses Random Binary Search Trees (RBST). We apply our method to 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. An extensive evaluation of our method against the state-of-the-art variations of Locality Sensitive Hashing (LSH), namely Uniform LSH and Multi-probe LSH, shows the superiority of our method in terms of retrieval precision with performance boost of over 20%

Related

• Approximate Nearest Neighbor Search on High Dimensional Data --- Experiments, Analyses, and Improvement (v1.0)
• PM-LSH: a fast and accurate in-memory framework for high-dimensional approximate NN and closest pair search
• Algorithms for Similarity Search and Pseudorandomness
• Anti-sparse coding for approximate nearest neighbor search
• Randomized embeddings with slack, and high-dimensional Approximate Nearest Neighbor