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

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