Efficient nearest neighbor query based on extended B+-tree in high-dimensional space

Nearest neighbor queries in high-dimensional space are important in various applications. One-dimensional mapping is an efficient indexing method to speed up the k-nearest neighbor search, which can transform a high-dimensional point into a single-dimensional value indexed by a B+-tree. In this paper, we present a new one-dimensional indexing scheme based on extended B+-tree for k-nearest neighbor search in high-dimensional space. We first partition the high-dimensional dataset and perform Principal Component Analysis on each partition. The distance of each point to the center of the partition is indexed using a B+-tree, and the projection on the first principal component of each point is embedded into leaf node of the B+-tree. In the query, a new filter strategy according to the spatial relationship between the query point and the axis determined by the first principal component is applied to improve the query performance. We also present a novel k-nearest neighbor search algorithm which can guarantee the accuracy of query results. Extensive experiments have been indicative of the effectiveness of our approach.