Search

Approximate 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%. • Random Binary Search Trees (RBST) are a relatively simple yet powerful ANN method. • RBST give better or equal results to the competing hashing algorithms. • A powerful ANN method can be created by extending a simple data structure. • Techniques like the priority search are not needed to create a good ANN method. [ABSTRACT FROM AUTHOR]

Abstract: Binary descriptors allow faster similarity computation than real-valued ones while requiring much less storage. As a result, many algorithms have recently been proposed to binarize floating-point descriptors so that they can be searched for quickly. Unfortunately, even if the similarity between vectors can be computed fast, exhaustive linear search remains impractical for truly large databases and approximate nearest neighbor (ANN) search is still required. It is therefore surprising that relatively little attention has been paid to the efficiency of ANN algorithms on binary vectors and this is the focus of this paper. We first show that binary-space Voronoi diagrams have thick boundaries, meaning that there are many points that lie at the same distance from two random points. This violates the implicit assumption made by most ANN algorithms that points can be neatly assigned to clusters centered around a set of cluster centers. As a result, state-of-the-art algorithms that can operate on binary vectors exhibit much lower performance than those that work with floating point ones. The above analysis is the first contribution of the paper. The second one is two effective ways to overcome this limitation, by appropriately randomizing either a tree-based algorithm or hashing-based one. In both cases, we show that we obtain precision/recall curves that are similar to those than can be obtained using floating point number calculation, but at much reduced computational cost. [Copyright &y& Elsevier]

The well known Hamming distance between a pair of permutations (or strings) of the same length is simply the number of pairs of different digits in these permutations. It has been an interesting topic of research to find mappings from the binary vectors to permutations of the same length such that the Hamming distance is preserved or increased. As a natural variation we introduce the Hamming gap of radius r between two permutations, which is, in a way, equivalent to the number of digits where the corresponding pair of entries differ by at least r. This is called the r -Hamming gap. We first discuss the properties of this new concept. We then show mappings from binary vectors to permutations such that the images of a pair of binary vectors (at Hamming distance d) have r -Hamming gap at least d. We also show the generalization of our findings to permutations on Z n (where n ≡ 0) instead of [ n ]. [ABSTRACT FROM AUTHOR]