Tao: A Learning Framework for Adaptive Nearest Neighbor Search using Static Features Only^††thanks: Hongya Wang is the corresponding author.

Nearest neighbor (NN) search in high dimensional spaces is a challenging problem that has been studied extensively in the past two decades. Formally, let $\mathcal{D}=\{o_{1},\cdots,o_{n}\}\subset\mathbb{R}^{d}$ be a finite set of $n$ vectors. Given query $q\in\mathbb{R}^{d}$, $k$NN search returns $k$ results $o_{i}$ $(1\leq i\leq k)$, where $o_{i}$ is the $i$-th nearest neighbor of $q$. In this paper we use the Euclidean distance as the distance function to measure (dis)similarity between vectors.

As database sizes reach millions or billions of entries, and the vector dimension grows into the hundreds, any indexing method is shown to be reduced to a linear scan of the whole dataset, which is prohibitively expensive in practice [28]. Therefore, practitioners often resort to approximate nearest neighbor search. Instead of identifying exact NNs of a query surely, ANN search sometimes may return neighbors that are only close enough to the query. By trading precision for efficiency, ANN search provides better latency than the exact version.

There is a large amount of significant literature on algorithms for approximate nearest neighbor search, which are roughly divided into four categories: tree-structure based approaches, hashing-based approaches, quantization-based approaches and graph-based approaches. In this paper, we focus on quantization-based and graph-based methods due to their appealing performance and popularity in real-life large scale applications [55].

Product quantization (PQ) algorithm is a lossy compression quantization algorithm that is developed on the basis of vector quantization [27]. By quantizing the vectors of the dataset, it can effectively reduce the storage needed to store the original vectors of the dataset. To the best of our knowledge, quantization-based method is the only one that can support billion-scale datasets on a commodity computer. However, the search is exhaustive for the original PQ – all database vectors must be evaluated.

To avoid exhaustive search, IVFADC [27] uses two quantization levels to organize large datasets. Particularly, IVFADC groups database vectors into different clusters. When building the index, a list of cluster centroids is trained by $K$-means clustering, and each database vector is assigned to the cluster with the closest centroid. During searching, the index first computes the distances between the query and all cluster centroids, then evaluates database vectors belonging to the first nprobe nearest clusters, where nprobe is the hyperparameter that should be determined apriori.

A number of variants of IVFADC are proposed, among which Inverted Multi-Index (IMI) [3] offers the state-of-the-art performance thanks to its efficient space-partitioning strategy. To be specific, IMI decomposes the vectors into several subspaces and trains separate a list of centroids in each subspace, which leads to a fine-grained space partition.

For example, Figure 2 illustrates how IMI generates two product codebooks ${C_{1}}$ and ${C_{2}}$ for different halves of the vector at the first level. Each codebook contains $5$ sub-codewords, leading to $5^{2}$ clusters in total. By subtracting a vector to the corresponding cluster centroids, one obtains the residuals for the second quantization level. Similar to IVFADC, IMI searches the same fixed number of nprobe nearest clusters for all queries.

Graph-based methods such as hierarchical navigable small worlds (HNSW) are currently one of the most efficient ANN search paradigms [41]. HNSW employs hierarchical network structures to organized vectors, and such networks are essentially approximate $k$NN-graphs [54]. To process a query, the graph is traversed starting from the entry point using beam search, and the parameter efSearch is used to control the hops of graph traversal. Greater efSearch is, more accurate answers will be.

For almost all graph-based methods, the ANN search procedure is based on the same principle as illustrated in Figure 3. For a query $q$, start at an initial vertex chosen arbitrarily or using some sophisticated selection rule, say $p$. Moves along an edge to the adjacent vertex with minimum distance to $q$. Repeat this step until the current element $v$ is closer to $q$ than all its neighbors, and then report $v$ as the NN of $q$.

Most existing ANN approaches use fixed configurations that apply the same termination condition to all queries. Li et al. conducted an empirical study over three datasets (Deep/Sift/Gist)¹¹1The detailed description of these datasets are given in Section VI-A using IMI and HNSW implementations in the Faiss library [35]. They observed that, due to the index structures and the vector distributions, the number of database vectors that must be searched to find the ground-truth nearest neighbor varies significantly among queries. Take HNSW as an example, 80% of queries (dubbed “easy queries”) only need to perform at most 547/481/1260 distance evaluations for Deep10M/Sift10M/Gist, respectively, while the other 20% queries (dubbed “hard queries”) require up to 88696/16618/118277 distance evaluations, respectively.

