An efficient tree structure for indexing feature vectors

作者：The Anh Pham^*; Barrat Sabine; Delalandre Mathieu; Ramel Jean Yves

来源：Pattern Recognition Letters, 2015, 55: 42-50.

DOI：10.1016/j.patrec.2014.08.006

• Exact nearest neighbour search
• Approximate nearest neighbour search
• Feature indexing
• Randomized KD-trees
• Randomized clustering trees

This paper addresses the problem of feature indexing in feature vector space. A linked-node m-ary tree (LM-tree) structure is presented to quickly produce the queries for an approximate and exact nearest neighbour search. Three main contributions are made, which can be attributed to the proposed LM-tree. First, a new polar-space-based method of data decomposition is presented to construct the LM-tree. Second, a novel pruning rule is proposed to efficiently narrow down the search space. Finally, a bandwidth search method is introduced to explore the nodes of the LM-tree. Extensive experiments were performed to study the behaviour of the proposed indexing algorithm. These experimental results showed that the proposed algorithm provides a significant improvement in the search performance for the tasks of both exact and approximate nearest neighbour (ENN/ANN) searches.

• 出版日期2015-4-1