An efficient retrieval method for nearest neighbor searches in high-dimensional image database

Nearest neighbor search is emerging as an important search paradigm in the high-dimensional image databases. The VA-File approach in which data compression technology has been applied can accelerate the nearest neighbor search by reducing the I/O complexity. In this paper, we propose a new VA-File approach based on a multiresolution data structure. Due to this multiresolution characteristic, we can dramatically reduce the computational complexity of VA-File by eliminating improper candidates with much smaller computation at lower levels. This new method has been applied on the k-nearest neighbor search in the image database and has been compared with the VA-File and multiresolution sequential scan method. The experiment results show that the new multiresolution VA-File can improve the search speed and outperforms the other methods.