Fixed configurations lead to high average latency because easy queries are forced to conduct a lengthy search as the amount required to deliver reasonable performance for hard queries. To address this issue, Li et al. propose to predict different termination condition for each individual query, making easy queries do less computation than hard ones, thus reducing the end-to-end average latency dramatically.

One central proposition in AdaptNN is that static features alone (e.g., the query vectors themselves) cannot offer good prediction power. To realize highly accurate predictions, it elaborately identifies a set of runtime features of the intermediate search results, and it adopts gradient boosting decision trees to predict the minimum amount of search to perform. As an example, AdaptNN uses the distances between the query and its 1st and 10th neighbors as two runtime features for HNSW.

Figure 1(a) depicts the workflow of AdaptNN. When receiving a query, AdaptNN first invokes the ANN search algorithm and performs a fixed amount of search to obtain the intermediate search results. Thereafter, AdaptNN computes the runtime features, coalesces them with static features, and predicts the termination condition using gradient boosting decision trees. The termination condition is passed down to the ANN search algorithm, which continues to run until the condition is met. Experimental results show that adaptive query processing based on runtime prediction consistently reduces the average end-to-end latency.

AdaptNN, however, faces a number of limitations. Firstly, the input features are chosen in an ad-hoc fashion and one has to try different hand-crafted features for different algorithms. For example, HNSW uses six input features whereas IMI adopts 14 runtime statistics to predict the minimum amount of search, respectively. While the importance of different features are evaluated using the per-feature gain stats from gradient boosting decision tree models (the importance of a feature is proportional to the total error reduction contributed by the feature), this only alleviate the feature engineering efforts and does not address issues such as correlation among features. Hand-crafted feature engineering impedes the application of AdaptNN to other ANN search algorithms not addressed in [35].

Secondly, as noted in [35], if AdaptNN searches less before the feature generation, the intermediate result features may provide less information gain, reducing the prediction accuracy. If we search more before the feature generation, all queries must search more, increasing the end-to-end average latency. As will be discussed shortly, our preliminary experiments show that the end-to-end latency is quite sensitive to the prediction time. Unfortunately, again, AdaptNN provides no principled method or guideline to determine when to predict in runtime.

The pragmatic (currently practiced) way to choose the prediction time adopted by AdaptNN is as follows. Given a dataset, manually choose a set of accuracy targets, say $0.5-0.9$ with a step of $0.1$, and then perform binary search to obtain the corresponding search costs (nprobe or efSearch) for all accuracy targets. To determine the optimal one, one has to run AdaptNN using different prediction times over training datasets and pick the one with the least average latency. Since the tuning process is tedious, time-consuming and lossy in nature, AdaptNN simply uses a fixed prediction time, i.e., the time instant in which 0.8 recall is reached for all datasets by default in practice [35].

Unsurprisingly, we found that the best prediction time is obviously data-dependent. Table I lists the total number of points examined (search cost) under different prediction times (recall already obtained) for a collection of datasets²²2The detailed description of these datasets are given in Section VI-A using AdaptNN with the HNSW method. As one can see 1) the optimal prediction time vary across different datasets and, 2) choosing inappropriate prediction time will cause significant performance degradation. For example, the maximum search cost is twice as much as the minimum for Msong.

The limitations of AdaptNN motivate us to look for a radically different way to perform adaptive ANN query processing. It is claimed in [35] that “static features such as the query vector itself are not sufficient to predict this termination condition”. Counter-intuitively, however, we observe that query vectors themselves, with the help of an intermediate feature local intrinsic dimension, are sufficient to fulfill this goal. Next, we will present the core ideas and workflow of Tao.

Many learning tasks involve data represented as vectors of dimension $d$. For example, an image representation is an embedding function that transforms the raw pixel representation of the image to a point in a high-dimensional vector space. While data are embedded in the space $\mathbb{R}^{d}$, this does not necessarily mean that its intrinsic dimension (ID) is $d$.

The intrinsic dimensionality of a representation refers to the minimum number of parameters (or degrees of freedom) necessary to capture the entire information present in the representation [8]. Equivalently, it refers to the dimensionality of the $m$-dimensional manifold $\mathcal{M}$ embedded within the $d$-dimensional ambient (representation) space where $m\leq d$.

