Abstract: K nearest neighbor (KNN) search is a very challenging research topic in many application areas, such as multimedia information retrieval and data mining. Lots of index structures have been proposed to solve this problem. However, the query performance based on tree-like index structures would decrease drastically with the increase of dimensionality. As a result, ‘the curse of dimensionality’ is brought about and well known in many index structures like R-Tree, X-Tree and SS-Tree, etc.. Researchers also proposed other methods like VA-File to reduce disk I/O cost by compressing data. However, approximate vectors in VA-File are not sorted or classified hierarchically. In this paper, a new index structure VAR-Tree is proposed, which combines VA-File and R-Tree, and employs R-Tree to manage the approximations. A KNN search algorithm is also presented to perform similarity search in a VAR-Tree. Experimental results show that VAR-Tree has a promising retrieval performance.