Pacmann: Efficient Private Approximate Nearest Neighbor Search
Authors: Mingxun Zhou
Elaine Shi
Giulia Fanti
Venue: ICLR 2025 Poster (2025)
Keywords: Information Retrieval
Privacy
Primary area: alignment, fairness, safety, privacy, and societal considerations
TL;DR: A privacy-preserving nearest neighbor search algorithm that achieves more than 2x improvement in search quality with even lower latency compared to SOTA.

Abstract: 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.

Published as a conference paper at ICLR 2025
PACMANN: EFFICIENT PRIVATE APPROXIMATE NEAR- EST NEIGHBOR SEARCH
Mingxun Zhou, Elaine Shi & Giulia Fanti Carnegie Mellon University Piusburgh, PA 15213, USA (mingxunz, rshi, g fant ( wwwnddewwcuu.com
ABSTRACT
We propose 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 the server. Unlike prior constructions that run encrypted search on the server side, PACMANN carefully offloads limited com- putation and storage the client, no longer requiring compuuationallly-ineesss cryptographic techniques. Specifically, clients run a graph-based ANN search, where in each hop on the graph. the client privately retrieves local graph informa- tion from the server. To make this efficient, we combine two ideas: (1) we adapt a leading graph-based ANN search algorithm be compatible with private informa- tion retrieval (PIR) for subgraph retrieval; (2) we use 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.5x better search accuracy on real-world datasets than prior work and reaching 90% quality of a state-of-the ofrtte-artttttto 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 62% reduction in computation time and 22% reduction in overall latency.
INTRODUCTION
Today, most search systems require clients to send a plaintext query to the server, which per- forms search over the database and returns the most relevant document(s). This architec- ture poses serious privacy risk to users, whose search queries can leak privacy-sensitive infor- mation (aol 2006). To this end, an impor- tant problem is that of private search: algo- rithms that allow user to search a database without revealing their query to the server in plaintext. date, there have been several pro- posed private search algorithms, which provide cryptographic privacy guarantees over the user's 's
Server
Gouh
[U4 D2.... By
PIR Pisprocessing
PIR Grash Actecons
Client
Local
AANN Queries
query (Henzinger al. 2023 Asi et al. 2024 Servan-Schreiher et al.
Figure 1: The high-level overview of PACMANN. 1) The server builds a graph structure on the database vectors. 2) The client and the server run the preprocessing protocol for the PIR scheme, storing the local hint in client's storage. 3) The client makes ANN queries. 4) The client runs the graph traversal algorithm locally, but uses the PIR scheme to access the graph information remotely.
However, ex- isting algorithms suffer from poor tradeoffss between: (1) search quality and/or (2) efli- ciency. For example, consider Tiptoe (Hen- zinger et al., (202)), the state-of-te sfate-of-the-ar the-the-rt private search algorithm with cryptographically strong privacy guarantees. Tiptoe incurs linear com- putation cost for the server per query; that is,
2022
Cryptographic privacy means that the server learns cryntographically negligible information about the query.

---

Published as a conference paper at ICLR 2025
Ours (NAN)
Cluster (MRR)
Ours (LAN)
NGT (MRR=0.311
Ours (WAN)
Cluster (Recall= (Recall=0,99)
Liner Alg. (Latency-0.25))
(LAN)
0.40
Lincar Aig. [Latency 4.05)
Non-priatta ANN
0.35
Non-priuate ANN
1.0
0.30
MRR800
0.25
Recall@11
0.20
0.6
0.4
0.10
0.05
Tiptoo (simulated)
0.2
Tipro (simutanec)
0.00
0.0
0.2
0.4
0.6
0.8
1.0
1.4
08
0.0
0.5
1.0
1.5
2.0
2.5
3.0
3.5
4.0
4.5
Latency (5)
Latency (6)
(a) Results on MS MARCO dataset.
(b) Results on SIFT-100M dataset.
Figure 2: Tradeoff between search quality and latency. "Linear Alg. is an SIMD-optimized linear algorithm that lower bounds the latency of Tiptoe (Henzinger et al. (023). the state-of- of-the-art private search algorithm. As a safe lower bound, we do not include network latency for "Linear Alg.". "Cluster" is clustering- the two can be viewed as our (simulated) result for Tiptoe. We upper bound search quality with NGT, state-of-the-ar non-private ANN search algorithm (Iwasaki & Miyazaki 2018). We plot PACMANN result both the LAN (5ms RTT) and WAN (50ms RTT) settings.
algorithm that upper bounds the quality of Tiptoe. The intersection of
the server needs to at least scan through the entire database for each query. Although Tiptoe is parallelizable, the linear computation cost may be a bottleneck for large-scale applications. At the same time, Tiptoe's 's search accuracy is limited. For example, it only achieves around 40% of the non-private search accuracy in the MS-MARCC dataset.
Typical private search algorithms can be categorized by two main design choices: the search algorithm and the privacy primitive. These two are closely intertwined: the search algorithm must be chosen to be compatible with the privacy primitive, while also ensuring that information is not leaked to the server and the search quality is not overly degraded. For example, Tiptoe makes two design choices that limit its performance: (I) It uses clustering-based approximate nearest neighbor (ANN) algorithm that significantly limits the search quality. (2) Its privacy guarantees are based on preprocessed somewhat homomorphic encryption (SHE) scheme, which requires significant computation linear in the dataset size.
In this work, we present PACMANN (Privately ACcess More Approximate Nearest Neighbors), fully private nearest neighhor search algorithm that addresses the search quality-efficiency tradeoff. Instead of performing encrypted search the server's side, the client can run the search algorithm locally. To achieve this without the client storing the whole index structure, the client in PACMANN dynamically fetches necessary information from the server. Doing allows to use more sophisticated graph- based ANN search algorithms that have been popularized in applications like eetrieval-augmenne generation (RAG) MMlkovv Yashunin, 2018 Jayaram Subramanya al. 2019 Iwasaki & Miyazaki 2018). without designing complicated cryptographic protocols. PACMANN achieves strong privacy with the help of recently popularized cryptographic primitive called prepresprepoocsssing private information retrieval (PIR) (Zhou et al. 2024).
Contributions. In this work, we make two main contributions.
1. Algorithm Design. We present the design of PACMANN, which builds on a customized graph- based ANN search algorithms. In graph-based ANN search algorithms (Malkov Yashunin 2018: Jayaram Subramanya et al.] 2019 Iwasaki & Miyazaki 2018), each vertex in the graph represents a database vector and is connected to multiple other vertices based on proximity in a vector (embedding) space. Given a query vector, the algorithms usually start from given vertex and traverse the graph to find ANNs. In each step of the traversal, the algorithms examine all connected vertices to the current vertex and move to the next vertex that is closer the query, until a stopping criterion is met. To implement graph traversal algorithm privately, PACMANN requires the client locally run graph traversal over carefully-selected subgraphs. To efficiently retrieve
2

---

Published as a conference paper at ICLR 2025
the appropriate subgraph, we modify existing, practically-efficiee PIR scheme (Zhou et al. 2024) to handle batched queries. Figure I gives a high-level system overview of PACMANN.
2. Empirical results. We empirically evaluate the performance of PACMANN in terms of search qual- ity, query latency, communication, and storage costs. Our results show that PACMANN achieves significantly better search quality than the clustering-based private ANN search algorithm used by state-of-the-art Tiptoe (Henzinger et al., 2023) and Wally (Asi et al. 2024). For example, our implementation finds the most relevant result in around 63% of the queries on the MSMARCO dataset, compared to 29% for ceastering-basee algorithms-
2.1x improvement in search success rate. In the 100M SIFT dataset, our evaluation shows a 2.5x better recall @ 10 compared to Tiptoe. FigureZ]shows shows that PACMANN achieves 90% of the search quality of the leading non-private ANN algorithm (NGT (lwasaki & Miyazaki 2018 ), measured in mean reciprocal ranking (MRR) and recall. PACMANN also has lower latency than linear computation cost algorithms,, including Tip- toe (Henzinger et al., 2023) and Preco Seervan-Scheeibe et al., 2022) when the database is larger than 5M records in the LAN setting (i.c., when the search engine and the database are co-located, so network round-trip latency is 5 ms), and 50M records in the WAN setting, respectively. For example, for a database with 100M records, Tiptoe requires at least 4s of search latency, whereas PACMANN achieves 1.6s in the LAN setting (a 60% reduction) and 3.1s in the WAN setting (a 22 % reduction). Experimental details can be found in Section
1.1 RELATED WORK
Private Information Retrieval (PIR) (Chor et al. 1995, Chor & Gilboa 1997, Cachin et al.
1999
Chang 2004 Gentry & Ramzan 2005) is cryptographic primitive that allows a user to retrieve
information from a public database without revealing the query to the service provider. Most recent works that rely on Homomorphic Encryption (Melchor et al. 2016 Ahmad al.) 2021 Menon PIR schemes with linear computation cost per query. The "client- preeetttrrproossinggg PIR" model (Corrigan-Ginn
& Wu 2022] Henzinger et al. 2022) construct communication-
& Kogan 2020; (Sh et al.] 2021 Corrigan- Gibgn et al. [022 /hhou et al.] 2023 Lazzaretti & Papamanthou
2023a) introduces a preprocessing phase that allows the client to store sketched information about the database, which can be used to achieve sublinear (amortized) computation and communication cost per query. Most PIR schemes are designed for basic array-type queries. Some PIR schemes consider key-value access (Chor al., 1997 Patel et al. 2023 Celi & Davidson 2024) where the client can make private queries based on keyword matching. However, ANN search usually requires a more sophisticated search algorithm and thus requires a more complex access pattern.
Several existing works directly consider the private nearest neighbor search problem. In addition to Tiptoe (Henzinger al., 2023). Wally (Asi al. 2024) improves the efficiency of Tiptoe by batching multiple anonymous queries. Nonetheless, Tiptoe and Wally are based on simple clustering- searching strategy that partitions the vectors into roughly /n clusters, and only performs exhaustive search in one particular cluster during the search phase. This algorithm is not competitive with the state-of-tt taffthe-ar art non- coniitriate ANN search algorithms. For example, its top- search accuracy is only around 40% of the non-private ANN search algorithms on the MS-MARCO dataset. On the other hand, Preco Servan-Schreiber Sensitive Hashing (LSH) techniques, but it requires linear computation cost per query and a stronger assumption that there are two non-colluding servers storing the same databasc.
al., 2022) achieves a better search quality with Locality
In an independent and concurrent work, Zhu et al. (Zuu al. 2024) also proposes ANN search algorithm under a different setting such that the database is provided by the client and outsoureed to the server while being encrypted. In that case, the server not only stores the per-client encrypted database, but can also store per-client state to facilitate the search. Their solution is based on the HNSW graph-based ANN indexing algorithm (Malkov & Yashunin, 2018) and Path Oblivious RAM (ORAM) (Stefanov et al. 2018). Our setting is different that we assume the database is public and shared among all clients, while the server does not have any per-client storage.
2 FORMAL DEFINITIONS
K- AAAproxiiette Nearest Neighbor Search (K-ANN), Assume a dd-iiensionnl metric space with a distance function A.,,). Given database containing vectors, denoted as DB = {v1, 12,-..0 vn)
3

