Private Approximate Nearest Neighbor Search for Vector Database Querying

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(N2M1/N-1) for N databases. For large M, this communication cost is lower than competing cryptographic ANN search protocols.