Despite Hashing codes and PQ codes can enable the fast computation between the query and each reference item, when the number of reference items in the database is large, the time cost is still costly.
To make the retrieval more scalable to large-scale dataset, some non-exhaustive search methods are proposed. Inverted multiple indexing (IMI) [1]} is one of the most popular methods for non-exhaustive search. Basically, it partitions the feature space into fine cells through the k-means. It only computes the similarity between the query and the cell centroids. Since the number of centroids is significantly smaller than the number of reference items, the efficiency is considerably boosted. In parallel, K-Dimensional tree [2]} is another widely used strategy for avoiding comparing the query with each item exhaustively. It builds a binary search tree to partition the feature space, and formulates the retrieval into a tree traverse problem. Recently, TDM [3]} also exploits the tree structure to boost the efficiency of deep models deployed in recommendation system. The core idea is that, it only evaluate the expensive deep models in a small subset of tree nodes and avoids evaluating the deep models on all items in the database.