---

Published as a conference paper at ICLR 2025
R and query vector q E I' such that K K-approximate nearest neighbor search algorithm takes the database DB and the query vector as input, and outputs an index set I = {ii.... i such that the distances between 9 and v ..... Vi are minimized, i.c., = (....... 2x is approximation to the true K -eearestt neighbors of q in DB. Specifically, we use the recall or the mean reciprocal rank (MRR) evaluate the quality of the approximation, depending the context.
Single Server (Preprocessing) Private K-ANN. A single-server preprocessing private ANN protocol is run between a stateful client and server. The protocol consists of two phases: preprocessing phase and query phase.
1. Preprocessing: The preprocessing phase is run before the query phase and could involve the communication between the client and the server. The server will receive the vector database DB _dx as input.
2. Queries: The query phase can include multiple (adaptive) queries from the client. Each query is vector q R The client and the server can have multiple rounds of communica- tion for each query, At the end, the client will output K indices where the corresponding vectors are the K K-approximate nearest neighbors of q in DB.
The privacy a private ANN protocol requires that the server learns negligible information about the simulation-basee definition for the privacy of the protocol, being
query vector q. Formally, consistent with prior work (Henzinger et al. 2023).
Definition 2.1. An ANN protocol is private if there exists a simulator Sim such that for any prob- abilistic polynomial
adversary A acting as the server, the views of A in the following two experiments are computationally indistinguishable w.r.t the security parameter X:
Real: the client interacts with A(17, DB) who acts the server. In each query step, A may adaptively choose the next query y for the client. The client invoked with as input.
Ideal: the simulated client Sim(1>, n) interacts with A(1 DB) who acts as the server and .A still may adaptively choose the next query q for the client. However, the simulator is invoked with only the knowledge of the size of the database, and without the information of the chosen query q-
Throughout this paper, we assume the adversary is semi-honest. That is, the adversary follows the server's protocol specification but may try to learn additional information from the server's view. We leave the extension to malicious adversaries as future work.
OUR GRAPH-BASED ANN CONSTRUCTION
As starting point, we describe our ANN search algorithm construction without privacy considera- tions. Our construction relies on customized version of the graph-based ANN search algorithm.
3.1 PRELIMINARY: GENERIC GRAPH-BASED ANN SEARCH BLUEPRINT
Many popular graph-based ANN search algorithms such NSW Malkov et al.) 2012)) HNSW (Malkov & Yashunin 2018), DiskANN (Jayaram Subramanya et al. 2019). NGT (Iwasaki & Miyazaki 2018). and FINGER (Chen et al. 2023) follow the same technical blueprint: the algorithm builds a graph based on the input vectors during the preprocessing phase, and then performs a graph traversal algorithm to find the approximate nearest neighbors for given query vector. We provide graphical illustration of this process in Figure 3 and pseudocode description in Figure
Preprocessing. The preprocessing phase takes in n vectors DB {1), ......, ",) E Rdxx from a metric space and builds an indexing graph G where the vertices represent the vectors. Different algorithms may have different ways of selecting graph edges. One common approach (c.g., seen in (Jayaram Subramanya et al. 2019) ) is to connect each vertex U, several nearest neighbors, i.c. vectors that are close to 9; in the metric space, as well as multiple distant neighbors to ensure the diversity of the neighbor list (Wang al. 2021). Most recent ANN algorithms more advanced structures on top of the indexing graph (e.g. hierarchical structure in HNSW (Malkov & Yashunin 2018) or auxiliary tree-structure NGT (Iwasaki & Miyazaki 2018 improve the search efficiency.
4

---

Published as a conference paper at ICLR 2025
Query. Given query vector q. the query algo- rithm performs a graph traversal algorithm on the index graph G' and outputs a vertex u* as the approximate nearest neighbor of q. The search algorithm starts from an entry point Maun often picked as the closest vertex to the centroid of DB. We denote the set of neighbors of node (v). In each hop, the search algorithm greedily moves from the current vertex v to its neighbor in (w) that is the closest to the query vector q. The algorithm terminates when the number of hops reaches certain threshold or local minimum is met, i.c. none of the neighbors is closer than the current iterate. This can be easily extended to outputting K approximate nearest neighbors by keeping track of the vis- ited vertices and outputting the top K nearest vertices in the visited set.
Figure 3: An illustration of the graph-based ANN search algorithm on 2D space. The starting vertex is located around the upper left part of the graph, and the query vector shown as a blue star. We highlight the path that the algorithm takes to reach the approximate nearest neighbor.
3.2 OUR GRAPH BUILDING ALGORITIMM
To make graph-based ANN search private, PACMANN imposes two constraints: (1) We retain the single graph structure, as opposed to adding auxiliary structures, as done in the non-private setting. This is done to facilitate the upgrade to the the graph's 'ss out-degree distribution. This prevents information leakage from the number of neighbors accessed. These properties building algorithm to meet them. We describe the high-level idea to build a regular C-out directed indexing graph here and defer the formal description Appendix A
version. (2) We enforce regularity on
not met by existing ANN algorithms. and customize the graph-
Start from an unbalanced graph. Our first observation that we can take advantage of existing ANN libraries to find nearby neighbors for all vectors in the database and treat them the candidate neighbors in the graph. Specifically, we find 2C' approximate nearest neighbors as neighbor candidates for each vertex using existing ANN library (e.g.. NGT (Iwasaki & Miyazaki, (018)), then trim the candidate list to C' candidates with the ppars--nighbbortood--aaa (SNG) heuristic (Arya & Mount 1993). Roughly, SNG sorts the candidates by their distance to the vertex and adds candidates to the neighbor list one by one. It only adds a candidate if it is not too close to a neighbor already in the list; this is done to ensure diversity (see Figure 7 for the details). We temporarily add directed edges between each vertex and its C' neighbor candidates in both directions to ensure the graph is well-connected, i.e. so that each vertex has least inbound and outbound directed edges.
Balancing the graph. We now have a graph that could be highly unbalanced terms of the degrees. We use a sampling technique balance the graph. That is, for each directed edge (x - yy), we keep This ensures that vertex will have C' inbound edges
it with a probability of C/InboundDegree in expectation after the sampling process. Then, we ensure that each vertex has exactly C outbound edges. For those vertices with more than C outbound edges, we again use the SNG heuristic to trim the outbounds to C. For those vertices with fewer than C outbound edges, we connect them to vertices selected uniformly at random.
4 PACMANN: PRIVATE GRAPH-BASER ANN
We next describe how PACMANN protects query privacy over our customized graph-based ANN search algorithm Section 3 We start with a basic, inefficient construction, then show how PACMANN optimizes it. Due to space constraints, we present the full construction of PACMANN in Appendix B
4.1 INEFFICIENT PRIVATE GRAPH-BASED ANN SEARCH WITH CLASSICAL PIR
As a strawman scheme, one could try to protect query privacy by implementing the search algorithm with generic cryptographic primitives, such fully homomorphic encryption (Gentry) 2009). and/or
5

---

