  Rapid advances in GPU hardware and multiple areas of Deep Learning open up a
new opportunity for billion-scale information retrieval with exhaustive search.
Building on top of the powerful concept of semantic learning, this paper
proposes a Recurrent Binary Embedding (RBE) model that learns compact
representations for real-time retrieval. The model has the unique ability to
refine a base binary vector by progressively adding binary residual vectors to
meet the desired accuracy. The refined vector enables efficient implementation
of exhaustive similarity computation with bit-wise operations, followed by a
near- lossless k-NN selection algorithm, also proposed in this paper. The
proposed algorithms are integrated into an end-to-end multi-GPU system that
retrieves thousands of top items from over a billion candidates in real-time.
The RBE model and the retrieval system were evaluated with data from a major
paid search engine. When measured against the state-of-the-art model for binary
representation and the full precision model for semantic embedding, RBE
significantly outperformed the former, and filled in over 80% of the AUC gap
in-between. Experiments comparing with our production retrieval system also
demonstrated superior performance. While the primary focus of this paper is to
build RBE based on a particular class of semantic models, generalizing to other
types is straightforward, as exemplified by two different models at the end of
the paper.
