  In this paper, we aim to learn a mapping (or embedding) from images to a
compact binary space in which Hamming distances correspond to a ranking measure
for the image retrieval task.
  We make use of a triplet loss because this has been shown to be most
effective for ranking problems.
  However, training in previous works can be prohibitively expensive due to the
fact that optimization is directly performed on the triplet space, where the
number of possible triplets for training is cubic in the number of training
examples.
  To address this issue, we propose to formulate high-order binary codes
learning as a multi-label classification problem by explicitly separating
learning into two interleaved stages.
  To solve the first stage, we design a large-scale high-order binary codes
inference algorithm to reduce the high-order objective to a standard binary
quadratic problem such that graph cuts can be used to efficiently infer the
binary code which serve as the label of each training datum.
  In the second stage we propose to map the original image to compact binary
codes via carefully designed deep convolutional neural networks (CNNs) and the
hashing function fitting can be solved by training binary CNN classifiers.
  An incremental/interleaved optimization strategy is proffered to ensure that
these two steps are interactive with each other during training for better
accuracy.
  We conduct experiments on several benchmark datasets, which demonstrate both
improved training time (by as much as two orders of magnitude) as well as
producing state-of-the-art hashing for various retrieval tasks.
