Abstract:

In order to reduce the “curse of dimensionality” faced by the traditional indexing method at high dimensionality, a new MRVA-File(Multi-Resolution Vector Approximation File) approach is proposed. In the new approach, a multi-resolution data structure is built using the wavelet transform, and low-dimensional distance measure between the candidate vector and query vector can be obtained at a low-resolution level. When doing the nearest neighbor search, the lower bounds of distance is computed at each level and compared with the latest nearest neighbor distance, starting from the low-resoltuion level. If it is larger than the latest nearest neighbor distance, the candidate can be removed without calculating the distance in the high-dimensional space at the high-resolution level. By doing this, the total computational complexity can be dramatically reduced. Experimental results on large image databases show that the new approach provides a faster search speed than the VA-File approach.

Key words: image databases, curse of dimensionality, k-nearest neighbor search, multi-resolution, wavelet transform