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