# Approximate Nearest Neighbor (ANN)

<mark style="color:blue;">**Approximate Nearest Neighbor (ANN)**</mark> is a search algorithms used for extracting high-dimensional unstructured data such as images, text, and audio from vector databases.

These algorithms, by focusing on approximation rather than exact matches, strike a balance between speed and accuracy, enabling efficient similarity searches in vast datasets.

ANN search algorithms operate on the principle that in many applications, an exact nearest neighbor search is unnecessarily precise and computationally expensive.&#x20;

{% embed url="<https://arxiv.org/abs/1806.09823>" %}
Approximate Nearest Neighbor (ANN)
{% endembed %}

### <mark style="color:purple;">Understanding ANN Search</mark>

The nearest neighbour problem involves finding the <mark style="color:yellow;">closest point in a set</mark> $$P$$ to a given <mark style="color:yellow;">query point</mark> $$q$$ in a <mark style="color:yellow;">metric space</mark>.&#x20;

To <mark style="color:yellow;">enhance efficiency in terms of computation and memory usage</mark>, the concept of approximate nearest neighbour (ANN) is introduced, where the goal is to find a point $$′p′$$ in $$P$$ such that its distance to $$q$$ is within a factor $$c$$ (<mark style="color:blue;">approximation factor</mark>) of the actual nearest neighbour's distance.

### <mark style="color:green;">**Trade-off Between Query Time and Space**</mark>

Early solutions to the nearest neighbour problem demonstrated a trade-off between the time it takes to answer a query (query time) and the amount of memory used (space).&#x20;

The challenge has been to develop data structures that reduce both these factors effectively.

<mark style="color:blue;">**Data-independent Approaches**</mark><mark style="color:blue;">:</mark> These approaches do not rely on the specific dataset $$P$$ but instead use methods like <mark style="color:yellow;">dimension reduction and randomized space partitions</mark> to pre-process the space, making the search for nearest neighbours more efficient.

<mark style="color:blue;">**Dimension Reduction**</mark><mark style="color:blue;">:</mark> One key strategy for ANN involves <mark style="color:yellow;">reducing the dimensionality of the data</mark> before applying nearest neighbour algorithms. This can significantly decrease space and time complexity, as seen in the Johnson-Lindenstrauss lemma, which facilitates this reduction while preserving distance relationships to a certain degree.

<mark style="color:blue;">**Locality-Sensitive Hashing (LSH)**</mark><mark style="color:blue;">:</mark> LSH is a method in constructing efficient ANN data structures, characterised by hashing that ensures <mark style="color:yellow;">closer points have a higher probability of colliding in the hashed space</mark>. This method balances the space and query time more favourably and is adaptable to various metric spaces.

Here are some key equations representing how Approximate Nearest Neighbour (ANN) works:

### <mark style="color:green;">**Nearest Neighbour**</mark>

For a set $$P$$ of $$n$$ points in a metric space $$(X,D)$$, and a query point $$q∈X$$, the nearest neighbour is defined as: $$( \text{NN}(q) = \arg\min\_{p \in P} D(q, p) )$$

### <mark style="color:green;">**Approximate Nearest Neighbour**</mark>

