Index structures for fast similarity search of real-valued vectors. I / Rachkovskij. (2018)
Ukrainian

English  Cybernetics and Systems Analysis   /     Issue (2018, 54 (1))

Rachkovskij D.A.
Index structures for fast similarity search of real-valued vectors. I

This survey article considers index structures for fast similarity search for objects represented by real-valued vectors. Structures for both exact and faster but approximate similarity search are considered. Index structures based on partitioning into regions (including hierarchical ones) and on proximity graphs are mainly presented. The acceleration of similarity search using the transformation of initial data is also discussed. The ideas of concrete algorithms including recently proposed ones are outlined. The approaches to the acceleration of similarity search in index structures of the considered types and also on the basis of similarity-preserving hashing are discussed and compared. © 2018, Springer Science+Business Media, LLC, part of Springer Nature.

Keywords: branch and bound method, clustering, index structure, locality-sensitive hashing, near neighbor, nearest neighbor, proximity graph, similarity search, tree and forest, Metadata, Nearest neighbor search, clustering, Index structure, Locality sensitive hashing, near neighbor, Nearest neighbors, Proximity graphs, Similarity search, tree and forest, Branch and bound method


Cite:
Rachkovskij D.A. (2018). Index structures for fast similarity search of real-valued vectors. I. Cybernetics and Systems Analysis, 54 (1), 168-183. doi: https://doi.org/10.1007/s10559-018-0034-z http://jnas.nbuv.gov.ua/article/UJRN-0000805867 [In Russian].


 

Institute of Information Technologies of VNLU


+38 (044) 525-36-24
Ukraine, 03039, Kyiv, Holosiivskyi Ave, 3, room 209