> For the complete documentation index, see [llms.txt](https://sliu583.gitbook.io/blog/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://sliu583.gitbook.io/blog/specific-work/shivarams-group/embeddings/billion-scale-approximate-nearest-neighbor-search.md). # 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 ![Problem setting ](/files/-MbdAJNyQ0dU7-BA6PHF) #### Naive implementation ![](/files/-MbdAQPikFrscIllX4NO) #### Faiss implementation ![](/files/-MbdAfB4mgkEZBGwKN_-) * M = number of query vectors * SIMD (Single-Instruction Multiple Data) * also known as vectorization * BLAS (Basic Linear Algebra Subprograms) 1. SIMD ![](/files/-MbdC67xUOxnGUvnQclJ) ![](/files/-MbdCD2s2P46vcY3yGE5) Then go into the d >= 4 and d > 0 and the end of the function ![](/files/-MbdD9_BC25YUtrmeUnz) * 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 ![](/files/-MbdDLTXnJ1cOmDOE3NZ) * Norm: Euclidean norm ![](/files/-MbdDpvlanh3bw8e3XwC) * k-means: one of the benchmarks for KNN * Faster if using multiple GPU Some useful reference ![](/files/-MbdE5WzwAoGCH-4tMvX) ## Approximate Nearest Neighbor Search: ANN * Faster search * Trade-off: runtime, accuracy, and memory consumption * A sense of scale: billion-scale data on memory ![](/files/-Mbd9GTMdfPEJUg28SnR) #### 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 ![](/files/-MbdEIxgWl3meUxIK5gK) ### Locality Sensitive Hashing (LSH) ![](/files/-MbdElzXjrbbtOpKn9ZP) Hash function that we use, generally speaking: ![](/files/-MbdFCaJbtuEsKegglYH) 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 ![](/files/-MbdFgYcKzIbRNOviBwK) #### Falconn ![](/files/-MbdG-gIUAQwY5RK6PBV) ### Tree / Space Partitioning #### FLANN ![](/files/-MbdGOwkOL7a7pOESiXE) #### Annoy ![](/files/-MbdGct7bGTsCAf3hJaJ) ![](/files/-MbdGuMXT1GROV7BxqsX) ![](/files/-MbdH0YdsrNZ-cr9IS0v) ### 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 ![](/files/-MbdHpgqiw0SsdsaqlTh) * 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 ![](/files/-MbdIL_LsiEtY-u1lzWq) * Then, traverse in a greedy manner #### Extension: Hierarchical NSW; HNSW ![](/files/-MbdI_4z_0fIk2GWO9b0) * Sub-sample from bottom to the top #### NMSLIB (Non-Metric Space Library) ![](/files/-MbdIoxbCRyUdk_rN1n3) #### 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 ![](/files/-MbdJAU1VMPRTNLPVQtr) ### Compressed data #### Basic idea ![](/files/-MbdJg50k1f7AVvHJ-fu) ![](/files/-MbdJzChdScWam2BqVN8) ![](/files/-MbdK9UVdhfbpbBIlnzT) #### Product Quantization: PQ ![](/files/-MbdKM1uQRqeXKduETon) * Split the vector into three parts * For this first 2-D vector, find the closest in this codebook * Then, record the ID ![](/files/-MbdKqfeHghxeZ4nR-6q) ![](/files/-MbdKuKuyTEzrFVrxWOF) 1. Memory Efficient ![](/files/-MbdLOUsxbSMnRX7UJRd) 2\. Distance Estimation * First, apply product quantization on the database * Then, get the PQ code ![](/files/-MbdLiK7VyCFBeBnpnHA) ![](/files/-MbdLkaYH6rrkUp9KF5O) ![](/files/-MbdLxthUlG-TaxfourW) ![](/files/-MbdMEoJU2Pq84G71JhQ) #### Deep PQ ![](/files/-MbdMTPocZPMCVeScAJH) ![](/files/-MbdMWhjBZlQct1HuOUU) #### Hamming-based v.s Lookup-based ![](/files/-MbdM_oM1h3l-RjQBsq7) ### Billion-scale ![](/files/-MbdMlmqnkqWyCY_7Oh-) #### Inverted Index + PQ: Record ![](/files/-MbdN-2LjOkVyJUuRycj) ![](/files/-MbdNQkUnOM7M0I0nJ2d) ![](/files/-MbdNZM50OqPuVmJlmMX) #### Inverted Index + PQ: Search ![](/files/-MbdNk_mHCxZ1UYywY1N) #### Faiss ![](/files/-MbdO4ZvaeIW-GEVg3zq) ![](/files/-MbdOAF5mR9JyST1Rn_O) #### Graph Traversal ![](/files/-MbdOXJgA5VMrRJ50WSZ) ![](/files/-MbdOqVExoFl6YknO1NK) ## Cheat sheet of choosing index ![](/files/-Mbd9qSKQ8ZTC9NK_avC) ### Benchmark ![](/files/-MbdQ-OJ8xPEhiVfmnpn) ![](/files/-MbdQ6zSyUqj-_XZqdaZ) ![](/files/-MbdQCfhloHY9UwveMmg) ### Nearest neighbor search engine ![](/files/-MbdQTD1sRoCxFHDZoHK) ### Problems of ANN ![](/files/-MbdQZJRY_5bGBgpvnLU)