The goal in ANN is to find a point $$p∈P$$ such that: $$( D(q, p') \leq c cdot min\_{p in P} D(q, p) )$$ where $$≥1c≥1$$ is the approximation factor.

These equations encapsulate the core mathematical concepts underpinning the ANN search methodology, illustrating the trade-offs between accuracy and computational efficiency inherent in the problem.

*<mark style="color:yellow;">**By accepting a degree of approximation, ANN searches significantly reduce the time and resources required to find similar items within large datasets.**</mark>* This trade-off is particularly valuable in real-world applications where speed and efficiency are paramount, and an exact match is not strictly necessary.

### <mark style="color:purple;">Locality-Sensitive Hashing (LSH)</mark>

Locality-Sensitive Hashing (LSH) is a technique used to solve the Approximate Nearest Neighbour (ANN) search problem efficiently, especially in high-dimensional spaces.&#x20;

#### <mark style="color:green;">Fundamentals of LSH</mark>

**Hashing Families**: LSH uses a family of hash functions designed so that closer points in the space are more likely to collide (have the same hash value) than points that are far apart.&#x20;

This family is defined by four parameters $$(r,cr,p1​,p2​)$$

&#x20;where:

* If the distance $$( D(x, y) \leq r )$$ then $$( \Pr\[h(x) = h(y)] \geq p\_1 )$$
* If the distance $$( D(x, y) > cr )$$, then $$( \Pr\[h(x) = h(y)] \leq p\_2 )$$
* Here, $$>1c>1$$ is the approximation factor, and $$>0r>0$$ is a scale parameter.

1. **Quality Parameter** $$ρ$$: The effectiveness of an LSH family is often measured by the parameter $$\[ \rho = \frac{\log(1/p\_2)}{\log(1/p\_1)} ]$$, where $$ρ<1$$. The smaller $$ρ$$ is, the more effective the LSH family is at distinguishing between close and distant neighbours.

Below is a great article on LSH:

{% embed url="<https://towardsdatascience.com/similarity-search-part-5-locality-sensitive-hashing-lsh-76ae4b388203>" %}

### <mark style="color:green;">LSH for ANN</mark>

<mark style="color:blue;">**Data Structure Construction**</mark><mark style="color:blue;">:</mark> LSH-based data structures for ANN are built by using multiple hash tables. Each table uses a hash function (or a composite hash function) drawn from the LSH family.

<mark style="color:blue;">**Query Processing**</mark><mark style="color:blue;">:</mark> To find the approximate nearest neighbours of a query point $$q$$, LSH computes the hash values of $$q$$ using the same hash functions and looks up points in the corresponding buckets across the hash tables. The points in these buckets are then considered as candidate nearest neighbours.

<mark style="color:blue;">**Enhancing Accuracy**</mark><mark style="color:blue;">:</mark> By using multiple hash tables (each with potentially a composite hash function created by concatenating multiple LSH functions), the probability of missing the true nearest neighbour is reduced. Essentially, even if a neighbor is missed in one table, it might be caught in another.

<mark style="color:blue;">**Limitations**</mark><mark style="color:blue;">:</mark> The effectiveness of LSH is inherently tied to the dimensionality and intrinsic structure of the data. While LSH offers a powerful framework for ANN, its performance can degrade in ultra-high-dimensional spaces or when the data does not align well with the chosen LSH family.

LSH provides a scalable and efficient framework for performing approximate nearest neighbour searches in high-dimensional spaces, balancing the trade-offs between space, accuracy, and computational time.

### <mark style="color:purple;">Categories of ANN Algorithms</mark>

ANN algorithms can be categorized based on their underlying mechanisms and structures. Each category has its unique advantages and is suited to particular types of data or applications.

<mark style="color:green;">**Tree-based Methods**</mark>

Tree-based algorithms, such as k-d trees, ball trees, and ANNOY, use tree data structures to partition the search space, facilitating efficient navigation and search. While these methods are effective for lower-dimensional data, they tend to struggle with the "curse of dimensionality," making them less suitable for very high-dimensional spaces.

<mark style="color:green;">**Quantization-based Methods**</mark>

Quantization involves compressing the search space to reduce both storage and computational demands. &#x20;

Techniques like IVF\_FLAT, IVF\_SQ8, and IVF\_PQ work by first dividing the vector space into clusters using a predefined number of centroids.&#x20;

During the encoding process, each vector is assigned to its nearest centroid, and the vectors within each cluster are encoded using different quantization strategies.

IVF\_FLAT stores vectors directly, IVF\_SQ8 applies scalar quantization to reduce dimension size, and IVF\_PQ uses product quantization to split vectors into subspaces.&#x20;

This clustering and encoding reduce both storage requirements and search complexity, enabling efficient retrieval in high-dimensional spaces.

<mark style="color:green;">**Graph-based Methods**</mark>

Graph-based algorithms represent the search space as a graph, with nodes corresponding to vectors and edges linking similar vectors.&#x20;

Techniques like HNSW and NGT leverage graph traversal to efficiently locate nearest neighbours. These methods are known for their rapid search capabilities and resilience against the curse of dimensionality.

<mark style="color:green;">**Deep Learning-based Methods**</mark>

Deep learning approaches, including autoencoders and specialized neural networks, learn compact vector representations for efficient similarity searches. While offering high accuracy, these methods require significant computational resources and training time.

### <mark style="color:purple;">Vector Databases vs. ANN Libraries</mark>

The distinction between vector databases and ANN libraries lies in their scope and functionality.&#x20;

Vector databases provide a comprehensive solution for managing unstructured data, featuring capabilities like cloud-nativity, multi-tenancy, and scalability.&#x20;

These platforms offer a robust environment for data ingestion, indexing, querying, and persistence, alongside advanced functionalities such as data sharding and hybrid search.

Conversely, ANN libraries like FAISS, ScaNN, and HNSW focus on constructing efficient vector indices to expedite the nearest neighbour search.&#x20;

These libraries are optimised for performance, offering fast search capabilities with minimal resource usage. While sufficient for smaller, less complex datasets, ANN libraries may not adequately address the scaling challenges posed by larger datasets and multi-user environments.

### <mark style="color:purple;">Conclusion</mark>

The debate between the comprehensive features of vector databases and the focused efficiency of ANN libraries underscores the diverse needs of modern data applications.&#x20;

While vector databases excel in providing a full-fledged environment for managing and querying unstructured data at scale, ANN libraries offer streamlined, efficient solutions for specific nearest neighbour search tasks.&#x20;

The choice between the two depends on the specific requirements of the application, including dataset size, complexity, and operational scalability.


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://training.continuumlabs.ai/knowledge/vector-databases/approximate-nearest-neighbor-ann.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.