The similarity search of images can be transformed into the point matching in the high-dimensional vector space by the feature extraction and transformation. In order to reduce the curse of dimensionality, a new Vector Approximation File approach based on the multi-resolution data structure is proposed. The new approach computes the lower bound of distance from low-resolution level. If it is larger than the latest maximum distance in the result set, the candidate can be removed without calculating the full-resolution distance. The computational time can be dramatically reduced by eliminating improper candidates at lower levels. The algorithm supporting k-nearest neighbor search is also presented in the new approach and has been applied for feature matching in the large image data sets. The experiment results show that the new approach improves the k-nearest neighbor search speed and outperforms the Vector Approximation File approach.