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

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