# Protecting K-Nearest Neighbor Queries from Location Inference Attacks Source: [Protecting K-Nearest Neighbor Queries from Location Inference Attacks]() Collection index: [llms.txt]() Data updated: 2026-06-06T05:00:04.316Z Authors: Zhiyu Sun, Jie Fu, Xinpeng Ling, Huifa Li, Zhili Chen Published: 2026-06-04T03:25:58.000Z ## Abstract The k-nearest neighbor query (kNNQ) is a core component of modern location-based services (LBS) and has been widely adopted in popular features such as \`\`people nearby''. However, its potential privacy risks have long been overlooked. In this work, we present the first two attacks against kNNQ, namely the geometric intersection location inference attack (GI-LIA) and the zero-order optimization location inference attack (ZO-LIA), revealing the inherent location privacy risks posed by kNNQ. To mitigate these privacy risks, we further propose DPRS, a differential privacy framework for kNNQ protection. The core idea of DPRS is to incorporate a rejection sampling mechanism within a constrained perturbation interval, thereby mitigating the distance distortion caused by excessive noise injection. In addition, we design a private interval construction algorithm to construct the perturbation interval, enabling the rejection sampling mechanism to achieve a more favorable trade-off between privacy protection and query utility in kNNQ. Extensive experiments on real-world spatial datasets demonstrate that DPRS outperforms existing methods in both privacy protection and query utility. Our code is available at https://github.com/reanatom/DPRS. ## Recorded benchmark results A research result applies to its stated dataset, split, metric and evaluation configuration. Compare like-for-like settings, preserve the metric's unit and direction, and distinguish paper-reported results from independent reproduction. The best result recorded here is not a claim of exhaustive, current global coverage. - [10-NN on Brightkite (test)](): 10-NN; Brightkite (test); Recall: 48.9. - [10-NN on Gowalla (test)](): 10-NN; Gowalla (test); Recall: 48.2. - [10-NN on Gaussian synthetic (test)](): 10-NN; Gaussian synthetic (test); Recall: 67.2. - [10-NN on Beta synthetic (test)](): 10-NN; Beta synthetic (test); Recall: 62.3. - [Location inference attack on brightkite](): Location inference attack; Brightkite; Distance: 25.74. - [Location inference attack on gowalla](): Location inference attack; Gowalla; Distance: 20.59. - [Location inference attack on gaussian](): Location inference attack; GAUSSIAN; Distance: 18.34. - [Location inference attack on beta](): Location inference attack; beta; Distance: 39.96. ## Original sources and implementation [Original paper]() [PDF]()