Published as a conference paper at ICLR 2025
Figure 4: Description of the graph based ANN search algorithm including the optional optimizations. The pseudocode can be read in the following two ways: 1) the non-highlighted part describes the generic graph-based ANN search algorithm; 2) the full description, including the optimizations we introduced in Section 4.3 describes our customized version of the algorithm. In the non-private setting, the algorithm is run on the server. the private setting, the client will run the query algorithm locally, and use Batched Piano PIR to perform the information retrieval dynamically and privately.
Graph-based ANN Search Algorithm
Preprocessing.
Input: a set of n vectors DB = {ui, , E Rdx=,
Output: directed graph G with vertices corresponding the vectors in DB, and entry v
point(s) Ustart U
1. G + ANN.BuildGrpph(DB):
// Description in Section
2. Let the closest vector to the centroid be the starting vertex arg mingg[n] A(vu, Ejete) vt).
Ustart
vn 3. Let the extra starting vertices be vn random vertices usun...... star sampled from [n].
Query.
Parameters: H: max hop number; beam search width mi: the number parallel paths.
Input: a query vector 9 E Rd
Output: an index u² such that tu- is recognized approximate nearest neighbor of q.
1. Let Ustart
Let U1 Um the top m vertices in mn stan start
that are closest to q
3. For t = 1.,
*
Update u as follows:
Read the neighbor list (u)) from G and all vectors v, for j Nu) from DB.
Let u' arg minjeN(w) A(Ujs q).
If ((u',)) q) & ((,,g) q), update +- w/.
Similarly, update u1,..., Um-
Let arg min ((..n.....MM A(u' 9).
Output u.
multi-party computation (Cramer et al., 2015). However, the search algorithm of graph-based ANN inherently iterative and adaptive in that during the graph traversal process, each hop's vertex is dynamically determined by both the previous hop's vertex and also the query vector, Handling such
(adaptive) iteration is a common challenge in designing cryptographic protocols Pl
as observed by
previous works (Barni et al. 2009 Delpech de Saint Guilhem et al. 2022 Choudhuri et al. 2024
Goel al. 2022 Heath et
2021
Localized Searching, Our main idea is to perform the iterative graph traversal algorithm on the client side, completely removing the privacy concern of performing iterative computation on the server. Naively, this would require the client to store the whole indexing graph, which is impractical in terms of storage cost. Instead, we let the client dynamically and privately retrieve subgraph information from the server. Specifically, during search, the client can retrieve the neighbor list N (w;)
"The standard FHE or MPC techniques are designed flow is fixed and known advance. Although the circuit model is indeed Turing-compler complete, does not naturally support mandom-access memory and control flow operations like else conditions. In the context of graph- based ANN search, do need to (adaptively) read the graph from random access memory, so the standard techniques not directly applicable.
so-called circuit model, where computation

---

Published as a conference paper at ICLR 2025
of the current vertex v and also all vectors in the neighbor list from the server for each hop. The client then computes the distances between the query vector q and all the neighbor vectors in N (v;) locally, and chooses the closest neighbor within that set. This process is repeated until the search terminates.
Protecting Retrieval Privacy with PIR. Even without directly observing the query vector, the server can infer non-tri non-trivial information from the vertex indices retrieved by the client. For example, if the server learns that the client retrieves many vertices whose underlying records represent documents about food topics, the server can infer that the client is searching for information about foods. Thus, the final challenge is how the client can retrieve the graph information (including the neighbor lists and the vectors) without revealing which vertex it is retrieving.
We use Private Information Retrieval (PIR) scheme for this purpose. Standard PIR (Chor et al., 1995) allows a client to retrieve one or multiple entries from a server-stored database of n entries without revealing the indices of the entries to the server.
To integrate a PIR scheme into our private graph- mrsph-based.om ANN search algorithm, we can run a standard PIR protocol for a database storing all the vertex information in the graph, where each entry stores the vector U; and also the neighbor list (1). Whenever the client needs to access the graph, it issues PIR query to retrieve the information privately. Notice that by merging the vector information and also the neighbor information into a single database, we can finish each hop in one round of communication.
Efficiency Issue. This construction runs into a major efficiency issue. It was formally proved by Beimel, Ishai, and Malkin (Beimel et al., 2000) that any PIR scheme requires (2()) computation cost there is no preprocessing, and if the server stores the database naively without encoding. Hence, we have non- non-private graph-based ANN algorithm that proceeds for H hops, and each hop requires the client to retrieve the information of C' neighbors, the online computation cost of the scheme will be 2 H2HC,), which is super-linear in This is worse than the prior linear-cost private ANN schemes (Henzinger et al. 2023 Servan-Schreiber et al.) 2022).
4.2 IMPROVING EFFICIENCY WITH PREPROCESSING PIR
To address this efficiency limitation, we utilize a new paradigm of PIR schemes: client-side prepro- cessing PIR (Corrigan- Gibbs & Kogan 2020). Client-side preprocessing PIR achieves sublinear (amortized) query cost by allowing a one-time preprocessing phase before the query phase in which the client will eventually store useful information about the database. Specifically, we use PIR scheme called Piano (Zhou et al. 2024) that achieves practical efficiency for the single-server setting, matching our requirements. Given a database with v entries, Piano achieves Ö(v)) computation and communication per query with (V client storage after a one-time preprocessing phase that incurs linear computation and communication costs Other alternatives of PIRs (Ghoshal et al. 2024 Ren et al. 2024) could also be used in our construction for similar efficiency guarantees.
By applying the Piano PIR scheme to our private ANN construction, after linear cost preprocessing phase, each PIR query in the graph traversal algorithm will incur Ö(v)) computation and communi- cation cost. Again, if we assume the search algorithm takes H hops and each hop requires the client to retrieve the information of C' neighbors, the overall running time of the scheme will be As long as
o( /n)), the resulting scheme will have sublinear computation cost, being more efficient than the prior private ANN schemes (Henzinger et al., 2023
et al. 2022).
Tradeoff and Practicality of Preprocessing. Despite significant online efficiency improvements, the Piano PIR client must download the whole database (i.e., the indexing graph) in a streaming fashion during the preprocessing phase. Here, streaming means that the client only stores small portion of the database to preprocess at a time, but the total amount of data the client has to download is still the whole database. Therefore, our scheme more suitable for a client with a good network connection. In our evaluation where we assume a good network connection (1 Gbps), the preprocessing phase takes around 5 minutes and GB of client storage space for a database with 100 million vectors, and the total download communication is around 60GB. An alternative approach to reduce the
We use the notation Ö(-) hide polylogarithmic factors.

---

Published as a conference paper at ICLR 2025
preprocessing cost is to have second server to preprocess the database and directly provide the client with the preprocessed results, as suggested in many existing PIR schemes (Zhou et al. 2024
Lazzaretti & Papamanthou, 2023b; Ghoshal et al. 2024: Kogan & Corrigan- Gibbs (021).
4.3 NECESSARY OPTIMIZATIONS
In practice, we observe that the total number of visited vertices in the graph-based search algorithm (that is, the product between max hop number H and the graph out-degree C)) tends to be around few hundreds or thousands. We describe the necessary optimizations here and conduct an ablation study in the evaluation section to show the effectiveness of these optimizations in Section [S] Empirically. we observe that our optimizations reduce the concrete computation cost by 76%, and the overall latency by nearly 70% (including the communication time).
Beam Search. The basic description of the graph-based ANN search algorithm Figure 4 traverses the graph in single path. In practice, can explore multiple paths in parallel. This approach is used in other graph-based ANN algorithms (Jayaram Subramanya et al.) 2019). Although doing so increases the query cost per hop, we observe that beam search significantly reduces the total hops to reach a given search quality, and is thus essential to reducing the overall latency.
Fast Starting. Intuitively, if the starting vertex is already very close to the query vector q, we can reach the approximate nearest neighbors with fewer hops. With fast starting, we let the client store around (VT)) vertices' information locally, and scan all these vertices to find those that are already close to q to start the searching algorithm. We get this benefit for free, because Piano PIR already requires the client to store ((yn). vectors locally, which are selected uniformly at random.
Batched PIR Query. We observe that the PIR queries in each hop are parallel and can be handled in single batch. We can use a batching technique called partial batch retrieval (PBR) (Servan-Schreiben et al. 2022) to further improve the efficiency. We provide the details in Appendix B.2
5
EVALUATION
We evaluate PACMANN's 's performance in terms of search quality and latency and compare it against two baselines: state-of-the-ard private ANN search algorithm, Tiptoe (Henzinger et al.) (2023), ) and a non-private ANN search algorithm, NGT (Iwasaki & Miyazaki 2018). Our evaluation results show that PACMANN achieves better search quality with lower online query latency than Tiptoe in two real datasets, SIFT and MS-MARCO. We provide more details in Appendix [ including a detailed breakdown of the preprocessing, storage, and communication cost, and discussion about quantization and the alternative implementations.
5.1 EVALUATION SETUP
Our open-source implementation") uses Python for data preprocessing and Golang for the core algorithm, including the graph ANN algorithm and the PIR scheme. Details of the implementation are provided in Appendix C The experiments are run on a single server with a 2.4GHz Intel Xeon ES-2680 CPU and 256 GB of RAM. We evaluate the latency numbers on two simulated network settings, the local area network (LAN) setting with 5ms round-trip-tims (RTT) and the wide area network (WAN) setting with 50ms RTT. Although our implementation supports multi-threading optimization, we only use a single thread for all the experiments for a fair comparison.
Quality Metrics
Recall: Recall is the standard metric used in evaluating the quality of ANN algorithms (Aumüller et al. 2020). For each query g. if the algorithm outputs K-inder set I, and the top K ground truth indices are T*, the recall@ K is defined as: Recall@ -1--0
Mean Reciprocal Rank (MRR): MRR is a standard quality metric for information retrieval sys- tems Nguyen et al. 2016). Given a query q, assume there is ground truth index i" such that DB[i*]
https:://iithbb.com.
8

---

Published as a conference paper at ICLR 2025
is the most relevant entry. If the client outputs list of indices that actually contains i" at the j-th rank where j & K, the reciprocal rank (denoted as RR@ K) score is 1/j. Otherwise, RR@ K 0. MRR is defined as the average of RR @ K over multiple queries.
Datasets
SIFT Dataset (Jégou et al. 2011 We use the first 100 million 128-dimensions) vectors from the SIFT dataset for our evaluation. We vary the database size by picking the first million to 100 million vectors. We test 1,000 top- 10 queries in the query set for each configuration, and measure the average @ecall@ (the top-10 ground truth nearest neighbors for each query are provided by the dataset).
MS-MARCO Dataset. (Nguyen et al. 2016 The dataset contains 3.2 million text documents with more than 5000 test queries such that the top relevant document provided. We follow the same procedure as in the Tiptoe paper (Henzinger et al. 2023) to process the dataset: 1) embed the documents and the queries into a (68-dimensional vector space with sentence- Meatence-BERTTT (Reimers & Gurevych 2019); 2) reduce the dimensions to 192 with PCA. We follow the same quality evaluation metric as in the Tiptoe paper that we compute the average MRR @ 100 for the first 1000 queries.
Baselines
Tiptoe (Simulated). We aim to compare our scheme against the otate-of-the-art private ANN search algorithm, Tiptoe (Henzinger et al. 2023). Due to resource constraints, were unable to run the full Tiptoe system, in which the dominating cost comes from the clustering step that requires dozens of servers rumning hundreds of core-hours as reported in the original paper. Hence, we simulated Tiptoe by using two baselines as follows.
Latency lower bound: Linear Algorithm. The Tiptoe algorithm computes n inner products per query with preprocessed homomorphic encryption. As latency lower bound, linear time algorithm that only computes the inner product between the query and each database vector in plaintext. We optimized the implementation using AVX-512 instructions. The throughput of this algorithm is approximately 11 11.9 GB/s, matching the memory bandwidth of the machine. Finally, do not include network latency for this baseline.
[ ww implement
Quality upper bound: Cluster: We replicate the clustering- ranking algorithm used in Tiptoe with full precision (32-bit We cluster the vectors into v clusters offline. For each query, we find the closest cluster centroid, and search for the nearest neighbor within the cluster.
NGT. NGT is one of the state-of-the-art non-private ANN search algorithms. We use the GoNGT library [wasaki & Miyazaki 2018). We compare our scheme against NGT in terms of search quality.
5.2 EVALUATION RESULTS
PACMANN provides a favorable tradeoff between privacy, search quality, and latency. We first measure the tradeoff between search quality and query latency. Specifically, by increasing the number of rounds and the number of parallel queries in each round, qualities at the cost of higher latency. The results are shown in Figure 2 We consider a wide range of search quality requirements, where the lower bound is by the cluster search algorithm (replicating the Tiptoe search algorithm), and the upper bound is set by the non-private ANN algorithm, NGT. We observe that our scheme provides wide range of tradeoff's between quality and latency, and can indeed achieve approximately 90% of NGT's search quality. In the SIFT- 100M dataset, the advantage of our scheme is more significant, and even with 91% recall@ 10, our scheme still has a lower latency than the linear algorithm baseline.
algorithm can achieve higher search
Scalability: PACMANN outperforms Tiptoe in latency and accuracy datasets of at least 2M-50M records. We next evaluate the scalability of our scheme by scaling the database size up 100 million vectors. We tune the parameters of our scheme to achieve 0.90 recall @ 10 for each
We compared the simulated online latency with the actual numbers reported in the original paper (Henzinger 2023), and the simulated latency is 8% less than the reported latency. See the detailed results in Appendix C algorithm reached 0.15 MRR @ 100 the MS-MARCO
ctal a
Our reimplementation of the clustering-
dataset, better than the 0.13 MRR @ 100 reported in the Tiptoe paper (Henzinger et al. 2023

---

Published as a conference paper at ICLR 2025
4.0
Ours (WAN)
4.79
Communication Time
(LAN)
1.04
Computation
Linear Algorithm
3.0
2.5
2.0
Latency
2.32
1.5
3.75
1.07
0.89
1.94
1.50 0.25
0.5
1.25
1.05
0.0 2M 5M
10M
20M
50M
100M
Database Size
No Opt
Beam
Beam-FS
Beame Batch
Figure 5: Latency results on different database sizes, sampled from the SIFT dataset. We tune the parameters of our scheme to achieve 0.90 call@ 10 for each data point; For each data point, the total latency is the sum of the actual compu- tation time and the round-trij time the com- munication, multiplied by the number of rounds. We plot both the LAN setting (5ms rtt) and the WAN setting results (50ms rtt) in this figure.
Figure 6: Ablation study on the 10M subset of SIFT (WAN setting). Given a fixed configuration, we increase the max number of rounds until the quality reaches 0.90 recall @ 10. "No Opt" means no optimizations are enabled. "Beam" means the beam search optimization. "FS" means the fast starting strategy. "Batch" means we enable the batch-mode Piano PIR. Our full implementation enables all the optimizations.
data point; that is, 9 out of 10 of the search results are indeed ground truth top- 10 nearest neighbors on average. The results are shown Figure 5 We observe that in the LAN setting where the computation time is dominant, our scheme beats the linear algorithm baseline when the database size larger than 5M. In the WAN setting where the communication time is more dominant, our scheme beats the linear baseline when the database size is larger than 50M. We observe that the number of rounds to achieve a certain recall 10 increases roughly logarithmically with the database size, and know from the theoretical analysis that PIR cost scales with vn. This suggests that the total latency of our scheme increases sublinearly with the database size.
Ablation study: Our optimizations give 70% latency reduction. Finally, we conduct ablation study on the 10M subset of the SIFT dataset to evaluate the optimizations in Section 4.3 1) Beam
Search: The number of parallel paths in the beam search algorithm is increased from to 3. 2) Fast Starting: The client starts the search by choosing the starting vertices from Ö(v preprocessed vertices. 3) Batched PIR: We enable the batch-mode PIR for each round of the search.
We compare four configurations in Figure where we increase the number of rounds until the quality reaches 0.90 recall @ 10. The beam search optimization significantly reduces the maximum number of rounds needed to achieve the same quality by 3x. Adding the fast-start strategy furtuher reduces the required rounds by 20%. When we enable the batch-mode PIR, we observe that the computation time in each round reduced by 4x, but, as we mentioned in Appendix [.. we do introduce some query failures, which need to balance with the slight increase in the number of rounds.
CONCLUSION
We present PACMANN, new private ANN search scheme that allows clients to perform nearest neighbor search queries over hundreds of millions of vectors while preserving the queries' privacy. PACMANN achieves significantly better search quality compared to the state-of-the-arr private ANN search schemes and has lower latency in large-scale datasets. PACMANN could be applied to a wide range of applications including conventional search and aetrieval-augmenn generation.
Limitations. PACMANN inherits the drawbacks of the single-server preprocessing PIR schemes and requires the client to download the whole indexing structure offline in a streaming manner. Therefore, PACMANN will not be suitable for
scenarios. PACMANN also does not naturally support dynamic updates the database, which has been challenging open problem in the field of PIR. Finally, PACMANN is designed under the assumption that the database is public, so we do not consider server-side privacy. We leave these questions interesting future directions.
10

---

Published as a conference paper at ICLR 2025
REPRODUCIBILITY STATEMENT
Our open source implementation can be found at the anonymous repository on Github: https
/ //gi thub. com/ httpm//wwwww/paaaaaaaaaa The repository contains the following components:
Instructions to install the required dependencies;
Our own implementation for PACMANN;
All bascline implementations including NGT, clustering- -based ANN and also the plaintext inner- product search (referred as "Linear algorithm" in Section 5
A script to download the SIFT dataset;
Customizable scripts run the baselines and our implementation with different parameter settings.
ACKNOWLEDGMENT
This work is in part supported by grant from ONR, grant from the DARPA SIEVE program under a subcontract from SRI, a gift from Cisco, Samsung MSI., NSF awards under grant numbers 1705007, 21 2128519 and 2044679. addition, this work is in part supported by NSF grant CCF-2338772. as well as support from the Sloan Foundation, Intel, and Bosch. We thank Justin Zhang for his contribution in the evaluations.
REFERENCES
AOL search data release reveals a great deal. http:://www.ssatooeo 08 17 aol data x. htm. 2006.
Col
Ishtiyaque Ahmad, Yuntian Yang. Divyakant Agrawal, Amr El Abbadi, and Trinabh Gupta. Addra: sectadat--private voice communication over fully untrusted infrastructure. In 15th USENIX Symposium on Operating Systems Design and Implementation, OSDI2021, July 14-16, 2021, 2021.
Sunil Arya and David M Mount. Approximate nearest neighbor queries in fixed dimensions. In SODA, volume 93, pp. 271-280. Citeseer, 1993.
Hilal Asi, Fabian Boemer, Nicholas Genise, Muhammad Haris Mughees, Tabitha Ogilvie, Rehan Rishi, Guy N Rothblum, Kunal Talwar, Karl Tarbe, Ruiyu Zhu, et al. Scalable private search with wally, arXiv preprini urXiv:2406.0677 06761, 2024.
Martin Aumüller, Erik Bernhardsson, and Alexander Faithfull. Ann-henchmarks: A benchmarking tool for approximate nearest neighbor algorithms. Information Systems, 87:101374, 2020.
Mauro Barni, Pierluigi Failla, Vladimir Kolesnikov, Riccardo Lazzeretti, Ahmad-Reza Sadeghi, and Thomas Schneider. Secure evaluation of private linear branching programs with medical applications. In Computer Security- -EORICSS 2009; 14th European Symposium Research in Computer Security, Saint-Malo, France, September 21-23, 2009, Proceedings 14, pp. 424-439. Springer, 2009.
Amos Beimel, Yuval Ishai, and Tal Malkin. Reducing the servers computation in private information retrieval: Pir with preprocessing. In CRYPTO, pp. 55-73, 2000.
Christian Cachin, Silvio Micali, and Markus Stadler. Computationally private information retrieval with polylogarithmic communication. In EUROCRYPT, pp. 402-414, 1999.
Soffa Celi and Alex Davidson. Call me by my name: Simple, practical private information retrieval for keyword queries. Cryptology ePrint Archive, 2024.
Yan-Cheng Chang. Single database private information retrieval with logarithmic communication. In ACISP, 2004.
Patrick Chen, Wei-Cheng Chang, Jyun- Yu Jiang, Hsiang Fu Yu, Inderjit Dhillon, and Cho-Jui Hsich. Finger: Fast inference for graph-based approximate nearest neighbor search. In Proceedings of the ACM Web Conference 2023, pp. 3225-3235, 2023.

---

Published as a conference paper at ICLR 2025
Benny Chor and Niv Gilboa. Computationally private information retrieval. In STOC, 1997.
Benny Chor, Oded Goldreich, Eyal Kushilevitz, and Madhu Sudan. Private information retrieval. In FOCS, 1995.
Benny Chor, Niv Gilboa, and Moni Naor. Private information retrieval by keywords. 1997.
Arka Rai Choudhuri, Sanjam Garg, Aarushi Goel, Sruthi Sekar, and Rohit Sinha. Sublonk: Sublinear prover plonk. Proceedings on Privacy Enhancing Technologies, 2024.
Henry Corrigan-Gibbs and Dmitry Kogan. Private information retrieval with sublinear online time. In EUROCRYPT, 2020.
Henry Corrigan-Gibbee Alexandra Henzinger, and Dmitry Kogan. Single-server private information retrieval with sublinear amortized time. In Eurocrypt, 2022.
Ronald Cramer, Ivan Bjerre Damgård, et al. Secure multiparty computation. Cambridge University Press, 2015.
Cyprien Delpech de Saint Guilhem, Emmanuela Orsini, Titouan Tanguy, and Michiel Verbauwhede. Efficient proof of ram programs from any public-coin eero-knowledge system. In International Conference on Security and Cryptography for Networks, pp. 615-638. Springer, 2022.
Haya Diwan, Jinrui Gou, Cameron Musco, Christopher Musco, and Torsten Suel. Navigable graphs for dige-diimesional nearest neighbor search: Constructions and limits. arXiv preprint 2.KV::2005.86800 2024.
Craig Gentry. Fully homomorphic encryption using ideal lattices. In Proceedings of the the forty-first annual ACM symposium on Theory of computing, pp. 169-178, 2009.
Craig Gentry and Zulfikar Ramzan. Single-database private information retrieval with constant communication rate. ICALP, 2005.
Ashrujit Ghoshal, Mingxun Zhou, and Elaine Shi. Efficient pre-processing pir without public-key cryptography. In Annual International Conference the Theory and Applications of Cryptographic Techniques, pp. 210-240. Springer, 2024.
Aarushi Goel, Mathias Hall-Andersen, Aditya Hegde, and Abhishek Jain. Secure multiparty compu- tation with free branching. In Annual International Conference on the Theory and Applications of Cryptographic Techniques, pp. 397-397-29 Springer, 2022.
David Hcath, Vladimir Kolesnikov, and Stanislav Peceny. Masked triples: Amortizing multiplication triples across conditionals. In IACR International Conference on Public-Ket Cryptography, pp. 319-348. Springer, 2021.
Alexandra Henzinger, Matthew M. Hong. Henry Corrigan-Gibbb, Sarah Meiklejohn, and Vinod Vaikuntanathan. One server for the price of two: Simple and fast single-server private information retrieval. Cryptology ePrint Archive, Paper 2022/949, 2022. URL httpps://ppriitt. iacr orq/2022/ 949 https: /tteps:/epprit.... iacr. /ttpg///2222/99
Alexandra Henzinger, Emma Dauterman, Henry Corrigan-Gibbs, and Nickolai Zeldovich. Private web search with Tiptoe. 29th ACM Symposium on Operating Systems Principles (SOSP), Koblenz, Germany, October 2023.
Masajiro Twasaki and Daisuke Miyazaki. Optimization of indexing based on k-nearest neighbor graph for proximity search in high-dimensional data. arXiv preprint arXiv:1810.07355, 2018.
Suhas Jayaram Subramanya, Fnu Devvrit, Harsha Vardhan Simhadri, Ravishankar Krishnawamy, and Rohan Kadekodi. Diskann: Fast accurate billion-poin nearest neighbor search on a single node. Advances in Neural Information Processing Systems, 32, 2019.
Hervé Jégou, Romain Tavenard, Matthijs Douze, and Laurent Amsaleg. Searching in billion vectors: re-rank with source coding. In 2011 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), pp. 861-864 IEFE, 2011.
12

---

Published as a conference paper at ICLR 2025
Dmitry Kogan and Henry Corrigan Corriga--Gibbs. Private blocklist lookups with checklist. In 30th USENIX Security Symposium (USENIX Security 21). pp. 875 892. USENIX Association, Au- gust 2021. ISBN 978- 179-1-933933-22-3 URL https: www. usenix. org/conference.
usen usenixsecuriin
Thijs Laarhoven. Graph-based time-space trade-offs for approximate near neighbors. In 34th International Symposium on Compulational Geometry (SoCG 2018). Schloss Dagstuhl-Leibnizz Zentrum fuer Informatik, 2018.
Kasper Green Larsen, Tal Malkin, Omri Weinstein, and Kevin Yeo. Lower bounds for oblivious near-neighbor search. In Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms,, pp. 1 11166-135 1134. SIAM, 2020.
Arthur Lazzaretti and Charalampos Papamanthou. Near-optimal private information retrieval with preprocessing. In Theory of Cryptography Conference, pp- 406-435. Springer, 2023a.
Arthur Lazzaretti and Charalampos Papamanthou. Treepir: Sublinear-time and polylog-bandwidee bandwidth private information retrieval from ddh. In SBYPTO,20233
Yu A Malkov and Dmitry A Yashunin. Efficient and robust approximate nearest neighbor search using hierarchical navigable small world graphs. IEEE transactions on pattern analysis and machine intelligence, 42(4):824-88) 836, 2018.
Yury Malkov, Alexander Ponomarenko, Andrey Logvinov, and Vladimir Krylov. Scalable distributed algorithm for approximate nearest neighbor search problem in high dimensional general metric spaces. In Similarity Search and Applications: 5th International Conference, SISAP 2012, Toronto, ON, Canada, August 9-10, 2012. Proceedings 5, pp. 132-147. Springer, 2012.
Carlos Aguilar Melchor, Joris Barrier, Laurent Fousse, and Marc-Olivier Killijian. Xpir: Private information retrieval for everyone. Proceedings on Privacy Enhancing Technologies, pp. 155-174, 2016.
Samir Jordan Menon and David J. Wu. SPIRAL: Fast, high-rate single-server PIR via FHE composi- tion. In JEEE S&P, 2022.
Hoang-Dung Nguyen, Jorge Guajardo, and Thang Hoang. Client-efficient online-offline private information retrieval. Cryptology ePrint Archive, Paper 2024/719, 2024. URL https:// eprint. iacr. org/2024/1123
Tri Nguyen, Mir Rosenberg, Xia Song, Jianfeng Gao, Saurabh Tiwary, Rangan Majumder, and Li Deng. Ms marco: A human-generated machine reading comprehension dataset. 2016.
Sarvar Patel, Joon Young Seo, and Kevin Yeo. (Don't) 't) be dense: Efficient keyword (PIR) for sparse databases. In 32nd USENIX Security Symposium (USENIX Security 23), pp. 3853-3870, 2023.
Giuseppe Persiano and Kevin Yeo. Limits of preprocessing for single-server PIR. SODA, pp. 2522-2548. SIAM, 2022.
Liudmila Prokhorenkova and Aleksandr Shekhovtsov. Graph-based nearest neighbor search: From practice to theory. In International Conference on Machine Learning, pp. 7803-7813, PMLR, 2020.
Nils Reimers and Iryna Gurevych. Sentence-BEi BBRR:: Sentence embeddings using Siamese BERT- networks. In Proceedings of the 2019 Conference on Empirical Methods in Natural Language Processing and the 9th International Joint Conference on Natural Language Processing (EMNLP- IJCNLP), 2019, doi: 1/111533/1/D199 19-10-1100...
Ling Ren, Muhammad Haris Mughees, and I Sun. Simple and practical amortized sublinear pri- vate information retrieval using dummy subsets. In Proceedings of the 2024 on ACM SIGSAC Conference Computer and Communications Security, 2024.
Sacha
Simon Langowski, and Srinivas Devadas. Private approximate nearest neighbor search with sublinear communication. In 2022 IEEE Symposium on Security and Privacy (SP), pp. 911 1--29. IEFF, 2022.
13

---

Published as a conference paper at ICLR 2025
Elaine Shi, Waqar Aqeel, Balakrishnan Chandrasekaran, and Bruce Maggs. Puncturable pseudo- random sets and private information retrieval with near-optimal online bandwidth and time. In CRYPTO. 2021.
Emil Stefanov, Marten van Dijk, Elaine Shi, T.-H. Hubert Chan, Christopher W. Fletcher, Ling Ren, Xiangyao Yu, and Srinivas Devadas. Path ORAM: an extremely simple oblivious RAM protocol.
ACM, 65(4):18:111::66, 2018.
Mengzhao Wang, Xiaoliang Xu, Qiang Yue, and Yuxiang Wang. comprehensive survey and experimental comparison of graph-based approximate nearest neighbor search. arXiv preprint arXiv:2101.12631, 2021.
Yinghao Wang, Xuanming Liu, Jiawen Zhang, Jian Liu, and Xiaohu Yang. Crust: Verifiable and efficient private information retrieval with sublinear online time. Cryptology ePrint Archive, 2023.
Mingxun Zhou, Wei-Kai Lin, Yiannis Tsclekounis, and Elaine Shi. Optimal single-server private information retrieval. In EUROCRYPT, 2023.
Mingxun Zhou, Andrew Park, Elaine Shi, and Wenting Zheng. Piano: Extremely simple, single-server pir with sublinear server computation. In IEFE S& P. 2024.
Jinhao Zhu, Liana Patel, Matei Zaharia, and Raluca Ada Popa. Compass: Encrypted semantic search with high accuracy. Cryptology ePrint Archive, Paper 2024/1255, 2024. URL https 7/eprint. facr. org/2024/12555 https://epring iacr bcr..org/024/1255
14

---

Published as a conference paper at ICLR 2025
A DETAILS OF OUR GRAPH-BASED ANN CONSTRUCTION
We now provide a detailed description of our customized graph building algorithm in Figure
Our Graph Building Algorithm: ANN.BuildGraph.
Input: set of vectors DB {U1, U2,.... Un) R and target degree C.
Output: directed regular C'outt graph G with vertices corresponding to the vectors in DB.
Subroutine: ANN.TrimNNeihhoort
C). // Given vertex and list of neighbors I, return the picked C neighbors of u in L. with the SNG heuristic.
1. Let w be the number of vertices in L and let (i1...., kw)) be the sorted indices in L according the distance to the vector Vu (ascendingly).
2. Let Kept 0, Dscd <- 0.
For j ii...... tw:
(a) If 3y' E Kept such that ((r). Uy:) < A(uy, v.), label j as discarded. // SNG heuristic
(b) If j is not discarded, insert j Kept. Otherwise, insert j to Dscd.
(c) Terminate |Kep] =
KKep]| C. insert the first C |Kept| vertices in Dscd Kept.
5. Return Kept.
Graph Building.
For each u E [n]:
(a) Let N,, the set 2C approximate neighbor indices to e, obtained by an underlying
ANN algorithm.
(b) Trim N, to C neighbors: let N, + ANN. ANN.TrimNNeighbor(.. NN,, C).
(c) For all u' E (N),), add directed edges (u + u') and edge (u' - u) to the graph G.
2. Fix InDegree(w) to be the in-degree of vertex in the current graph G.
3. For each edge (i, G: keep the edge in G with probability InDegree([))
For each u E [m]:
(a) Denote Nu(u) be the of outbounds of in G.
(b) If [N)) < C: add edges from u to random vertices in [n] until [Na(u)) = C.
(c) If [N)] > C: let Nu)u) + ANN. ANN.TriiNNiighbor/ (N).
Output the graph
Figure Description of our graph building algorithm ANN.BuildGraph.
B DETAILED CONSTRUCTION DESCRIPTION
We include the full description of our algorithm in Figure 8 The algorithm further involves the local caching optimization that the client will keep track all queried vertices and avoid repetitive queries.
B. REVIEW ON PIANO PIR
We review the main idea Pian PIR (Zhou et al. 2024) below. During the preprocessing phase, the client will sample around vni log random sets, each containing /ni random indices in [n]. For each sampled set S, the client will store the random seed to generate S, and also the sum of the entires indexed by S, denoted sum(S) entry in DB is included in at least one set. Then, for each query x, the client will first find local set S that contains
Eie DB[i]. The number of sets ensure the every
Since the client knows sum(S), if it learn learn Sum(S/ it can
15

---

Published as a conference paper at ICLR 2025
recover DB(x] by a simple subtraction. However, the client cannot query (um(S/(x)) by directly sending those yn - indices to the server, because the server will notice that all the indices received from the client are not z, which is a privacy issue. Piano fixes this issue by having the client remember roughly O(vn) random entries during the preprocessing phase, which are called the "replcaments". Then, instead of deleting x from S, the client will replace x with a replacement entry y and query the server of sum(S/{2) {x) {w}) by sending all vn indices in this "edited" set to the server. The server takes v computation to compute the sum and returns the result to the client. Since the client already knows the value of DB y) in preprocessing, it can recover DB [x]] by calculating DB[x]] sum(S) sum (S/{z} U {y]) + DB(y). It is not hard to see this sungle-query version of Piano indeed private the server only sees vn random indices that are independent of the actual query index x. We omit the details of the multiple, adaptive-quee -ueryyquerrrr version of Piano here and refer the interested readers to the original paper (Zhou et al. 2024).
We can use technique called Partial Batched Retrieval to support multiple queries in single round of communication. The idea is use a pseudorandom permutation to permute the database upfront, and then partition the permuted database into B sub-databases where each sub-database has n/ entries. On average, each sub-datahase will have Q/B B queries given batch of Q queries (if we using beam search, Q mC). By doing this, each PIR query will be issued to a sub-database of size n/B instead of the full database, saving the computation and communication cost. To ensure privacy, the client has issue fixed number of queries for each sub-database, say choosing the number T = 1.5Q/ B. If fewer than T queries are in the same sub-database, the client submits dummy queries. If more than T queries are in the same sub-database, the client only submits the first T queries and discards the rest. For example, if we have a batch size Q 32 and set partition number B 16 and T = 3, around 90% of the queries in the batch will be successfully submitted in expectation. []] Intuitively, if each vertex has 32 neighbors. our retrieval process can retrieve nearly 30 neighbors' information with single batched query. Since the graph tends to be highly-connected we observe that even with a mild query failure probability, the algorithm still finds good results with more hops.
Batched Piano PIR.
In the algorithm description, we use the following syntax of to capture the Piano PIR functionality with the made interface:
hint + PIR.Prep AA DB): given the security parameter 1 and the database DB, generate the preprocessed PIR hint hint.
msg <- PIR. HRR.BatchQuery(hint batch): given the PIR hint and a batch of query indices
batch S [n).. the client generates the PIR query message msg-
ans < PIR. Bar.BatthhnnseeDDe msg): upon receiving the batched PIR query message msg. the server generates the batched answer ans.
(3, hint') < PaR.BatchReecoerhhhii
ans, batch): given the batched answer ans and the PIR hint hint, recover the answers 3 and update the hint hint'. Here, / is a set that includes all the successful query indices and their corresponding answers. That is, 8 includes the tuples (i, (B( for all i batch that are successfully queried.
B.2 FULL ALGORITHM DESCRIPTION
Preprocessing, We use the same graph building algorithm as in Figure build graph G' from the vectors DB. We then combine the neighbor list of each vertex with its vector to build a new database v DB' = {(v,,, (())))ee()) Then, randomly sample / starting vertices u Ustart ... U from [n]]. We then run the client-side preprocessing algorithm of Piano and let the client store the hint hint. Further, we let the client download those starting vertices and their vectors and neighbor lists from the server.
"We can approximate this process with randomly throwing Q halls into B bins, each with a maximum load of T, and calculate how many balls discarded due to overflow in expectation. Given some fixed order of throwing the balls, the probability that the i-th thrown ball is thrown into fully- bin is always Pr Pr[Bin(i - 1, 1/B) 2 TJ. Here, Bin(t. p) denotes the Binomial distribution that is, the number of successful trials in repeated, independent trials where each trial has success probability of p. Then, the expected number of discarded balls (i.c., failed queries) in total is 0 Pr(Bin(i 11 1/B) T].
16

