Sparse Ternary Codes for similarity search have higher coding gain than\n dense binary codes

2017/01/26 by Sohrab Ferdowsi, Ferdowsi, Sohrab, Slava Voloshynovskiy +5
Computer Science · #Advanced Image and Video Retrieval Techniques #Machine Learning and Algorithms #Algorithms and Data Compression

paper · pdf · doi:10.48550/arxiv.1701.07675

Abstract

This paper addresses the problem of Approximate Nearest Neighbor (ANN) search\nin pattern recognition where feature vectors in a database are encoded as\ncompact codes in order to speed-up the similarity search in large-scale\ndatabases. Considering the ANN problem from an information-theoretic\nperspective, we interpret it as an encoding, which maps the original feature\nvectors to a less entropic sparse representation while requiring them to be as\ninformative as possible. We then define the coding gain for ANN search using\ninformation-theoretic measures. We next show that the classical approach to\nthis problem, which consists of binarization of the projected vectors is\nsub-optimal. Instead, a properly designed ternary encoding achieves higher\ncoding gains and lower complexity.\n

Related

• A multi-layer network based on Sparse Ternary Codes for universal vector compression
• Nearest neighbor search with compact codes: A decoder perspective
• Polysemous codes
• Anti-sparse coding for approximate nearest neighbor search
• Learning Better Encoding for Approximate Nearest Neighbor Search with Dictionary Annealing