Pacmann: Efficient Private Approximate Nearest Neighbor Search
Mingxun Zhou Elaine Shi Giulia Fanti
We propose a new private Approximate Nearest Neighbor (ANN) search scheme
named Pacmann
that allows a client to perform ANN search
in a vector database 
without revealing the query vector to the server.
Unlike prior constructions that run encrypted search on the server side,
Pacmann carefully offloads limited computation and storage to the client,
no longer requiring computationally-intensive cryptographic techniques.
Specifically, clients run a graph-based ANN search, where in each hop on the graph, the client privately retrieves local graph information from the server. 
To make this efficient, we combine two ideas: 
(1) we adapt a leading graph-based ANN search algorithm to be compatible with private information retrieval (PIR) for subgraph retrieval;
(2) we use a recent class of PIR schemes that trade offline preprocessing for online computational efficiency. 
Pacmann achieves significantly better search quality than
the state-of-the-art private ANN search schemes,
showing up to 2.5$\times$ better search accuracy on 
real-world datasets than prior work and
reaching 90\% quality of a state-of-the-art 
non-private ANN algorithm.
Moreover on large datasets with up to 100 million vectors,
Pacmann shows better scalability 
than prior private ANN schemes
with up to 62\% reduction in computation time
and 22\% reduction in overall latency.
Information Retrieval, Privacy
A privacy-preserving nearest neighbor search algorithm that achieves more than 2x improvement in search quality with even lower latency compared to SOTA.