title: Trinary-projection trees for approximate nearest neighbor search.
abstract: 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.
authors.affiliation: Microsoft Research Aisa, Beijing.
authors.forename: Jingdong
authors.initials: J
authors.lastname: Wang
authors.affiliation: The Hong Kong University of Science and Technology, Hong Kong.
authors.forename: Naiyan
authors.initials: N
authors.lastname: Wang
authors.affiliation: Carnegie Mellon University, Pittsburgh.
authors.forename: You
authors.initials: Y
authors.lastname: Jia
authors.affiliation: Tsinghua University, Beijing.
authors.forename: Jian
authors.initials: J
authors.lastname: Li
authors.affiliation: Peking University, Beijing.
authors.forename: Gang
authors.initials: G
authors.lastname: Zeng
authors.affiliation: Peking University, Beijing.
authors.forename: Hongbin
authors.initials: H
authors.lastname: Zha
authors.affiliation: Microsoft Corporation, Bellevue.
authors.forename: Xian-Sheng
authors.initials: XS
authors.lastname: Hua
mesh_terms: D000465:Algorithms; D001185:Artificial Intelligence; D007089:Image Enhancement / Q000379:methods; D007090:Image Interpretation, Computer-Assisted / Q000379:methods*; D010363:Pattern Recognition, Automated / Q000379:methods*; D015203:Reproducibility of Results; D012680:Sensitivity and Specificity; D013382:Subtraction Technique