The Power of Asymmetry in Binary Hashing
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 ).
This paper suggested constructing different binary 
      data representation using different hash functions in the asymmetric theme 
      to possibly reduce the encoding length. Encoding data as compactly as 
      possible is no doubt important to theory and practice of approximate 
      nearest neighbor search. Detailed comments: 1. A major 
      concern of the asymmetric design is the consistency of the results. In 
      Eqns. (2) (3) and Theorem 1, there is no constraint enforcing Y's 
      symmetry, although there was a sentence vaguely mentioning this issue 
      below Eqn. (2). Therefore, by this design it is very possible to obtain 
      inconsistent results such as < u(x), v(y) > ~= < u(y), v(x) >, 
      which means that the learned hash functions CANNOT support a distance 
      metric. And in the actual experiments, the authors used whether a certain 
      point x is in the database to determine which hash function to use, which 
      is ad-hoc and lacks any ground support. Hence, this asymmetric design on 
      this hand makes the theoretical model inconsistent and broken, and on the 
      other hand weakens the experimental evidence, considering that too many 
      parameters were used. 2. Some recent important state-of-the-art 
      hashing methods are missing, e.g., Yunchao Gong, S. Lazebnik, A. 
      Gordo, and F. Perronnin. Iterative Quantization: A Procrustean Approach to 
      Learning Binary Codes for Large-scale Image Retrieval. TPAMI 2012. W. 
      Liu, J. Wang, S. Kumar, and S.-F. Chang. Hashing with Graphs. ICML 2011. 
      W. Liu, J. Wang, R. Ji, Y.-G. Jiang, and S.-F. Chang. Supervised 
      Hashing with Kernels. CVPR 2012. The experiments only compared 
      with some baselines known to be problematic in the short-bit setting such 
      as LSH, thus are not too convincing. In addition, kernel-based supervised 
      hashing (the CVPR12 paper mentioned above) has shown superior performance 
      over BRE and MLH. Why not cited and compared? The idea of manipulating 
      code inner products was proposed by this work. The authors should give 
      clear credit to the CVPR12 paper when using code inner products in their 
      method. The authors also need to clarify the relationship and difference 
      with the prior asymmetric hashing work [3] (cite the PAMI version). 
      3. L084-085: the value for < u, v > seems incorrect. 
      4. L142-152: aka, second part of proof to Theorem 1; Line 142, it 
      should be ks(S) >= n/2; Line 143, why \theta is in that range? Can the 
      authors explain? Line 146-150: how to move to the upper bound, in 
      particular for the latter two terms? The current derivation is doubtful. 
      5. Part 4-5: There is an important turn from approximation to 
      generalization, which makes the main thrust of the paper. My major 
      concerns are: 1) Even if we know that compact codes are possible, why 
      is a linear threshold function one appropriate choice for forming hash 
      functions? 2) Given that in advance we do not know the data space 
      much, how to choose k properly in Eqn. (3)? This could be a hard decision 
      in practice. I think that a more pertinent version could fix an 
      approximation tolerance, and minimize k instead. The presentation in Part 
      4 is loose. Overall, I think that the asymmetric 
      similarity/distance approximation problem and some results in the paper 
      are interesting. When treating practical problems, the proposed methods 
      (Part 4-5) stay at the heuristic level and do not correspond well to the 
      former claim. The bottom line is that the heuristics are justified by 
      sufficient experiments with positive results. In addition, I think that 
      the authors should put more efforts on polishing their paper, in view of 
      numerous statement problems and grammatical 
      errors.