Abstract. In this survey paper we consider the class of index structures for fast similarity search that uses for index construction and application only information about the values or ranks of some distances/similarities between objects. We discuss the search by metric distances (for which the triangle inequality and other metric axioms are valid), as well as by non-metric ones. Considered index structures include those returning the objects of the base that are exact results to the similarity search query, and index structures for approximate similarity search, which do not guarantee the accuracy, but usually return close to accurate results and work faster than the structures for exact search. Some general principles for construction and usage of index structures as well as some ideas of specific algorithms, including recently proposed ones, are discussed.
Keywords: similarity search, nearest neighbor search, index structures, distance-based indexing, metric distances, non-metric distances, metric trees, proximity graph, branch and bound.
International Scientific-Educational Center of Information Technologies and Systems, NAS of Ukraine and MES
of Ukraine, Kyiv, Ukraine,
e-mail: dar@infrm.kiev.ua.