Private Approximate Nearest Neighbor Search for Vector Database Querying
Sajani Vithana, Martina Cardone, Flavio P. Calman · 2024
We consider the problem of private approximate nearest neighbor (ANN) search. A user seeks the closest vector to a target query$q$among$M$vectors stored in a system of$N$non-colluding databases. The user aims to retrieve the ANN without revealing information about$q$to any of the$N$databases. We provide an information-theoretic formulation of the problem and propose a scheme based on a tree-structured ANN search mechanism. The proposed scheme uses a coding-theoretic approach to traverse the branch in the tree structure that leads to the approximately closest vector to$q$while guaran-teeing perfect information-theoretic privacy. We prove that our approach achieves a communication cost of$O(N^{2}M^{\frac{1}{N-1})}$for$N$databases. For large$M$, this communication cost is lower than competing cryptographic ANN search protocols.