ID has wide applications in many machine learning and data mining contexts. For example, most dimension reduction techniques require that a target dimension be provided by the user. Ideally, the supplied dimension should depend on the intrinsic dimensionality of the data. This has served to motivate the development of models of ID, as well as accurate estimators.

Over the past few decades, many practical models of the intrinsic dimensionality of datasets have been proposed. Examples include the Principal Component Analysis and its variants [7], as well as several manifold learning techniques [31]. Topological approaches to ID estimate the basis dimension of the tangent space of the data manifold from local samples. Fractal methods such as the Correlation Dimension estimate an intrinsic dimension from the space-filling capacity of the data [9]. Graph-based methods use the $k$-nearest neighbors graph along with density in order to estimate ID [11].

The aforementioned intrinsic dimensionality measures can be described as ‘global’, in that they consider the dimensionality of a given set as a whole, without any individual object being given a special role. In other words, all vectors share the same intrinsic dimension. In contrast, ‘local’ ID measures are defined as those that involve only the $k$-nearest neighbor distances of a specific location in the space.

Several local intrinsic dimensionality models have been proposed recently, such as the expansion dimension [30], the generalized expansion dimension [25], the minimum neighbor distance [45], and local continuous intrinsic dimension (LID)[24]. In this paper we focus on LID, which is defined formally as follows:

LID quantifies intrinsic dimension in terms of the rate at which the number of encountered objects grows as the considered range of distances expands from a reference location. Estimates of local ID constitute a measure of the complexity of data and LID could give researchers and practitioners more insight into the nature of their data, and therefore help them improve the efficiency and efficacy of their applications [47].

Amsaleg et al. studied several estimators of LID using maximum likelihood estimation (MLE), the method of moment, probability weighted moment and regularly varying functions [1]. Experimental results show that the performance of different estimators to be largely in agreement with one another, and faster initial convergence favors the choice of MLE for applications where the number of available query-to-neighbor distances is limited, or where time complexity is an issue.

Assume that we are given a sequence $x_{1}$ ,…, $x_{n}$ of observations of a random distance variable $X$ with support [0,$w$) in ascending order, that is, $x_{1}$ $\leq$ $x_{2}$ $\leq$ ··· $\leq$ $x_{n}$. Then, the MLE estimator of LID can be calculated as

By definition, the LID number of a vector $q$ is closed related to the distribution of its near neighbors, which suggests that LID might be a promising indicator for the difficulty in finding $k$NN of $q$. Unfortunately, for an unsee query, there is no way to calculate the LID value without knowing its $k$NN. To circumvent this dilemma, we explore the possibility of predicting LID for unseen vectors using neural networks, considering they are extremely good at capturing complex relationships in high dimensional spaces [33].

Suppose dataset $\mathcal{D}$ is a sample drawn from a population that follows some unknown probability distribution $\mathcal{X}$. For any point $o\sim\mathcal{X}$, we can calculate the LID estimate of $o$ using Equation (1), where $x_{i}$ is the distance between $o$ and its $i$-th NN in $\mathcal{D}$. For unseen vectors, assume there exists a function $f(\cdot)$ that relates any sample vector drawn from $\mathcal{X}$ to a single LID value. The universal approximation theorem tells us that a neural network can approximate $f(\cdot)$, given that $f(\cdot)$ is continuous on a compact set and the neural network has sufficiently many hidden neurons with activation functions [12, 23].

Verifying the continuity of $f(\cdot)$ analytically is impossible because we do not even have an closed-form expression for $f(\cdot)$. To this end, we demonstrate the feasibility by empirically evaluating the approximation errors on several real datasets. Particularly, we trained an MLP network with two hidden fully-connected layers, using 200 neurons per layer (i.e., 200 width) and ReLU activation functions. The inputs to the neural network are exclusively the original vectors and the outputs are the predicted LID values. We use the training vectors listed in Table III to generate training data and the query vectors to generate testing data.

Table II summarizes the statistics of common evaluation metrics for regression models. For mean absolute error (MAE) and RMSE, lower is better. For R2 scores, higher is better. As we can see from the table, we can reliably estimate the LID of query vectors using our regression model. E.g., the MAE of the prediction is less than 1.24 in 6 out of the 8 datasets. We formulate this observation as Property 1:

