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 in pattern recognition where feature vectors in a database are encoded as compact codes in or- der to speed-up the similarity search in large-scale databases. Considering the ANN problem from an information-theoretic perspective, we interpret it as an encoding, which maps the original feature vectors to a less entropic sparse represen- tation while requiring them to be as informative as possi- ble. We then define the coding gain for ANN search using information-theoretic measures. We next show that the clas- sical approach to this problem, which consists of binarization of the projected vectors is sub-optimal. Instead, a properly designed ternary encoding achieves higher coding gains and lower complexity