Efficient nearest neighbor query based on extended B+-tree in high-dimensional space
Efficient nearest neighbor query based on extended B+-tree in high-dimensional space
复制标题
DOI：
10.1016/j.patrec.2010.05.026
复制
发表时间：
2010-09
期刊：
影响因子：
--
通讯作者：
Jiangtao Cui;Zhiyong An;Yong Guo;Shuisheng Zhou
中科院分区：
文献类型：
--
作者：
Jiangtao Cui;Zhiyong An;Yong Guo;Shuisheng Zhou
高维空间中的最近邻查询在各种应用中具有重要意义。一维映射是一种有效的索引方法，它可以将高维的点转化为一个由B+树索引的一维值，从而加快k-近邻搜索的速度。本文提出了一种基于扩展B+树的一维索引方案，用于高维空间中的k-最近邻搜索。我们首先对高维数据集进行分区，并对每个分区执行主成分分析。利用B+树对每个点到分割中心的距离进行索引，并将每个点在第一主成分上的投影嵌入到B+树的叶节点中。在查询过程中，根据第一主成分确定的查询点与轴线之间的空间关系，应用了一种新的过滤策略，提高了查询性能。我们还提出了一种新的k-近邻搜索算法，可以保证查询结果的准确性。大量的实验表明了我们方法的有效性。
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.