We further illustrate the real and the predicted LID values in Figure 4 over Deep10M and Sift10M. The $x$-axis represents the LID numbers of vectors calculated using Equation (1), which are partitioned into bins of size 2. The average of predicted LID values in each bin are marked on the top of bars. As we can see, the estimates match rather well with the real values for small LID ($0-14$ for Deep10M and $2-16$ for Sift10M). For large LID, the regression model somewhat underestimates the target values, mainly due to the sparsity of training vectors with large LID numbers. Please note that similar trends are observed for other datasets and we do not report them here due to space limitation.

We also adopt gradient boosting decision tree models (using the LightGBM library [32]) to perform the vector to LID mapping, which achieves similar results with MLP. This suggests that there exists inherent correlation between vectors and LID for all real datasets that we have experimented with, and such correlation may be model independent to some extent. We conjecture that the reason might be these datasets, while represented in high-dimensional spaces, inherently resides on some low-dimensional manifolds [21, 2]. As a result, the relation between vectors and LID can be easily captured using a reasonable regression model. We believe that more in-depth analysis of this correlation deserves further study on its own right, and is thus out of the scope of this paper.

LID is aimed to quantify the local intrinsic dimensionality of a feature space exclusively in terms of the distance distribution of neighbors of a specific location. It is well known that the dimensionality of the space that the point resides in has a significant impact on the difficulty of NN search [20]. Intuitively, the overhead of NN search is probably correlated with the LID of query vectors.

The way to measure search cost varies over different indexing methods. For IMI, the amount of search is represented by the number of nearest clusters that need to be examined (nprobe). For HNSW, we use the number of distance evaluations to represent the amount of search. This is because 1) The distance evaluation between query and database vector is a time-consuming task; 2) The number of distance evaluations fluctuates greatly even with the same number of hops in the graph (efsearch).

Figure 5 illustrates the mean minimum search cost to find the ground truth nearest neighbor for query vectors with different LID using HNSW. The bin size is 2 and the search cost is averaged over each bin. A base 2 logarithmic scale is used for $y$-axis. As one can see, for both Deep10M and Sift10M, the search cost increases roughly exponentially as LID grows, suggesting that LID is a promising static feature to predict the termination condition.

Figure 6 shows the histogram of the mean minimum number of centroids examined to find the ground truth nearest neighbor using IMI. The LID bin size is set to 2 and the search cost is averaged over each bin. As with HNSW, there exists a strong correlation between LID and the number of centroids examined. It is worth mentioning that IMI and HNSW exhibit similar trends for the remaining datasets that have been experimented with, which are not reported here due to space limitation. We highlight such correlations as Property 2:

As discussed above, Property 1 is data dependent and Property 2 depends on both data and algorithms. Given an ANN search algorithm and a dataset, it is possible to accomplish the goal of adaptive query processing as long as these two properties hold. Such simple guidelines turn the learning black box transparent to users to some extent, eliminate the hand-crafted feature selection process and ease the applications of Tao to other ANN algorithms and datasets.

We used seven publicly available real datasets, which are of different data dimensions, cardinalities and types. Table III lists the statistics of datasets we have experimented with. The sizes of these datasets range from millions to one billion.

• •

  Deep1B³³3https://github.com/facebookresearch/faiss/tree/master/ consist of 1 billion contains deep neural codes of natural images obtained from the activations of a convolutional neural network.

• •

  Deep10M⁴⁴4https://github.com/facebookresearch/faiss/tree/master/ is a subset of Deep1B.

• •

  Sift1B⁵⁵5http://corpus-texmex.irisa.fr/ consist of 1 billion 128-dim SIFT vectors.

• •

  Sift10M⁶⁶6https://archive.ics.uci.edu/ml/datasets/SIFT10M consists of 10 million 128-dim SIFT vectors.

• •

  Gist⁷⁷7http://corpus-texmex.irisa.fr/ is an image dataset which contains about 1 million data points.

• •

  ImageNet⁸⁸8 http://cloudcv.org/objdetect/ contains about 2.4 million data points with 150 dimensions dense SIFT features.

• •

  Msong⁹⁹9http://www.ifs.tuwien.ac.at/mir/msd/download.html is a collection of audio features and metadata for millions of contemporary popular music tracks.

• •

  Trevi¹⁰¹⁰10 http://phototour.cs.washington.edu/patches/default.htm consists of around 1,000,000 4096-$d$ vectors.

