Asymmetric distances for binary embeddings

Albert Gordo, Florent Perronnin, Yunchao Gong, Svetlana Lazebnik

Research output: Contribution to journalArticlepeer-review


In large-scale query-by-example retrieval, embedding image signatures in a binary space offers two benefits: data compression and search efficiency. While most embedding algorithms binarize both query and database signatures, it has been noted that this is not strictly a requirement. Indeed, asymmetric schemes that binarize the database signatures but not the query still enjoy the same two benefits but may provide superior accuracy. In this work, we propose two general asymmetric distances that are applicable to a wide variety of embedding techniques including locality sensitive hashing (LSH), locality sensitive binary codes (LSBC), spectral hashing (SH), PCA embedding (PCAE), PCAE with random rotations (PCAE-RR), and PCAE with iterative quantization (PCAE-ITQ). We experiment on four public benchmarks containing up to 1M images and show that the proposed asymmetric distances consistently lead to large improvements over the symmetric Hamming distance for all binary embedding techniques.

Original languageEnglish (US)
Article number6518116
Pages (from-to)33-47
Number of pages15
JournalIEEE transactions on pattern analysis and machine intelligence
Issue number1
StatePublished - Jan 2014


  • Asymmetric distances
  • Binary codes
  • Large-scale retrieval

ASJC Scopus subject areas

  • Software
  • Computer Vision and Pattern Recognition
  • Computational Theory and Mathematics
  • Artificial Intelligence
  • Applied Mathematics


Dive into the research topics of 'Asymmetric distances for binary embeddings'. Together they form a unique fingerprint.

Cite this