---

Published as a conference paper at ICLR 2025
Query for K K-approximate nearest neighbors of vector q R.. We generalize the search algorithm to the following exploration process. The client can maintain two sets of vertices locally: 1) visited including all vertices that the client has already visited and stored their vectors and neighbor lists, and 2) developed including all vertices that the client has already visited and retrieved all their neighhors' information. The client can maintain visited as a priority queue where the closer vertices to & are at the front. Each time the client can pick multiple vertices from visited and fetch their neighbors' information in parallel. The client will move those picked vertices from visited developed, and add their neighbors to visited. We collect all those neighbors' indices as batch and issue batched PIR query the server. After receiving the batched answer, the client will recover all the successful queries and push them to visited. The client also needs to update the local hint hint after each query. We can repeat this process until the max hop number is reached. Finally, the client can output the top K nearest vertices in visited and developed to the query vector q-
We summarize the main result the following theorem.
Theorem B.1. Assume there exists one-way functions. Consider a database with n vectors in R-. Assuming a non-private graph-based ANN algorithm that preprocesses the database into a C-degree graph, and searches for the approximate nearest neighbors with H hops in the graph. Then, by applying the Piano PIR scheme, we can build a private ANN scheme with the following efficiency, while achieving the same search quality as the non-private graph ANN:
Preprocessing: Ö(n(d + C)) client and server time and O(n(d + CT) communication:
Query: ((H-VCn-(d+CC) client and server time and OHI- VCn- communication.
Storage: Ölvū (d + C)) client storage and no additional server storage except the database.
Proof. The proof follows directly from the efficiency of the Piano PIR scheme when we consider database with n entries and each entry stores vector in IRd and neighbor list of size C. Moreover, by applying the batched optimization we described in Section 4.3 we further reduce the computation and communication cost of each PIR query by vC. The privacy proof is fairly straightforward, as the server only sees multiple Piano PIR queries from the client. We can construct a simulator for the Ideal experiment that simulates the server's view by invoking the simulator of the Piano PIR scheme for each query issued from the client. It follows from the privacy of the Piano PIR scheme that the two views (the Real and the Ideal experiments) computationally indistinguishable.
C DETAILED EVALUATION
C.I IMPLEMENTATION DETAILS
We describe our implementation of the two components below.
Graph-based ANN. The graph-base based ANN algorithm can be divided into two parts: the graph building part and the query part. The graph building part follows our description in Figure and sets the outbound number C. 32. The query part strictly follows our description in Figure
Batched PIR. We implement a bateh-mode version of the Piano PIR scheme (Zhou et al. 2024) by first implementing the single-query version of the Piano PIR scheme with 128-bit security parameter, then wrapping with batch-mode interface. The interface simply splits the whole database into B partitions, and then runs single-query Piano PIR scheme each partition parallelly. Given a batch of Q queries, we simply identify which partition each query belongs to, and then make Q/ B queries at each partition to ensure privacy. We choose B 16 and Q = 32 in our evaluation. Moreover, implement the automatic maintenance for the client state. We keep track of the consumed hints the client's space and automatically run another preprocessing phase when the hints are exhausted.
C.2 DETAILED BREAKDOWN
Finally, we provide detailed breakdown of the costs of our scheme in Table I We pick two representative parameter settings for the MS-MARCO dataset and the SIFT dataset, all achieving
17

---

Published as a conference paper at ICLR 2025
PACMANN: Private Graph ANN with Preprocessing
Preprocessing.
Server Side Preprocessing:
Input: set of vectors DB fei, 02 ,, un
Rdxn
Runs G (DD)
Randomly sample / starting vertices Usmns from [n].
Let DB' = {(0,,,,)) (1)) sejn) where N(1) is the neighbor list of i in G.
Client Side Preprocessing:
Stores hint PIR.Pree(1 DBB).
// Involving communication with the server.
Downloads the representative indices U staat from the server.
For all E {u downloads OB"[u] = (U., N (u)) from the server.
Query for a--pppoxi nearest neighbors of vector q E Rd. Parameters: max hop number H and beam search width m.
Client Side Algorithm.
Let visited (Maunhkety priority queue where the closest vertices to q are at the front.
Let developed = 0. For t 1, 2, .
Let 0I, Um be the top m indices in visited move them from visited developed.
Let batch [se[m] NV0a:mNNWaau (u:) be the union of the neighbor lists of ui...., Um-
Remove those indices in batch that are already in visited U developed.
Send msg +- PIR. Bwt.BBattcuuerileec (hint, batch) to the server.
Upon receiving ans from the server, run (3, hint') <- HIR.Recoverrans, hint). where / is set that includes all the successful query indices and their corresponding answers. For each successful query tuple (u, (v,, N (u))) 8, add visited and store the vector eu and neighbor list Nuu) locally.
Update the local PIR hint hint <- hint'. Finally, for all visited Jdeveloped, compute the distance A(va, g). Output the k: indices with the smallest distances.
Server Side Algorithm.
Upon receiving PIR batch query message msg from the client, BDDB. msg) and return ans.
Figure 8: Our private ANN scheme with preprocessing.
18

---

Published as a conference paper at ICLR 2025
MS-MARCO (3M)
SIFT (100M)
Preprocessing
Graph Buliding Time
8.5 min
343.5 min
PIR Preprocessing
9.1 s
271.6
Communication
2.7 GB
59.6 GB
Online per query
Latency Computation Time
1.1 s
3.0 s
0.10 s 1.5 MB 20
1.48 s
Online Communication
14.4 MB 32
Rounds
Maintenance per query
Time Communication
0.19 s
1.99
60.1 MB
399.4 MB
Client Storage
0.6 GB
2.9 GB
Table 1: Detailed breakdown of our results on different datasets in the WAN setting. We list the preprocessing, online query. and maintenance costs. The graph-building cost happens only once. The PIR preprocessing cost is incurred when each client joins the system. The online query cost is the cost on the critical path of the search queries. Following each online query, there is necessary one-round maintenance to update the client state. We use 16 threads for the graph building and one thread for other parts. The corresponding quality for the experiments is 0.266 MRR @ 100 for MS-MARCO and 0.90 recall @ 10 for SIFT.
90% of the quality of the state-of- thet---rttt--tttt non- non-private ANN search algorithm. The graph building time is significant for both datasets, taking 8.5 minutes for the MS-MARCO dataset and 343.5 minutes for the SIFT dataset. However, the graph building only happens once on the server side. The PIR preprocessing is per-client, but it is relatively cheap, taking 9.1 seconds for the MS-MARCO dataset and 271.6 seconds for the SIFT dataset. The most expensive part is that during the preprocessing, the client has to scan over the whole index structure in streaming fashion, incurring large communication cost. For each online query, the latency and computation time match our analysis in Section 5.2 Notably, the communication cost on the critical path is relatively low, taking 1.5MB for the MS- MARCO dataset and 14.4MB for the SIFT dataset. Notice that the client has to update its local state after each query. We see that the maintenance time per query is relatively cheap, but the communication cost is high, taking 60. IMB for the MS-MARCO dataset and 399.4MB for the SIFT dataset. Theoretically, the client stores around Ö(n) amount of local state. Empirically, we that the client stores 0.6GB of data for the MS-MARCO dataset and 2.9GB of data for the SIFT dataset, and the scaling factor matches our theoretical analysis.
Discussion on quantization and comparing against Tiptoe. We noticed that the original Tiptoe implementation uses 4-bit quantization for the vectors further trade off the search quality for the latency. In our evaluation, we use the full 32-bit precision for all the algorithms. Thus, the quality of the clustering-
algorithm should be considered an upper bound for the actual Tiptoe algorithm. For the latency, the "Linear Algorithm" baseline should be a good approximation of the actual Tiptoe algorithm. As an example, if we extrapolate the reported numbers of Tiptoe's ' algorithm based on the Table 6 and Table 7 in the original paner (Henzinger et al. 2023) to the MS-MARCO dataset, the latency will be around 0.27 seconds.
Alternative Implementations. As alternatives, one can indeed use other PIR schemes to implement our graph-based ANN algorithm. As an example, using another recent single-server PIR scheme,
*The authors of Tiptoe reported the total core-second is 145 seconds for their experiment on a dataset with 360 million 192 dimensional vectors. The full Tiptoc system contains three parts: "preprocessing" "ranking" and "URL" where the "ranking" part corresponds to our ANN search experiment. According Table in the paper, it should take about (1.9/ (6.5 + 1.9 + 0.6)) = 21% of the cost. Thus, an estimation of the time on a single-core for the 3.2M size MS-MARCO dataset will be 145 x 21% x 10 simulated "I "inne Algorithm" latency (0.25 seconds).
10 au 0.27s, which is close to
19

---

Published as a conference paper at ICLR 2025
SimplePIR (Henzinger et al., 2022) (used also in Tiptoe (Henzinger et al., 2023 comes with tradeoff. In the 10M SIFT dataset experiment, we can save the offline communication cost from roughly 6GB to around 300MB, but this would increase the online latency from 1.5s to roughly 90s according to our estimation as follows. We tested the throughput of the SimplePIR scheme on our server, which is around 10 GB/s. Then, are making in total 25 rounds of graph explorations where each round having 96 parallel queries. The batching technique allows each individual query to be made in sub-database of 16 times smaller than the whole database (around 6GB). Therefore, the 6GB
total estimated time would be 25 x 96 X 16x 10GR/ ~ 90s.
D THEORETICAL IMPLICATIONS
We focused on the practical aspects of our scheme in the main body. Although graph-based based ANN search has been empirically shown be successful in practice, the theoretical understanding of the graph-based ANN search is still very limited. Here, we provide some theoretical insights into the graph-based private ANN search given the existing theoretical results.
Definition D.1 Approo-tte Nearest Neighbor). Given n vectors DB = {u1, ....... on Rdx= and a distance function A(:-)) we say that an algorithm is (c, -approxmmmte nearest neighbor search algorithm if for any vector q E Rd such that the true minimal distance between q and any vector in DB is at most r, the algorithm outputs an index i such that A (1;, q) I c.r with at least constant probability.
For the low-dimension case where d (log n), we refer the reader to Prokhorenkova and Shekhovtsov (Prokhorenkova & Shekhovtsov 2020) for the detailed discussion. Here, we will focus on the high-dimensional regime (also known as the sparse data case) such that the dimension d = wlog n). which is the most common setting for ANN search (recall that most embedding spaces are least (00-dimensionaa).
Two notable theoretical results can be leveraged to analyze the graph-based ANN search. Laarhoven (Laarhoven, 2018 proves the following theorem:
Theorem D.2 (Laarhoven Laarhovenn] 2018). Consider a database contains independently random vectors in the unit sphere in ga-1 and the distance is measured by Euclidean distance. For >> 1, there exists a (c, (arr)grrrph-aae basphd ANN search algorithm with the Omn ((+ol)))()) space complexity and O(net(l)) query time complexity while taking only (1)) hops in the graph, where
C²
22 2c 20 +1
We call this setting the average case setting. Intuitively, we can think about n' in the above theorem roughly denoting the average degree of the graph. For example, if we aim to have a 2-approximation ANN, then P = 0.64. We see that with the approximation factor getting worse, lim p(c) 2-
On the other hand, Diwan et al. (Diwan et al., 2024) studied the problem of building a navigable graph. On high level, navigable graph provides the guarantee for dindiitribution" queries for ANN search, that is, when the query vector will be exactly some vector in the database. They showed the following theorem:
Theorem D.3 (Diwan et al. 2) For any n vectors in Rd, it is possible to build navigable graph with average degree of most 2 Moreover, the "greedy-routing" strategy always succeeds in finding the correct vector in the database with at most 2 hops.
The above two theorems provide the following theoretical insights: for the high-dimensional regime, to achieve strong guarantee on the ANN search, the average degree of the graph will be roughly n +o(1), and the query hop number will only be a constant. Therefore, if we use the same PIR technique to make the graph-based ANN search private, the underlying graph-information database is of size n +o(1), where the total number of entries is n and each entry is of size n 11/2+o(1) It is interesting to see that this is not typical setting of the PIR literature, because the entry size is much larger than a constant. If we plug in the best parameters of the prirot-ppproceessing PIR (Zhou et al. 2024 Nguyen et al. 2024 into the Laarhoven's 's algorithm, we will get the following result:
20

---

Published as a conference paper at ICLR 2025
Theorem D.4. Assume the existence of one-way functions. For 1. there exists (c, r graph- based private ANN search algorithm for Euclidean distance in the average case setting (random vectors on the unit sphere gd with the following properties:
Preprocessing cost: O(n communiication and computation cost;
Query cost:
-0(11/2+0t0()) computation cost;
((n(+o()) communication cost;
Storage cost:
Client: O(n
Server: On (oto()))
Here,
pz 2ct 2c +1
Specifically, we need to use the new result in Nguyen et al. (Nguyen et al. 2024) for optimizing the client storage. Notice that based on the existing client-specific preprocessing PIR lower bounds (Corrigan-Gibbs & Kogan 2020 Persiano & Yeo! 2022 Larsen et al. 2020). to privately access data structure size N, the product between client storage and the online time T satisfies S T Q(N). In this sense, the above theoretical result is nearly tight in terms of the client storage and online query time if we follow the graph-based ANN paradigm: the client storage is 1(n and the online query time is ((n)/2+2to(()) while the product matches the data structure size of 1+++)())
Gap between Theory and Practice. Notably, the above theoretical results on graph- based ANN algorithms based on the analysis of "high-degree" graphs, where the average degree is ((vn), and the query hop number a small constant. In practice, we see a different combination: popular graph-based ANN algorithm implementations usually pick much smaller average degree, e.g. 32 or 64, while making the query hop number larger (e.g. scaling with the logarithm of the database size). It remains an interesting open question whether there exists strong theoretical result for small-degree graphs with search process invoking large number of hops.
21


Reviews:
[{"review_id": "658ZQX2lkx", "reviewer": "Reviewer_DbeZ", "summary": "This paper presents Pacmann, a new private approximate nearest neighbor search scheme. The main claim is that this scheme is more accurate and efficient than prior private ANN search schemes.\n\nThe design of Pacmann includes a number of features, which I will try to recount here:\n* Pre-process the search graph to ensure that every vertex in the graph has a bounded out-degree of $C$. Then, when one performs a greedy walk on the graph (toward finding an approximate neighbor), the search for the next hop needs to inspect $C$ vertices at most.\n* To ensure privacy, the client will perform the search algorithm themselves. However, it is unreasonable to store the graph on the client side. If the client sends queries to the server in plain text, this may pose another privacy risk. The solution is a private information retrieval scheme, which allows the client to retrieve data from the server without revealing the index of interest. The paper appears to use an off-the-shelf PIR scheme from prior work, which, after client-side pre-processing, can achieve sublinear communication and computation costs for information retrieval.\n\nA number of experiments are provided to support the effectiveness of the approach.", "questions": "See above", "limitations": "", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "* The problem of study seems to be important, and the solution is natural and clearly written.\n* The experiment results look promising.", "weaknesses": "(Disclaimer: I might not be an expert in critiquing this paper, as I don't have much experience in this area.)\n\n* Can you comment on the scalability of your approach? I am quite concerned with the $O(\\sqrt{n})$ communication and computation cost, as I understand that $n$ is the total number of vertices in the database. I see you ran your experiments up to 100M vertices. What does this scale mean in practice? I imagine, e.g., Google search would have a way larger scale of data than this.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "DhhCe5ljcL", "reviewer": "Reviewer_bC3L", "summary": "This paper uses proposes a secure protocol for approximate nearest neighbours (ANN). The protocol is based on the client traversing a graph of the database held by a server, using a Private Information Retrieval (PIR) protocol to query each part of the graph that the client traverses. As the PIR protocol they use from previous work has O(sqrt(n)) online cost per query, and they need o(n) queries the latency is sublinear in the database size. Though the whole database must be sent during a preprocessing phase only a O(sqrt(n)) fraction of it need be stored by the client.\n\nThey provide some optimizations to the bsic idea, taking advantage of beam search to use the fact that it is cheaper per query to make several at once. they provide a small ablation study to verify this is infact helpful.\n\nThey then compare the quality of their results to the quality of some linear latency algorithm finding it improves on the baseline (on quality/latency tradeoff) when the database has size 2m to 50m depending on the network connection.", "questions": "Are you aware of any realistic applications?\n\nShouldn't the expansion of the PACMANN acronym include the word nearest to explain the double N?", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "This is an interesting idea to explore.\n\nThe scheme works well asymptotically, being the first scheme with sublinear latency, thus constituting a theoretical breakthrough.\n\nThe idea is not just naively applied with thought gone into possibilities like beam search.", "weaknesses": "The breakthrough in asymptotics here is mostly coming from previous PIR work, though exploring the applicaiton of it is still valuable.\n\nFor the largest dataset they consider, after all their optimizations the reduction in latency is between 1.3x and 2.2x depending on the network (down from about 4 seconds)  to achieve this they require 3GB of client storage and 60GB of preprocesing communication. I am not aware of and they do not point to any realistic application in which this is a good tradeoff in practice.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "9BQDbmnRjx", "reviewer": "Reviewer_4Hhv", "summary": "This paper introduces PACMANN, a private approximate nearest neighbor (ANN) search method enabling clients to conduct privacy-preserving nearest neighbor queries across hundreds of millions of vectors. PACMANN utilizes state-of-the-art private information retrieval technique and customized searching algorithm to query vector database both privately and efficiently. PACMANN surpasses current leading private ANN search techniques in search quality and offers reduced latency for large-scale datasets. This approach could inspire more follow-ups applications in the area.", "questions": "[Q1] Could you provide security analysis of the proposed method?\n\n[Q2] It would be better to compare efficiency with Tiptoe-based solution.", "limitations": "", "rating": 8, "confidence": 4, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "[S1] The motivation of this paper is clear and interesting, which is to address the privacy and efficiency challenges of remotely querying a vector database. \n\n[S2] This paper successfully identifies the and addresses the limitations of existing approaches. It introduces a novel application of private information retrieval (PIR) to perform ANN search in a vector database. Compared with the baseline Tiptoe [1], this work does not involve heavy clustering-based ANN algorithm and homomorphic encryption, acheving promising efficiency for private query.\n\n[1] Henzinger, Alexandra, et al. \"Private web search with Tiptoe.\" Proceedings of the 29th symposium on operating systems principles. 2023.\n\n[S3] This paper is well-organized with necessary background knowledge and clear illustration of high-level ideas. The language and presentation of this paper are easy understand.\n\n[S4] This paper provides fair discussion on the proposed approach and identifies the limitation of this work. For example, it is more suitable for scenarios with good network connection, which would lead further research on potential following works on more general network connection. \n\n[S5] This paper provides rigorous theoretical insights and illustrate the gap between theory and practice to enhance the understanding of graph-based ANN search.", "weaknesses": "[W1] The security analysis of the proposed approach is missing, which should be provided for a work specified in privacy-preservation. Although the core procedure PIR is invoked in black-box style, this paper should formally capture the potential information leakage during the workload. For example, the baseline of this paper Tiptoe provides a security analysis in Appendix D.\n\n[W2] It would be better if the baseline Tiptoe can be implemented more completely in experiments. For example, this paper claims the efficiency limitation of Tiptoe comes from heavy homomorphic encryption and some other factors. As far as I know, Tiptoe just requires lightweight homomorphic encryption (i.e., homomorphic addition in LWE-style ciphertexts) and it is not that slow. For fair comparison, the simulation of Tiptoe should be equipped with homomorphic encryption to confirm the outperformance of this paper.\n\nTypos: \n“We could potentially the verifiable” in Appendix C.1.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "8eWvVP6hjU", "reviewer": "Reviewer_BsSk", "summary": "The paper introduces PACMANN, a private Approximate Nearest Neighbor (ANN) search scheme enabling clients to search vector databases without exposing their query vector to the server. Unlike previous methods relying on server-side encrypted searches, PACMANN offloads limited computation and storage to the client. It achieves up to 2.5× higher search accuracy on real-world datasets compared to prior private ANN schemes, approaching 90% of the quality of a state-of-the-art non-private ANN algorithm.", "questions": "NA", "limitations": "", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "Query search mechanisms using fully homomorphic encryption (FHE) and multi-party computation (MPC) often suffer from high computational complexity. This paper addresses these challenges by introducing a localized search approach that performs iterative graph traversal on the client side. To minimize computation costs, it preprocesses Private Information Retrieval (PIR) to obtain private information from the server efficiently. Leveraging the Piano framework, the paper achieves a reduction in computation and communication costs to $O(\\sqrt{n})$. For practical implementation, it further enhances efficiency with techniques such as beam search, fast start, and batched PIR queries.", "weaknesses": "The definition of privacy in the paper is somewhat vague. Could you clarify the attack model? Specifically, what are the attacker’s capabilities, and what information are they attempting to extract from the dataset? Providing these details would help make the definition of privacy more precise and formal.\n\nIn addition to FHE, MPC, and PIR, differential privacy (DP) can also provide formal privacy guarantees. While DP generally incurs low computational costs, it may reduce the model’s utility. Including a comparison with DP-related work would make the paper more comprehensive.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Poster)