We address the problem of approximate nearest neighbor (ANN) search for visual descriptor indexing. Most spatial partition trees, such as KD trees, VP trees, and so on, follow the hierarchical binary space partitioning framework. The key effort is to design different partition functions (hyperplane or hypersphere) to divide the points so that 1) the data points can be well grouped to support effective NN candidate location and 2) the partition functions can be quickly evaluated to support efficient NN candidate location. We design a trinary-projection direction-based partition function. The trinary-projection direction is defined as a combination of a few coordinate axes with the weights being 1 or -1. We pursue the projection direction using the widely adopted maximum variance criterion to guarantee good space partitioning and find fewer coordinate axes to guarantee efficient partition function evaluation. We present a coordinate-wise enumeration algorithm to find the principal trinary-projection direction. In addition, we provide an extension using multiple randomized trees for improved performance. We justify our approach on large-scale local patch indexing and similar image search.

In this paper, we attempt to scale up the kd-tree indexing methods for large-scale vision applications, e.g., indexing a large number of SIFT features and other types of visual descriptors. To this end, we propose an effective approach to generate near-optimal binary space partitioning and need low time cost to access the nodes in the query stage. First, we relax the coordinate-axis-alignment constraint in partition axis selection used in conventional kd-trees, and form a partition axis with the great variance by combining a few coordinate axes in a binary manner for each node, which yields better space partitioning and requires almost the same time cost to visit internal nodes during the query stage thanks to cheap projection operations. Then, we introduce a simple but very effective scheme to guarantee the partition axis of each internal node is orthogonal to or parallel with those of its ancestors, which leads to efficient distance computation between a query point and the cell associated with each node and yields fast priority search. Compared with the conventional kd-trees, our approach takes a little more tree construction time, but obtains much better nearest neighbor search performance. Experimental results on large scale local patch indexing and image search with tiny images show that our approach outperforms the state-of-the-art kd-tree based indexing methods.