Abstract. In this survey paper, we consider index structures for fast similarity search of objects represented by real-valued vectors. Index structures based on locality-sensitive hashing and their modifications are considered. The ideas of specific algorithms, including the recently proposed ones, are outlined. Their interrelations and some theoretical aspects are discussed.

Keywords: similarity search, nearest neighbor, near neighbor, index structures, locality-sensitive hashing, locality-sensitive filtering.