Speed up Linear Scan in High-Dimensions Using Extended B+-Tree
Jiangtao Cui, Bin Xiao, Zhiliang Yin · 2010
High-dimensional indexing is a pervasive challenge faced in multimedia retrieval. Existing indexing methods applying linear scan strategy, such as VA-file and its variations, are still efficient when the dimensionality is high. In this paper, we propose a new access idea implemented on linear scan based methods to speed up the nearest-neighbor queries. The idea is to map high-dimensional points into two kinds of one-dimensional values using projection and distance computation. The projection values of points on the first Principal Component are indexed using a B+-tree, and the distances of each point to a reference point are also embedded into leaf node of the B+-tree. During the search, only a small portion of data points need to be linearly accessed according to the extended B+-tree, which can reduce the I/O and processor time dramatically. Experiment results on large image databases show that the new access method provides a faster search speed than existing high-dimensional index methods.