Foundations of Vector Retrieval

Preface
	Vector Retrieval
	About This Monograph
		Structure
		Introduction
		Retrieval Algorithms
		Compression
		Objective
		Intended Audience
Acknowledgements
Notation
	Terminology
	Symbols
		Reserved Symbols
		Vectors and Vector Space
		Functions and Operators
		Probabilities and Distributions
Contents
Part I Introduction
	Chapter 1 Vector Retrieval
		1.1 Vector Representations
		1.2 Vectors as Units of Retrieval
		1.3 Flavors of Vector Retrieval
			1.3.1 Nearest Neighbor Search
			1.3.2 Maximum Cosine Similarity Search
			1.3.3 Maximum Inner Product Search
				1.3.3.1 Properties of MIPS
				1.3.3.2 Empirical Demonstration of the Lack of Coincidence
		1.4 Approximate Vector Retrieval
		References
	Chapter 2 Retrieval Stability in High Dimensions
		2.1 Intuition
		2.2 Formal Results
		2.3 Empirical Demonstration of Instability
			2.3.1 Maximum Inner Product Search
		References
	Chapter 3 Intrinsic Dimensionality
		3.1 High-Dimensional Data and Low-Dimensional Manifolds
		3.2 Doubling Measure and Expansion Rate
		3.3 Doubling Dimension
			3.3.1 Properties of the Doubling Dimension
		References
Part II Retrieval Algorithms
	Chapter 4 Branch-and-Bound Algorithms
		4.1 Intuition
		4.2 k-dimensional Trees
			4.2.1 Complexity Analysis
			4.2.2 Failure in High Dimensions
		4.3 Randomized Trees
			4.3.1 Randomized Partition Trees
				4.3.1.1 A Potential Function to Quantify the Difficulty of NN Search
				4.3.1.2 Probability of Failure
				4.3.1.3 Data Drawn from a Doubling Measure
			4.3.2 Spill Trees
				4.3.2.1 Space Overhead
				4.3.2.2 Probability of Failure
		4.4 Cover Trees
			4.4.1 The Abstract Cover Tree and its Properties
			4.4.2 The Search Algorithm
			4.4.3 The Construction Algorithm
			4.4.4 The Concrete Cover Tree
		4.5 Closing Remarks
			4.5.1 Alternative Constructions and Extensions
			4.5.2 Future Directions
		References
	Chapter 5 Locality Sensitive Hashing
		5.1 Intuition
		5.2 Top-k Retrieval with LSH
			5.2.1 The Point Location in Equal Balls Problem
				5.2.1.1 Proof of Correctness
				5.2.1.2 Space and Time Complexity
			5.2.2 Back to the Approximate Retrieval Problem
		5.3 LSH Families
			5.3.1 Hamming Distance
			5.3.2 Angular Distance
				5.3.2.1 Hyperplane LSH
				5.3.2.2 Cross-polytope LSH
			5.3.3 Euclidean Distance
			5.3.4 Inner Product
		5.4 Closing Remarks
		References
	Chapter 6 Graph Algorithms
		6.1 Intuition
			6.1.1 The Research Question
		6.2 The Delaunay Graph
			6.2.1 Voronoi Diagram
			6.2.2 Delaunay Graph
			6.2.3 Top-1 Retrieval
			6.2.4 Top-k Retrieval
			6.2.5 The k-NN Graph
			6.2.6 The Case of Inner Product
				6.2.6.1 The IP-Delaunay Graph
				6.2.6.2 Is the IP-Delaunay Graph Necessary?
		6.3 The Small World Phenomenon
			6.3.1 Lattice Networks
				6.3.1.1 The Probabilistic Model
				6.3.1.2 The Claim
			6.3.2 Extension to the Delaunay Graph
				6.3.2.1 The Probabilistic Model
				6.3.2.2 The Claim
			6.3.3 Approximation
		6.4 Neighborhood Graphs
			6.4.1 From SNG to α-SNG
				6.4.1.1 Analysis
				6.4.1.2 Practical Construction of α-SNGs
		6.5 Closing Remarks
		References
	Chapter 7 Clustering
		7.1 Algorithm
		7.2 Closing Remarks
		References
	Chapter 8 Sampling Algorithms
		8.1 Intuition
		8.2 Approximating the Ranks
			8.2.1 Non-negative Data and Queries
			8.2.2 The General Case
			8.2.3 Sample Complexity
		8.3 Approximating the Scores
			8.3.1 The BoundedME Algorithm
			8.3.2 Proof of Correctness
		8.4 Closing Remarks
		References
Part III Compression
	Chapter 9 Quantization
		9.1 Vector Quantization
			9.1.1 Codebooks and Codewords
		9.2 Product Quantization
			9.2.1 Distance Computation with PQ
			9.2.2 Optimized Product Quantization
			9.2.3 Extensions
		9.3 Additive Quantization
			9.3.1 Distance Computation with AQ
			9.3.2 AQ Encoding and Codebook Learning
		9.4 Quantization for Inner Product
			9.4.1 Score-aware Quantization
				9.4.1.1 Parallel and Orthogonal Residuals
				9.4.1.2 Learning a Codebook
				9.4.1.3 Extensions
		References
	Chapter 10 Sketching
		10.1 Intuition
		10.2 Linear Sketching with the JL Transform
			10.2.1 Theoretical Analysis
		10.3 Asymmetric Sketching
			10.3.1 The Sketching Algorithm
			10.3.2 Inner Product Approximation
			10.3.3 Theoretical Analysis
				10.3.3.1 Probability of Error
				10.3.3.2 Distribution of Error
				10.3.3.3 Case Study: Gaussian Vectors
				10.3.3.4 Error of Inner Product
			10.3.4 Fixing the Sketch Size
		10.4 Sketching by Sampling
			10.4.1 The Sketching Algorithm
			10.4.2 Inner Product Approximation
			10.4.3 Theoretical Analysis
		References
Part IV Appendices
	Appendix A Collections
		References
	Appendix B Probability Review
		B.1 Probability
		B.2 Random Variables
		B.3 Conditional Probability
		B.4 Independence
		B.5 Expectation and Variance
		B.6 Central Limit Theorem
	Appendix C Concentration of Measure
		C.1 Markov’s Inequality
		C.2 Chebyshev’s Inequality
		C.3 Chernoff Bounds
		C.4 Hoeffding’s Inequality
		C.5 Bennet’s Inequality
	Appendix D Linear Algebra Review
		D.1 Inner Product
		D.2 Norms
		D.3 Distance
		D.4 Orthogonal Projection