• •

  Glove¹¹¹¹11 http://nlp.stanford.edu/projects/glove/ contains 1.2 million 100-$d$ word feature vectors extracted from Tweets.

For ImageNet/Msong/Trevi/Glove datasets, due to these datasets do not have a training set or the query set is small, so we split a subset of the database as the training set or query set. Taking ImageNet as an example, we split the first 200,000 of the database into a training set, then we split 200,001 to 210,000 of the database into a query set, and the rest as the new ImageNet base set.

• •

  Fixed Configuration. The implementations of IMI and HNSW in the Faiss ANN search library (CPU version) [35] is used. Parameters to control the answer quality, that is, efSearch (HNSW) and nprobe (IMI), are tuned to achieve the given target accuracy, and fixed for all queries.

• •

  AdaptNN. We use the training and parameter tuning methods described in [35] to obtain the optimal prediction time, which is both algorithm and dataset dependent. In other words, we report the best end-to-end search performance that AdaptNN can deliver for any given algorithm and dataset.

• •

  Tao. Tao employs two neural networks as the regression models. Both neural networks employ two fully connected layers with ReLU activation functions. For the first one, 200 neurons are used for each fully connected layer. The second neural network uses 10 neurons for each fully connected layer.

• •

  Vector Only (VO). VO combines the two neural networks of Tao into one single MLP with five hidden layers. To make fair comparison, the structure of VO is the same as those of Tao, i.e., five hidden layers are fully connected and the number of neurons in each layer are set to 200, 200, 1, 10, 10 respectively. The only difference between VO and Tao is the training process – LID is not used explicitly in VO and the input and output of the neural network of VO are query vectors and the amount of search to find the true NN, respectively.

The end-to-end latency and accuracy are two important metrics for evaluating ANN algorithms. To compare the performance of the baselines and proposed approach, we perform controlled experiments to keep the accuracy achieved by all approaches at the same level, and then to compare the average latency. Given an accuracy target, we perform binary search to find the minimum average latency for the fixed configuration baseline. For AdaptNN and Tao, we multiply the predicted search cost with a coefficient (tuning knob) to reach this desired accuracy. Then we compare their performance at each accuracy target, where the prediction overhead is included in the end-to-end latency.

For the accuracy target, we use recall$@$1 (the fraction of queries where the top-1 nearest neighbor returned from search is (one of) the ground truth nearest neighbor) for HNSW. For IMI, we use recall$@$100 (the fraction of queries where the top-100 nearest neighbors returned from search include (one of) the ground truth nearest neighbor) as the accuracy target since it’s challenging for quantization-based approaches to reach high recall$@$1. We measure the average latency in the single-threaded setting as in previous work [35].

Since the parameters of neural networks are fixed for all datasets, the model size is a constant (560KB) in our experiment setting as well, which is similar to those of AdaptNN (274 KB to 310 KB). When making prediction, it takes around 65us using the Keras framework for Tao (7us to 47us for AdaptNN). While the prediction overhead is very small already, a significant reduction to a few nano seconds is possible if one uses a plain C++ implementation [33]. We leave this as future work since it is not a dominant factor in the end-to-end latency.

Figure 7 compares the average end-to-end latency for plain IMI, AdaptNN and Tao. We choose IMI index with OPQ compression as the baseline, which is one of the state-of-the-art approaches for billion-scale ANN search. We build IMI index with $(2^{14})^{2}$ = 268,435,456 clusters.

All three methods achieve the highest accuracy, i.e., 0.995 for both Deep1B and Sift1B. We stop at these recall targets because it takes too long to reach 1.0 recall for billion-scale database. Overall, our approach provides up to 1.16x and 2.69x speedup on Sift1B and Deep1B, respectively.

To see the big picture, Table IV lists the latencies for three methods at recall$@$100 targets between 0.95 and 0.995. As the target accuracy increases, the gain of Tao over AdaptNN becomes more and more significant and seems to saturate at the highest recall. The reasons may be two-folds: 1) LID is more informative than features collected by AdaptNN; 2) Tao use only the training data obtained with 1.0 recall whereas AdaptNN is trained at a number of accuracy targets ranging from 0.95 from 0.995. It is worth noting that Tao does not take advantage of any runtime feature as AdaptNN does, and still outperforms its counterpart with the optimal configuration.

