Pair-wisely optimized clustering tree for feature indexing

•We present a new data structure for indexing real feature vectors.•A comprehensive review of related work is provided.•Extensive experiments are carried out in comparison with state-of-the-art methods.•We obtained promising results for many datasets and feature types.

This paper presents a new approach for indexing real feature vectors in high dimensional space. The proposed approach is developed based on Pair-wisely Optimized Clustering tree (POC-tree) that exploits the benefit of hierarchical clustering and Voronoi decomposition. The POC-tree maximizes the separation space of every pair of clusters at each level of decomposition, making a compact representation of the underlying data. Searching in the POC-tree is efficiently driven by the bandwidth search strategy. A single POC-tree can be used to create effective index of data for both exact and approximate nearest neighbour search. We also present a new method to combine multiple weak POC-trees for boosting the search performance for specific datasets in very high dimensional space. Extensive experiments have been conducted to evaluate the proposed approach in which it outperforms the state-of-the-art methods for all the datasets used in our experiments.