  We develop hierarchically quantized efficient embedding representations for
similarity-based search and show that this representation provides not only the
state of the art performance on the search accuracy but also provides several
orders of speed up during inference. The idea is to hierarchically quantize the
representation so that the quantization granularity is greatly increased while
maintaining the accuracy and keeping the computational complexity low. We also
show that the problem of finding the optimal sparse compound hash code
respecting the hierarchical structure can be optimized in polynomial time via
minimum cost flow in an equivalent flow network. This allows us to train the
method end-to-end in a mini-batch stochastic gradient descent setting. Our
experiments on Cifar100 and ImageNet datasets show the state of the art search
accuracy while providing several orders of magnitude search speedup
respectively over exhaustive linear search over the dataset.
