Random Binary Trees for Approximate Nearest Neighbour Search in Binary Space

Michal Komorowski, Tomasz Trzcinski

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%.

Introduction

In computer vision and data mining, finding the exact nearest neighbor to a query vector in massive databases is often computationally prohibitive. Consequently, systems rely on Approximate Nearest Neighbour (ANN) search. While much research has focused on real-valued vectors, real-time applications on mobile devices—such as augmented reality or drone navigation—increasingly utilize binary descriptors for speed. However, traditional tree-based ANN methods often perform poorly in binary spaces, leading to a reliance on Locality Sensitive Hashing (LSH).

This paper introduces Random Binary Search Trees (RBST), a method specifically optimized for high-dimensional binary spaces. By routing vectors through trees based on single-bit checks, RBST achieves a significant precision boost over state-of-the-art hashing methods without sacrificing speed or memory efficiency.

Methodology: Random Binary Search Trees

The proposed RBST approach leverages fast bitwise operations instead of complex distance calculations at each node during traversal.

Tree Structure and Routing

Unlike standard trees, RBSTs are constructed such that all paths from the root to the leaves have a uniform depth. The leaves store the actual binary descriptors. Internal nodes are assigned a random "bit mask" targeting a single dimension of the binary vector. During search, a bitwise AND operation determines the traversal path: a 0 bit routes the query left, while a 1 bit routes it right.

Ensemble and Ranking

To improve robustness, the system employs an ensemble of multiple trees. A query traverses all trees to gather a candidate pool of nearest neighbors from the leaves it lands in. Finally, the exact Hamming distances between the query and the union of candidates are calculated, and the candidates are sorted to return the top $N$ results. This approach bypasses heavy distance computations during tree traversal, shifting the primary workload to the final ranking stage.

Experimental Evaluation

The method was evaluated using a dataset of 1.25 million 512-dimensional binary FREAK descriptors from a Google Project Tango image-based localization system. Experiments were conducted across multiple subsets to ensure statistical significance.

Performance Comparison

RBST was compared against standard LSH, Uniform LSH, and Multi-probe LSH. The results demonstrate that RBST provides a substantial precision advantage.

Precision and Recall vs. Average Query Time. RBST shows a significant precision boost, especially at low query times.

As shown in the evaluation against query time, for fast queries (under 50 $\mu$s), RBST achieves over a 20% precision increase compared to the next best method, Uniform LSH. Crucially, this gain in precision does not come at the expense of recall.

Memory Efficiency

Regarding resource utilization, RBST remains competitive. With optimal parameters (e.g., depth of 40), its memory footprint is comparable to state-of-the-art methods, being only slightly higher than Multi-probe LSH, which is specifically designed for minimal memory usage.

Precision and Recall vs. Average Memory Consumption. RBST maintains high performance with competitive memory requirements.

Discussion and Future Work

A key insight from this research is that simplicity often rivals complex heuristics; random bit selection performed as well as more sophisticated metrics like Shannon entropy. However, the final stage—calculating Hamming distances and sorting candidates—remains the primary computational bottleneck.

Future work will explore optimizing this final linear search and investigating more complex metrics that account for bit dependencies to further refine tree routing and precision.

Summary updated

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%
BibTeX
@inproceedings{komorowski2017random,
  author = {Michal Komorowski and Tomasz Trzcinski},
  title = {{Random Binary Trees for Approximate Nearest Neighbour Search in Binary Space}},
  booktitle = {PReMI},
  year = {2017},
  url = {https://openreview.net/forum?id=eK_5AXOrV0F},
}
Figure