Figure 8 plots the average end-to-end latencies by comparing plain HNSW, AdaptNN and Tao for highest recalls we have reached. Because of the graph connectivity issue, it is unable to find the nearest neighbor for a few queries in the reasonable time budget. Hence, for different datasets we stop at different recall targets. Overall, Tao provides consistent speedup over AdaptNN from 1.05x to 1.2x for recall$@$1 measure.

Table VIII presents the detailed numbers for different accuracy targets. As one can see, the performance gaps among three methods are less significant for a relatively low recall, say 0.9 for Glove and 0.95 for the other datasets. With the increase of target recall, both AdaptNN and Tao perform better than the original algorithms thanks to their ability to distinguish ‘easy’ queries from ‘hard’ ones.

Table V lists the results of ablation study over Sift10M – the performance of Tao after removing the first regression model. We manually calculate LIDs using Equation (1) for all queries, and pass them to the second neural network. As one can see, the results are only slightly inferior to those using the predicted LID, which demonstrates the efficacy of the vectors-to-LID mapping.

Figure 9 depicts the average minimum search cost (obtained by the Oracle), the overhead incurred by Tao and fixed configurations in a semi-log plot over Deep10M. By partitioning 10,000 queries, sorted in ascending order of the minimum search cost, into 10 bins evenly, we compute the average of minimum search cost in each bin. As we can see, there exists significant variation in the optimal search cost. As discussed before, HNSW with fixed configuration cannot utilize this fact, thus lead to the largest latency. Tao, instead, is equipped with the power to assign smaller search steps for ‘easy’ queries, by which better performance is obtained. Note that the room for optimization is still giant since what Tao predict is still far away from the Oracle, calling for more efficient features and/or prediction models to shrink this gap.

Figure 10 compares the latency of IMI, Tao and VO at the highest recall we achieved, and Table VI lists the detailed numbers including the results of AdaptNN. As we can see: 1) by leveraging the information drawn from query vectors, VO performs better than the plain IMI; 2) without using any runtime features, VO is inferior to AdaptNN, validating the claim made in [35]; 3) LID does matter and helps to obtain the best latency among all approaches. The experimental results of HNSW are in agreement with IMI as shown in Figure 11 and Table VII. One interesting observation made is that, in some cases, the latency of VO is even worse than the original HNSW, which is caused by incorrect prediction.

This set of experimental results indicates that 1) the neural network of VO cannot learn the correlation between query vectors and the amount of NN search without the help of LID; 2) the explicit use of LID not only delivers better performance and makes Tao easy to use in practice, it also makes the black box (learning process) more explainable for users compared with AdaptNN and Vector Only method. This advantage is highly desirable nowadays since explainability is key for users to understand conclusions and recommendations of the prediction model.

For high-dimensional approximate search, the well-known indexing method is locality sensitive hashing (LSH) [20]. The main idea is to use a family of locality-sensitive hash functions to hash nearby data points into the same bucket. After the query point goes through the same hash functions, it will get the corresponding bucket number, and only compare the distance between the point in the bucket and the query point. In the end, the $k$ approximate nearest neighbor results that are closest to the query point will be returned. In recent two decades, many LSH-based variants have been proposed, such as E2LSH [14], QALSH [26], Multi-Probe LSH [40], BayesLSH [46].

E2LSH, the classical LSH implementations for $\ell_{2}$ norm, cannot solve $c$-ANN search problem directly. In practice, one has to either assume there exists a “magical’ radius $r$, which can lead to arbitrarily bad outputs, or uses multiple hashing tables tailored for different radii, which may lead to prohibitively large space consumption in indexing. To reduce the storage cost, LSB-Forest [51] and C2LSH [18] use the so-called virtual rehashing technique, implicitly or explicitly, to avoid building physical hash tables for each search radius.

Based on the idea of query-aware hashing, the two state-of-the-art algorithms QALSH [26] and SRS [49] further improve the efficiency over C2LSH by using different index structures and search methods, respectively. SRS reduces the ANN search problem in a $d$-dimensional space into the range query in an $m$-dimensional projection space (typically $m=6$), and uses $R$-tree to fulfill this purpose. Recently, Lv et al. proposed VHP, which achieves better efficiency by ingeniously restricting the search space to be the intersection of those of QALSH and SRS. All of the aforementioned LSH algorithms provide probability guarantees on the result quality (recall and/or precision).

