This chapter contains functions for computing the approximate nearest neighbors of a test data set and a training data set.
Approximate nearest neighbors (ANN) is a technique for efficiently finding points in a dataset that are close to a given query point, without requiring an exhaustive search through all data points. Unlike exact nearest neighbor search, which guarantees finding the true nearest neighbors, ANN algorithms trade some accuracy for improvements in runtime. For each point \(x_i\) in a test set \(X_{test}\), these algorithms compute the approximate \(k\) nearest points to \(x_i\) from a reference dataset \(X\).
AOCL-DA implements the IVFFlat algorithm for approximate nearest neighbor search (Sivic and Zisserman [2003]). This algorithm organizes data into a search structure called an inverted file index. The index partitions data into clusters, each defined by a centroid, to enable fast approximate queries.
During training, k-means clustering is applied to the training data to compute \(n_{list}\) centroids. The train fraction option controls how much of the training data is used for k-means clustering; using a smaller value can speed up training for large datasets while still producing a reasonable partition. The k-means_iter option sets the maximum number of k-means iterations. Note that training only computes the centroids; no data is stored in the index at this stage.
To populate the index, data must be explicitly added using a separate add operation. Each point is assigned to its nearest centroid, and a list of points is stored for each centroid. Additional data can be added at any time after training without recomputing the centroids.
At search time, rather than comparing the query point against all indexed data, IVFFlat first identifies the \(n_{probe}\) centroids closest to the query. Only the points assigned to these centroids are then searched exhaustively. This provides a speedup over brute-force search. However, if one of the true nearest neighbors is assigned to a centroid not among the \(n_{probe}\) closest, it will be missed.
The key parameters for controlling the accuracy-speed trade-off are \(n_{list}\) (the number of centroids) and \(n_{probe}\) (the number of centroids to search). Larger \(n_{list}\) creates more centroids with fewer points each. Larger \(n_{probe}\) improves recall at the cost of search speed; setting \(n_{probe} = n_{list}\) recovers exact search. A common guideline is to set \(n_{list} \approx \sqrt{N}\) for a dataset of size \(N\), and \(n_{probe}\) to a small fraction of \(n_{list}\) depending on the desired recall.
The metric option determines how nearness is measured. The available metrics are:
Euclidean distance: \(d(x,y) = \sqrt{\sum_i (x_i - y_i)^2}\).
Squared Euclidean distance: \(d(x,y) = \sum_i (x_i - y_i)^2\).
Cosine distance: \(d(x,y) = 1 - \frac{x^\mathrm{T}y}{\|x\| \|y\|}\).
Inner product: \(\langle x, y \rangle = x^\mathrm{T}y\).
The squared Euclidean distance omits the square root computation, making it slightly faster to compute while preserving the same ordering of neighbors as Euclidean distance.
For euclidean and sqeuclidean metrics, standard k-means clustering is used during training. For cosine and inner product, spherical k-means clustering is used instead, which normalizes the centroids to unit length at each iteration (Dhillon and Modha [2001]).
For euclidean, sqeuclidean, and cosine, the points with the smallest distances to the query are returned. For inner product, maximum inner product search is performed, returning the points with the largest inner products with the query.