vector db
Consider a query q, and suppose the algorithm outputs a set X of k candidate near neighbors, and suppose G is the ground-truth set of the k closest neighbors to q from among the points of the base dataset. Then, we define the k-recall@k of this set X to be |X∩G| / k.
The goal of an ANN algorithm then is to maximize recall while retrieving the results as quickly as possible, which results in the recall-vs-latency tradeoff.
A curated list of awesome works related to high dimensional structure/vector search & database
Vector databases
- Milvus: A Purpose-Built Vector Data Management System, SIGMOD '21
- Manu: A Cloud Native Vector Database Management System, 2022
- VBASE: Unifying Online Vector Similarity Search and Relational Queries via Relaxed Monotonicity, OSDI 2023 codebase
Graph Index
- Approximate nearest neighbor algorithm based on navigable small world graphs, 2014
- Efficient and robust approximate nearest neighbor search using Hierarchical Navigable Small World graphs, 2016
- Revisiting the Inverted Indices for Billion-Scale Approximate Nearest Neighbors, 2018
- FINGER: Fast Inference for Graph-based Approximate Nearest Neighbor Search, 2022 HNSW-FINGER Explained!
- DiskANN: Fast Accurate Billion-point Nearest Neighbor Search on a Single Node, 2019
Quantization
- Product Quantization for Nearest Neighbor Search, 2010
- A Survey of Quantization Methods for Efficient Neural Network Inference, 2021
Misc
- THE FAISS LIBRARY, 2024
- Faiss: The Missing Manual
- Cosine similarity = dot product for normalized vectors
- USearch: Smaller and faster single-file vector search engine
- Annoy(Approximate Nearest Neighbors Oh Yeah)
- RAPIDS RAFT library
- Accelerating Vector Search: Using GPU-Powered Indexes with RAPIDS RAFT
- Accelerating Vector Search: Fine-Tuning GPU Index Algorithms
- Accelerated Vector Search: Approximating with RAPIDS RAFT IVF-Flat
- Semantic Search: Measuring Meaning From Jaccard to Bert
- SPLADE for Sparse Vector Search Explain
- Sparse embedding or BM25?
- Unlock Advanced Recommendation Engines with Milvus' New Range Search
- Billion-scale vector search with Vespa - part one
- Billion-scale vector search with Vespa - part two
- Billion-scale vector search using hybrid HNSW-IF
- Weaviate: An Architectural Deep Dive (Etienne Dilocker) with HNSW and PQ detailed
- Milvus: A Purpose-Built Vector Data Management System! (Li Liu) Milvus 2.0 architecture explained