
Hash-based methods. Traditionally, hashing-based methods [1]}, [2]}, [3]}, [4]}, [5]}, [6]}, [7]}, [8]}, [9]}, [10]}, [11]}, [12]} partition the base vectors into a constant number of buckets via a specific hashing function. The chosen hashing function guarantees a collision probability is positively correlated to the specific similarity of two vectors, i.e., similar vectors have a high probability to be assigned to the same hash bucket. Relatively recently, learning to hash methods [13]}, [14]}, [15]}, [16]}, [17]} become popular. Typically they learn the hashing on a sample of data so that the learned hash function can better fit the data distribution compared with the classic data-independent hashing algorithms.

Tree-based methods [18]}, [19]}, [20]}, [21]}, [22]}, [23]}, [24]} partition the high-dimensional data space into smaller regions via a decision tree/space partitioning tree. The partitioned spaces are organized within a tree: A leaf node in the tree corresponds to the finest granularity of the partitioned space, and edges between tree nodes represent the hierarchical relationship of partitioned spaces. [25]} recently propose a tree-based method that builds an inverted index for each label/attributes. It is infeasible to build an index for each label combination without prior knowledge of the query constraints. Our proposed solution performs the original index and does not need to build any additional indices. Moreover, we do not need to know the query constraints beforehand.

Quantization-based algorithms [26]}, [27]}, [28]}, [29]}, [30]}, [31]} learn a code-book from base vectors and quantize the original high-dimensional vectors into a low-dimensional quantized values. The quantized value is a low-dimensional representation of the original vectors. The distances between quantized vectors approximate the distances between original vectors.

Graph-based algorithms achieve a lot of attention recently due to its superior performance to other similarity search techniques on many real-world datasets and industrial applications [32]}, [33]}, [34]}, [35]}, [36]}, [37]}, [38]}, [39]}, [40]}. Graph-based algorithms build a proximity graph as an index and perform a graph searching to answer the query. We investigate the constrained similarity search on the graph-based algorithm. Recently, [41]} develop the first GPU-based graph-based ANN algorithm.

Neural ranking. To resolve issues related to proximity search in various neural models, in recent years, the subject of “neural ranking” has attracted increasingly more attentions [42]}, [43]}, [44]}, [45]}, [46]}, [47]}, [48]}, [49]}. Effective algorithms for neural ranking can be very desirable in practice. For example, while the standard “two-tower” model is popular and fairly effective, practitioners might hope to replace the simple “cosine” loss function with a most sophisticated deep neural nets for better retrieval accuracy. However, once we have replaced the cosine by a neural net, we can no longer use the standard ANN techniques to achieve fast ranking.

