Abstract. In this survey paper, we consider index structures for fast similarity search of objects represented by real-valued vectors. Structures for both exact and faster, but approximate, similarity search are considered. We present index structures mainly on the basis of partitioning into regions (including hierarchical ones) and neighborhood graphs. The acceleration of the similarity search using the transformation of the original data is also discussed. The ideas of specific algorithms, including the recently proposed ones, are outlined. The approaches to the speed-up of similarity search in the index structures of the considered types and those based on similarity-preserving hashing are discussed and compared.

Keywords: similarity search, nearest neighbor, near neighbor, index structures, branch and bound, trees and forests, clustering, proximity graph, locality-sensitive hashing.