Vector Search
Vector Search
Vector search finds semantically similar text by comparing query embeddings with document embeddings in high-dimensional vector space. It uses metrics like Cosine Similarity or Inner Product, allowing search engines to match queries based on semantic meaning rather than exact keywords.
Complexity Profile
| Case | Complexity |
|---|---|
| Best Case | O(log N) - HNSW index |
| Average Case | O(log N) |
| Worst Case | O(N) - Flat scan |
| Space Complexity | O(N * D) |
Code Implementation
import numpy as np
def cosine_similarity(v1, v2):
dot_product = np.dot(v1, v2)
norm_v1 = np.linalg.norm(v1)
norm_v2 = np.linalg.norm(v2)
return dot_product / (norm_v1 * norm_v2)
# Flat search scanning candidate pool
def flat_vector_search(query_vec, candidate_matrix, top_k=5):
# candidate_matrix is of shape (N, D)
similarities = np.dot(candidate_matrix, query_vec) / (
np.linalg.norm(candidate_matrix, axis=1) * np.linalg.norm(query_vec)
)
return np.argsort(similarities)[-top_k:][::-1]Real-World Applications
- Retrieval-Augmented Generation (RAG) contexts locator.
- Recommendation systems (recommending similar products or tracks).
- Image similarity and reverse visual matching engines.
Hybrid Search
Hybrid Search combines sparse lexical retrieval (BM25) and dense semantic retrieval (Vector Search) to provide optimal query relevance. It executes both keyword matching and vector similarity lookups in parallel, and merges the resulting rank lists using Reciprocal Rank Fusion (RRF) to leverage the strengths of both retrieval styles.
K-Means
K-Means is a centroid-based clustering algorithm. It partitions $N$ observations into $K$ distinct clusters where each data point belongs to the cluster with the nearest mean (centroid). It repeats two steps: assigning points to the closest centroid, and recalculating centroids based on the average of all cluster members.