Amora: Communication-Efficient Private Approximate Nearest Neighbors Search
Amora cuts private nearest-neighbor search communication 93-99% versus Pacmann while raising accuracy.
Amora is a single-server private approximate nearest-neighbor search system that applies SimplePIR to a partitioned graph index so one PIR query covers many vertices. A dual layout uses VecPIR for partition-wide distances and NbrPIR for neighbor lists, shifting PIR cost from per-vertex to per-partition. Evaluated on five datasets from 96 to 1024 dimensions and up to 10 million vectors, Amora cuts online communication 93-99% versus Pacmann while improving search accuracy.
- Amora hides ANNS query vectors using partitioned-graph PIR.
- VecPIR and NbrPIR amortize one PIR query across many vertices.
- Batch PIR, centroid pruning, and TopCand reduce scans and rounds.
- Online communication falls 93-99% versus Pacmann with higher accuracy.
Full article260 words · extracted from arxiv.org · click to collapse
Approximate nearest neighbors search (ANNS) over cloud-hosted vector databases raises a critical privacy concern: the query vector, which often encodes sensitive user intent, is exposed to the server. Private ANNS (PANNS) allows a client to retrieve nearest neighbors without revealing its query. The state-of-the-art single-server scheme, Pacmann (ICLR'25), achieves high accuracy via graph-based search with private information retrieval (PIR), but incurs substantial communication overhead because each PIR query retrieves only a single vertex. We present Amora, a communication-efficient PANNS system that applies SimplePIR to a partitioned graph index so that one PIR query is amortized over many vertices. To retrieve as much of the distance and neighbor information the search needs under a limited communication budget, Amora adopts a dual-PIR split layout with two heterogeneous PIR matrices that stay balanced in dimension: VecPIR retrieves inner products for an entire partition of vertices as their distance at once, while NbrPIR retrieves necessary neighbor lists at subgroup granularity for graph traversal. This layout shifts the cost model of PIR query from per-vertex to per-partition, which significantly reduces the communication overhead. To further improve efficiency by reducing the number of scans and query rounds in the PIR database, Amora introduces batch PIR to pack multiple queries into one matrix multiplication, centroid-based pruning to filter unpromising partitions, and TopCand exploration that seeds jump-style graph navigation with the closest vertices from each retrieved partition. We evaluate Amora on five datasets spanning 96 to 1024 dimensions and up to 10 million vectors. Compared to Pacmann, Amora reduces online communication by 93--99% while achieving higher search accuracy.
Text extracted automatically; images, tables and formatting may be missing. Original: https://arxiv.org/abs/2610.21174