Cybernetics And Systems Analysis logo
Editorial Board Announcements Abstracts Authors Archive
Cybernetics And Systems Analysis
International Theoretical Science Journal
UDC 004.22+004.93'11
D.A. Rachkovskij

DISTANCE-BASED INDEX STRUCTURES FOR FAST SIMILARITY SEARCH

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.



FULL TEXT

International Scientific-Educational Center of Information Technologies and Systems, NAS of Ukraine and MES of Ukraine, Kyiv, Ukraine,
e-mail: dar@infrm.kiev.ua.

© 2017 Kibernetika.org. All rights reserved.