National Natural Science Foundation of China (61370077, 61772131)
With the thriving of location based service, privacy-preserving nearest neighbor querying over road networks receives widespread attention. Most of existing methods highly depend on the trusted anonymous server and auxiliary server-side global index structure of the whole road networks. The trusted anonymous server is inclined to be the bottleneck of the querying system and the global index structure is commonly with low utilization. Concerning these problems, a new privacy-preserving k nearest neighbor querying schema is proposed leveraging local index schema at server side. Two rounds of handshakes are initiated between query user and the server side to avoid the dependence on any trusted anonymous server. At the first round, the query user generates anonymous query sequence satisfying l-diversity of road nodes at client side via initiating road sections request that locate within a special cloaking area. Thereafter, the anonymous query sequence and the number of target object k are submitted to the server to achieve the candidate query results. At the server, the whole road network is partitioned into a series of basic units. A hitting frequency guided segmented query processing strategy is proposed, which differentiates basic units with high hitting frequency from those ones with low hitting frequency. For those units with high hitting frequency, a local Voronoi-R* index is designed and constructed. The k nearest neighbors of each location in anonymous query sequence can be easily achieved leveraging the new index, which promises higher querying processing efficiency. In contrast, the traditional server-side query strategy is applied to those units with low hitting frequency, which grasps nearest neighbors leveraging increment network expansion querying. This strategy can avoid redundant query process and index storage cost originated from global server side index structure, in parallel with no species difference query pattern based on the global index. Theoretical and empirical analysis demonstrates the effectiveness and efficiency of the proposed solution.