Other LSH extensions such as Multi-probe LSH [40], SK-LSH [37], LSH-forest [5] and Selective hashing [19] use heuristics to access more plausible buckets or re-organize datasets, and do not ensure any LSH-like theoretical guarantee. A recent paper discussed how to select better hash functions using a deep learning approach [50].

The most influential vector quantization for ANN search is Product Quantization (PQ)  [27]. It seeks to perform a similar dimension reduction to hashing algorithms, but in a way that better retains information about the relative distances between points in the original vector space. Formally, a quantizer is a function $q$ mapping a $d$-dimensional vector $x\in\mathbb{R}^{d}$ to a vector $q(x)\in C=\{c_{i};i\in\mathcal{I}\}$, where the index set $\mathcal{I}$ is assumed to be finite: $\mathcal{I}=0\ldots k-1$. The reproduction values $c_{i}$ are called centroids. The set $\mathcal{V}_{i}$ of vectors mapped to given index $i$ is referred to as a cell, and defined as

The $k$ cells of a quantizer form a partition of $\mathbb{R}^{d}$. So all the vectors lying in the same cell $\mathcal{V}_{i}$ are reconstructed by the same centroid $c_{i}$. Due to the huge number of samples required and the complexity of learning the quantizer, PQ uses $m$ distinct quantizers to quantize the subvectors separately. An input vector will be divided into $m$ distinct subvectors $u_{j}$, $1\leq j\leq m$. The dimension of each subvector is $d^{*}=d/m$. An input vector $x$ is mapped as follows:

where $q_{j}$ is a low-complexity quantizer associated with the $j^{th}$ subvector. And the codebook is defined as the Cartesian product,

and a centroid of this set is the concatenation of centroids of the m subquantizers. All subquantizers have the same finite number $k^{*}$ of reproduction values, the total number of centroids is $k=\left(k^{*}\right)^{m}$.

PQ offers three attractive properties: (1) PQ compresses an input vector into a short code (e.g., 64-bits), which enables it to handle typically one billion data points in memory; (2) the approximate distance between a raw vector and a compressed PQ code is computed efficiently (the so-called asymmetric distance computation (ADC) and the symmetric distance computation (SDC)), which is a good estimation of the original Euclidean distance; and (3) the data structure and coding algorithm are simple, which allow it to hybridize with other indexing structures.

Original PQ requires examining all vectors during ANN search. To handle billion-scale datasets, advanced indexing structures such as IMI and IVF are developed [3, 27].

The vast majority of graph-based indexing schemes are designed based on three types of theoretical graph models, that is, Delaunay Graphs [34], Relative Neighbor Graphs [52] and $K$-Nearest Neighbor Graphs [42, 15]. In practice, however, most search graphs are essentially approximate $K$-nearest neighbor graphs, which mainly distinguish oneself from the other in the edge selection policies.

Inspired by HNSW, several follow-up projects aim to improve the proximity graph-based approach. Douze et al. propose to combine HNSW with quantization [16]. Navigating Spreading-out Graph (NSG) aims to reduce the graph edge density while keeping the search accuracy [17]. SPTAG combines the IVF index and proximity graph for distributed ANN search[10]. As with HNSW, all of these proximity graph variants employ fixed configurations to perform a fixed amount of graph traversal for all queries. Interested readers are referred to a recent survey for more detailed discussion [56], where useful recommendations and guidelines are given for users to choose appropriate graph-based algorithms.

In this subsection, we would like to highlight a few studies focusing on external memory graph-based indices, which may be of great interests to database researchers. This line of research is imperative since the sizes of datasets can easily exceeds capacity of available main memory in a commodity server as more and more vectors are produced with the ubiquity of machine learning techniques.

To the best of our knowledge, Bin Wang et al. first presented ideas to explore slow storage to achieve billion-scale ANNS in a single machine [53]. HM-ANN maps the hierrchical design of the graph-based ANNS with memory heterogeneity in HM, thus most accesses will happen in upper layer stored in fast memory to avoid expensive accesses in slow memory without sacrificing accuracy [44]. Vamana fully analyzes the construction details of HNSW and NSG, based on which Vamana uses the random neighbor selection strategy of HNSW to increase the flexibility of edge selection. As a result, it is able to construct a high recall SSD index on a single server of 64G [48]. Minjia Zhang et al. presented an ANN solution ZOOM that uses SSD to employ a multi-view approach. Through the efficient routing and optimized distance computation, ZOOM greatly enhance the effectiveness and efficiency while attaining equal or higher accuracy [58].