A Privacy Protected k-NN Query Processing Algorithm Based on Network Voronoi Diagram in Spatial Networks

Abstract

With the advances in wireless internet and mobile positioning technology, location-based services (LBSs) become popular. In LBS, users must send their exact locations to enjoy the services while they may cause several privacy threats. To solve this problem, query processing algorithms based on a cloaking method have been proposed. The algorithms use spatial cloaking methods to blur the user’s exact location into a region satisfying the required privacy threshold (k). With the cloaked region, a LBS server can execute a spatial query processing algorithm preserving their privacy. However, the existing algorithms cannot provide good query processing performance. To resolve this problem, we, in this paper, propose a k-NN query processing algorithm based on network Voronoi diagram for spatial networks. Therefore, our algorithm can reduce network expansion overhead and share the information of the expanded road network. In order to demonstrate the efficiency of our algorithms, we have conducted extensive performance evaluations. The results show that our algorithm achieves better performance on retrieval time than the existing algorithms, such as PSNN and kRNN. This is because our k-NN query processing algorithm can greatly reduce a network expansion cost for retrieving k POIs.