PrivNN: A private and efficient framework for spatial nearest neighbor query processing

Zechun Cao

doi:10.1016/j.jisa.2025.104244

PrivNN: A private and efficient framework for spatial nearest neighbor query processing

2025-09-27

0

PRE

AI

DOI：10.1016/j.jisa.2025.104244

Original

Original request for help

Save

Abstract

En 中文

A common query type in location-based services (LBS) is finding the nearest neighbor (NN) of a given query object. However, the exact location of the query object is often sensitive information, posing significant privacy risks if the LBS server is untrusted or compromised. In this paper, we propose PrivNN, a novel spatial NN query processing framework that allows users to perform exact NN queries without revealing their location. Our framework introduces a novel spatial NN search algorithm, Dynamic Hierarchical Voronoi Overlay (DHVO), which efficiently finds the nearest neighbor by iteratively refining the search region using multi-granular Voronoi diagrams. We also present a client–server communication protocol that enables the server to respond to encrypted spatial NN queries by employing homomorphic encryption. We rigorously prove the correctness of our algorithm, analyze the theoretical properties of our framework, and demonstrate its strong security and robust privacy bounds. We implement and evaluate PrivNN on real-world spatial datasets, showing that it substantially reduces computational and communication overhead while remaining practical for private NN search in LBS applications.

PrivNN: A private and efficient framework for spatial nearest neighbor query processing

Abstract

Journal

Organization