The Power of Asymmetry in Binary Hashing

By Behnam Neyshabur, Nati Srebro, Ruslan Salakhutdinov, Yury Makarychev, Payman Yadollahpour. 2013

71 citations recorded by the source corpus.

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′).

Subfields: Artificial Intelligence, Computer Networks and Communications, Computer Vision and Pattern Recognition, Optimization & Training

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computer Networks and Communications

In Computer Vision and Pattern Recognition

In Optimization & Training

Citations in the corpus

Asymmetric LSH (ALSH) for Sublinear Time Maximum Inner Product Search (MIPS) (2014, methodology): “[20] used a related (asymmetric) idea for solving 3-way similarity search.”
A Survey on Metric Learning for Feature Vectors and Structured Data (2013, background): “Neyshabur et al. (2013) later showed that using asymmetric codes can lead to shorter encodings while maintaining similar performance.”
Large-Scale Supervised Multimodal Hashing with Semantic Correlation Maximization (2014, background): “…and Indyk 2008; Kulis and Darrell 2009; Lin, Ross, and Yagnik 2010; Wang, Kumar, and Chang 2010; Norouzi and Fleet 2011; Kong, Li, and Guo 2012; Heo et al. 2012; Liu et al. 2012a; Kong and Li 2012b; Norouzi, Fleet, and Salakhutdinov 2012; Strecha et al. 2012; Ge et al. 2013; Neyshabur et al. 2013).”
On Symmetric and Asymmetric LSHs for Inner Product Search (2014, methodology): “Recent studies have also explored the power of asymmetry in LSH and binary hashing, where two different mappings f(·), g(·) are used to approximate similarity, sim(x, y) ≈ P[h(x) = g(y)] (Neyshabur et al., 2013, 2014).”
Improved Asymmetric Locality Sensitive Hashing (ALSH) for Maximum Inner Product Search (MIPS) (2014, methodology): “Prior to our work, asymmetry was applied for hashing higher order similarity [22], sketching [8], hashing different subspaces [3], a nd data dependent hashing [20] which unlike locality sensitive hashing do not come with provable runtime guarantees.”
Asymmetric metric learning for knowledge transfer (2020, background): “Asymmetry Asymmetric distances or similarities are common in approximate nearest neighbor search , where queries may be quantized differently than the database, or not at all [12, 17, 34, 32, 45, 10].”
Discrete Graph Hashing (2014, background): “It is interesting to point out that DGH falls into the asymmetric hashing category [26] in the sense that hash codes are generated differently for samples within the dataset and queries outside the dataset.”
Simultaneous feature learning and hash coding with deep neural networks (2015, methodology): “The scheme of such an alternative is similar to the idea of “asymmetric hashing” methods [15], which use two distinct hash coding maps on a pair of images.”
Hashing with binary autoencoders (2015, background): “Some recent work has tried to respect the binary nature of the codes or thresholds by using alternating optimization directly on an objective function, over one entry or one row of the weight matrix in the hash function [16, 21], or over a subset of the binary codes [19, 18].”