Foundations of Vector Retrieval

Abstract

Vectors are universal mathematical objects that can represent text, images, speech, or a mix of these data modalities. That happens regardless of whether data is represented by hand-crafted features or learnt embeddings. Collect a large enough quantity of such vectors and the question of retrieval becomes urgently relevant: Finding vectors that are more similar to a query vector. This monograph is concerned with the question above and covers fundamental concepts along with advanced data structures and algorithms for vector retrieval. In doing so, it recaps this fascinating topic and lowers barriers of entry into this rich area of research.

References in corpus (23)

• Google's Neural Machine Translation System: Bridging the Gap between Human and Machine Translation
• Asymmetric LSH (ALSH) for Sublinear Time Maximum Inner Product Search (MIPS)
• Practical and Optimal LSH for Angular Distance
• ColBERT: Efficient and Effective Passage Search via Contextualized Late Interaction over BERT
• An Efficiency Study for SPLADE Models
• EFANNA : An Extremely Fast Approximate Nearest Neighbor Search Algorithm Based on kNN Graph
• On Symmetric and Asymmetric LSHs for Inner Product Search
• Quantization based Fast Inner Product Search
• Online Product Quantization
• Improved Asymmetric Locality Sensitive Hashing (ALSH) for Maximum Inner Product Search (MIPS)
• Clustering is Efficient for Approximate Maximum Inner Product Search
• Quicker ADC : Unlocking the hidden potential of Product Quantization with SIMD
• Efficient and Effective Tree-based and Neural Learning to Rank
• An Approximate Algorithm for Maximum Inner Product Search over Streaming Sparse Vectors
• From Distillation to Hard Negative Sampling: Making Sparse Neural IR Models More Effective
• FreshDiskANN: A Fast and Accurate Graph-Based ANN Index for Streaming Similarity Search
• A Comprehensive Survey and Experimental Comparison of Graph-Based Approximate Nearest Neighbor Search
• Bridging Dense and Sparse Maximum Inner Product Search
• A new near-linear time algorithm for k-nearest neighbor search using a compressed cover tree
• Worst-case Performance of Popular Approximate Nearest Neighbor Search Implementations: Guarantees and Limitations
• Improved Residual Vector Quantization for High-dimensional Approximate Nearest Neighbor Search
• Automating Nearest Neighbor Search Configuration with Constrained Optimization
• A Bandit Approach to Maximum Inner Product Search

Cited by in corpus (4)

• Pairing Clustered Inverted Indexes with kNN Graphs for Fast Approximate Retrieval over Learned Sparse Representations
• Bridging Dense and Sparse Maximum Inner Product Search
• The Impacts of Data, Ordering, and Intrinsic Dimensionality on Recall in Hierarchical Navigable Small Worlds
• A Learning-to-Rank Formulation of Clustering-Based Approximate Nearest Neighbor Search