Binary Vectors for Fast Distance and Similarity Estimation

详细信息    查看全文

• 作者：D. A. Rachkovskij
• 关键词：distance ; similarity ; embedding ; sketch ; random projection ; sampling ; binarization ; quantization ; Johnson–Lindenstrauss lemma ; kernel similarity ; similarity search ; locality ; sensitive hashing
• 刊名：Cybernetics and Systems Analysis
• 出版年：2017
• 出版时间：January 2017
• 年：2017
• 卷：53
• 期：1
• 页码：138-156
• 全文大小：
• 刊物类别：Mathematics and Statistics
• 刊物主题：Systems Theory, Control; Artificial Intelligence (incl. Robotics); Processor Architectures; Software Engineering/Programming and Operating Systems;
• 出版者：Springer US
• ISSN：1573-8337
• 卷排序：53

文摘

This review considers methods and algorithms for fast estimation of distance/similarity measures between initial data from vector representations with binary or integer-valued components obtained from initial data that are mainly high-dimensional vectors with different distance measures (angular, Euclidean, and others) and similarity measures (cosine, inner product, and others). Methods without learning that mainly use random projections with the subsequent quantization and also sampling methods are discussed. The obtained vectors can be applied in similarity search, machine learning, and other algorithms.