Approximate Nearest Neighbor (ANN) Search Implementation

ANN search algorithm

Approximate Nearest Neighbor (ANN) is a way of efficiently returning points that are close to the given query points. This approach proves to be better in many circumstances than the Exact Nearest Neighbor (EEN) search algorithm, as the former provides a balance between accuracy and efficiency. For example, there is a movie dataset with their genres and budget. $q2$ has a similar genre and budget with the query (action movie with high budget), while $q1$ has the same budget as a drama movie, $q10$ has the low budget action movie, and $q3$ has the medium budget action movie. So that, $q1$, $q10$, $q2$, and, $q3$ are the closest data points but not the accurate ones. In this case, $q2$ the nearest closing data point is the most accurate.

To understand how ANN works, let's break down its steps.

How the ANN search algorithm works

Here are the steps of how this algorithm works:

• Data preprocessing: This step is completely optional. Depending on the distance metric used and data characteristics, we might need to normalize or standardize our data to ensure all features are on a similar scale. This can improve the effectiveness of distance calculations.

• Distance metric selection: Choose an appropriate distance metric to measure the similarity between data points. Depending on our data and application, common choices include Euclidean distance, Manhattan distance, cosine similarity, or others.

• Data structure creation: This step varies based on our specific ANN algorithm. Some of the common approaches include Random projection trees, LSH, HNSW, and Metric trees.

  • Random projection tree: Random projection trees create multiple trees by recursively splitting the data using random hyperplanes. Each tree partitions the data space differently, providing a diverse set of partitions to enhance search efficiency. This method excels in high-dimensional spaces by reducing the complexity of distance calculations and improving query times, making it highly effective for large-scale nearest neighbor searches.

  • LSH: Locality-Sensitive Hashing (LSH) algorithms create hash tables where data points are mapped to buckets based on hash functions. These functions aim to preserve proximity in the original space, allowing efficient search within relevant buckets for similar items.

  • HNSW: Hierarchical Navigable Small World (HNSW) graphs build a graph structure connecting data points. The connections prioritize local and global relationships, facilitating efficient exploration during the search.

  • Metric Trees: These trees organize data points based on their distances from a set of vantage points. They can be useful for specific applications where some prior knowledge about the data distribution is available.

• Query processing: Once we have our data structure in place, we can process a query point. Some of the common approaches include Random projection trees, LSH, HNSW, and Metric trees. In the example below, we are using Random projection trees. Random projection trees search across multiple random projection trees to find nearest neighbors. Aggregate results from different trees to provide a list of approximate nearest neighbors.

• Similarity calculation and result selection: For each retrieved item (data point) from the search process, calculate the actual distance metric (e.g., Euclidean distance) between the query point and the retrieved item. Select the most similar items based on the calculated distances. We can either specify a desired number of nearest neighbors (k-NN) or choose a threshold on the distance metric.

Now, let's compare ANN with the Exact Nearest Neighbor (ENN) search algorithm to highlight their differences.

Comparison with Exact Nearest Neighbor (ENN) search

As we see, the ANN algorithm does not give us the exact closest data point. So, here we compare ANN with the Exact Nearest Neighbor Search algorithm.