In this paper, we attempt to scale up the kd-tree index-ing 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 e ach 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.