Journal of Frontiers of Computer Science and Technology ›› 2010, Vol. 4 ›› Issue (9): 840-849.DOI: 10.3778/j.issn.1673-9418.2010.09.007

• 学术研究 • Previous Articles     Next Articles

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

CUI Jiangtao1+, XIAO Bin1, ZHAN Haisheng2   

  1. 1. School of Computer Science and Technology, Xidian University, Xi’an 710071, China
    2. School of Network Education, Xidian University, Xi’an 710071, China
  • Received:1900-01-01 Revised:1900-01-01 Online:2010-09-09 Published:2010-09-09
  • Contact: CUI Jiangtao


崔江涛1+, 肖 斌1, 詹海生2   

  1. 1. 西安电子科技大学 计算机学院, 西安 710071
    2. 西安电子科技大学 网络教育学院, 西安 710071
  • 通讯作者: 崔江涛

Abstract: The sequential index method is studied. A new high-dimensional sequential indexing structure based on vector ap-proximation 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 computa-tional CPU cost and I/O cost. The experimental results on large image database are indicative of the effectiveness of the approach.

Key words: high-dimensional indexing, k-nearest neighbor search, ellipsoid shaped clustering, sequential scan

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

关键词: 高维索引, k近邻查询, 椭圆体聚类, 顺序查找

CLC Number: