# Billion-scale Approximate Nearest Neighbor Search
## Recorded video
{% embed url="" %}
## Nearest Neighbor Search: NN
* N D-dim database vectors
* Given a query q, find the closest vector from the database
* Solution: linear scan, O(ND), slow
* Should try this first of all
#### Naive implementation
#### Faiss implementation
* M = number of query vectors
* SIMD (Single-Instruction Multiple Data)
* also known as vectorization
* BLAS (Basic Linear Algebra Subprograms)
1. SIMD
Then go into the d >= 4 and d > 0 and the end of the function
* SIMD codes of faiss are simple and easy to read
* Being able to read SIMD codes comes in handy sometimes; why this impl is super fast
2\. BLAS
* Norm: Euclidean norm
* k-means: one of the benchmarks for KNN
* Faster if using multiple GPU
Some useful reference
## Approximate Nearest Neighbor Search: ANN
* Faster search
* Trade-off: runtime, accuracy, and memory consumption
* A sense of scale: billion-scale data on memory
#### Application
* NN/ANN for CV
* Image retrieval
* Person re-identification
* Clustering
* kNN recognition
* Fast construction of bag-of-features
* One of the benchmarks is still SIFT
### Locality Sensitive Hashing (LSH)
Hash function that we use, generally speaking:
Good sides:
* Math-friendly
* Popular in the theory area (FOCS, STOC, ...)
Bad sides:
* Large memory cost
* Need several tables to boost the accuracy
* Need to store the original data (# = N) on memory
* Data-dependent methods such as PQ are better for real-world data
* Thus, in recent CV papers, LSH has been treated as a classic method
#### Falconn
### Tree / Space Partitioning
#### FLANN
#### Annoy
### Graph Traversal
* **Very popular** in recent years
* Around 2017, it turned out that the graph-traversal-based methods work well for million-scale data
* Pioneer
* Navigable Small World Graphs (NSW)
* Hierarchical NSW (HNSW)
* Implementation: nmslib, hnsw, faiss
#### Record Phase
* Early links can be long
* In the early phase, there are not many vectors
* Such long links encourage a large hop, making the fast convergence for search
#### Search Phase
Task: find the similar node for the query node
* Then, traverse in a greedy manner
#### Extension: Hierarchical NSW; HNSW
* Sub-sample from bottom to the top
#### NMSLIB (Non-Metric Space Library)
#### Other implementation of HNSW
* Hnswlib
* Spin-off library from nmslib
* Include only hnsw
* Simpler; may be useful if you want to extend hnsw
* Faiss
* Libraries for PQ-based methods
* This lib also include hnsw
#### Other graph-based approaches
### Compressed data
#### Basic idea
#### Product Quantization: PQ
* Split the vector into three parts
* For this first 2-D vector, find the closest in this codebook
* Then, record the ID
1. Memory Efficient
2\. Distance Estimation
* First, apply product quantization on the database
* Then, get the PQ code
#### Deep PQ
#### Hamming-based v.s Lookup-based
### Billion-scale
#### Inverted Index + PQ: Record
#### Inverted Index + PQ: Search
#### Faiss
#### Graph Traversal
## Cheat sheet of choosing index
### Benchmark
### Nearest neighbor search engine
### Problems of ANN
---
# 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://sliu583.gitbook.io/blog/specific-work/shivarams-group/embeddings/billion-scale-approximate-nearest-neighbor-search.md?ask=
```
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.