What is Approximate Nearest Neighbors (ANN)

Approximate Nearest Neighbors (ANN) is a technique used to approximately find the nearest neighbors of high-dimensional vector data, such as embeddings of text or images, without performing exact calculations.

In high-dimensional vector data, calculating the distance to every data point to find the nearest one can become computationally expensive. Particularly in large datasets or real-time applications, this computational cost can pose a challenge. ANN employs fast and efficient algorithms to swiftly locate the nearest neighbors, allowing for practical-speed neighbor searches. Such algorithms find application in various fields, including similar image retrieval and recommendation systems.

This article introduces the following ANN algorithms:

• LSH (Locality-Sensitive Hashing)
• HNSW (Hierarchical Navigable Small World)
• IVF (Inverted File)

LSH (Locality-Sensitive Hashing)

LSH uses specialized hash functions that ensure similar items are hashed into the same "bucket" with high probability.

LSH Algorithm

The LSH algorithm consists of the following key steps:

1. Hash Function Selection: Choose hash functions that maximize the probability of similar items being placed in the same bucket.
2. Data Hashing: Assign each data point to a bucket using the hash functions.
3. Search within Buckets: Search for data points assigned to the same bucket as the query point.
4. Candidate Refinement: Select the closest data point from the candidates obtained through bucket-based search using further calculations.

HNSW (Hierarchical Navigable Small World)

HNSW represents data using a multi-layered graph structure to efficiently search for nearby data points from query points.

HNSW Algorithm

The HNSW algorithm is composed of the following main steps:

1. Graph Construction: Build a multi-layered graph with data points as vertices.
2. Edge Assignment: Assign edges between close data points to enable efficient exploration on the graph.
3. Hierarchical Search: Begin search from the upper layers of the graph, gradually moving down to find the nearest data point to the query point.

IVF (Inverted File)

Inverted File (IVF) is an efficient method for searching high-dimensional data through clustering.

IVF Algorithm

The basic IVF algorithm is structured as follows:

1. Clustering: Divide data points into several clusters and assign IDs to each cluster.
2. Indexing: Store the relationship between cluster IDs and individual data points in an index (inverted file).
3. Search: When a query is given, identify the nearest cluster and perform detailed distance calculations within that cluster to find the nearest neighbors.

Comparison of Each Method

Speed and Accuracy

• LSH: Offers fast search, but often has lower accuracy compared to other methods.
• HNSW: Balances high accuracy with efficiency, but may require higher memory usage.
• IVF: Enables fast search through indexing, but accuracy can be unstable due to clustering quality.

Memory Usage

• LSH: Generally exhibits good memory efficiency due to the use of hash tables.
• HNSW: Advanced graph structures may lead to higher memory usage.
• IVF: Memory usage increases with data volume due to the need to store index information.

Implementation Complexity

• LSH: Algorithm is simple and can be easily implemented in many programming languages.
• HNSW: Implementation is somewhat challenging due to the complex graph structure.
• IVF: Data structure is relatively simple, but efficient clustering and indexing are required.

References

https://archive.pinecone.io/learn/vector-indexes/