Speed up linear scan in high-dimensions by sorting one-dimensional projections
Jiangtao Cui, Bin Xiao, Gengdai Liu, Lian Jiang · International Journal of Intelligent Systems and Applications · 2011
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 highdimensional points into two kinds of one-dimensional values using projection and distance computation.The projection values on the line determined by the first Principal Component are sorted and 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.When performing nearest neighbor search, the Partial Distortion Searching and triangular inequality are employed to prune search space.In the new search algorithm, only a small portion of data points need to be linearly accessed by computing the bounded distance on the one-dimensional line, 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.