Personalized kNN Query Execution in Vector Databases

Abstract

Modern vector databases enable search over high-dimensional embeddings, but query execution engines rely on a specific similarity metric that cannot reflect how individual users perceive similarity. We advocate a metric-level perspective on personalization, keeping the shared embedding space and the underlying index unchanged, and representing each user's specific search needs by a small matrix for Mahalanobis distance learned using relevance feedback and metric learning. Using a lower bounding relationship between Mahalanobis and Euclidean distances, we propose a query execution strategy for personalized k-nearest neighbour search that retrieves an enlarged candidate set using a standard Euclidean (or inner product) index and refines it under the user's subjective metric. Experiments on CLIP embeddings from Profiset and LAION-2B-en datasets using FAISS-based indices show that this approach can be layered on top of existing vector databases with predictable behaviour, high overlap with precise Mahalanobis kNN search results, and only a small overhead over standard Euclidean search. When the Euclidean–Mahalanobis discrepancy becomes too large for efficient refinement, we propose approximation techniques and show that a Cholesky-based whitening transformation can reorganize embeddings so that personalized search reduces to Euclidean indexing again.