Anti-sparse coding for approximate nearest neighbor search

This paper proposes a binarization scheme for vectors of high dimension based the recent concept of anti-sparse coding, and shows its excellent for approximate nearest neighbor search. Unlike other binarization, this framework allows, up to a scaling factor, the explicit from the binary representation of the original vector. The paper shows that random projections which are used in Locality Sensitive Hashing, are significantly outperformed by regular frames for both synthetic real data if the number of bits exceeds the vector dimensionality, i.e., high precision is required.