Rachkovskij D.A.
Real-valued embeddings and sketches for fast distanceand similarity estimation

This survey article considers methods and algorithms for fast estimation of data distance/similarity measures from formed real-valued vectors of small dimension. The methods do not use learning and mainly use random projection and sampling. Initial data are mainly high-dimensional vectors with different measures of distance (Euclidean, Manhattan, statistical, etc.) and similarity (dot product, etc.). Vector representations of non-vector data are also considered. The resultant vectors can also be used in similarity search algorithms, machine learning, etc. © 2016, Springer Science+Business Media New York.

Keywords: dimensionality reduction, distance, embedding, Johnson–Lindenstrauss lemma, kernel similarity, random projection, sampling, similarity, similarity search, sketch, Artificial intelligence, Learning systems, Sampling, Dimensionality reduction, distance, embedding, kernel similarity, Random projections, similarity, Similarity search, sketch, Vectors

Cite:
Rachkovskij D.A. (2016). Real-valued embeddings and sketches for fast distanceand similarity estimation. Cybernetics and Systems Analysis, 52 (6), 156-180. doi: https://doi.org/10.1007/s10559-016-9899-x http://jnas.nbuv.gov.ua/article/UJRN-0000582985 [In Russian].