The Power of Asymmetry in Binary Hashing
This addresses a bottleneck in binary hashing for similarity search, offering a novel approach that could enhance efficiency in applications like information retrieval, though it appears incremental in nature.
The paper tackles the problem of approximating binary similarity using Hamming distance between short binary hashes, showing that using two distinct code maps instead of one can produce shorter and more accurate hashes, with concrete improvements in accuracy and length.
When approximating binary similarity using the hamming distance between short binary hashes, we show that even if the similarity is symmetric, we can have shorter and more accurate hashes by using two distinct code maps. I.e. by approximating the similarity between $x$ and $x'$ as the hamming distance between $f(x)$ and $g(x')$, for two distinct binary codes $f,g$, rather than as the hamming distance between $f(x)$ and $f(x')$.