面向高维数据集的近邻顺序查询方法

Sequential Search Method for Nearest Neighbor Query in High-Dimensional Dataset

对顺序索引方法进行了研究,提出一种基于向量近似的高维顺序索引结构,该结构顺序访问部分文件就能完成k近邻查询。在查询过程中依据投影值来终止查询过程,依据距离来排除不匹配的数据。为进一步降低数据访问率,采用椭圆体聚类算法对数据集进行划分。新索引结构支持以多个顺序访问过程完成k近邻查询,能够同时降低查询过程中的I/O开销和CPU开销。在大型高维图像特征库上的实验表明,新的高维索引结构的查询性能优于其他高维索引方法。

The sequential index method is studied. A new high-dimensional sequential indexing structure based on vector approximation is presented, in which only a small set of approximate vectors are sequentially accessed during the query. Two one-dimensional mapping values, projection value used for terminating the searching process and the distance used to reject impossible candidate points, are presented to improve the searching speed. To reduce the data points need to be accessed, the dataset is partitioned into some ellipsoid shaped clusters. The k-nearest neighbor search is composed of several sequentially scanning in the new index structure, which can reduce both the computational CPU cost and I/O cost. The experimental results on large image database are indicative of the effectiveness of the approach.