Pacmann: Efficient Private Approximate Nearest Neighbor Search

We propose a new private Approximate Nearest Neighbor (ANN) search schemenamed Pacmannthat allows a client to perform ANN searchin 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 thanthe state-of-the-art private ANN search schemes,showing up to 2.5$\times$ better search accuracy on real-world datasets than prior work andreaching 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 schemeswith up to 62\% reduction in computation timeand 22\% reduction in overall latency.