基于Voronoi-R*的隐私保护路网k近邻查询方法

针对已有的保护位置隐私路网k近邻查询依赖可信匿名服务器造成的安全隐患，以及服务器端全局路网索引利用效率低的缺陷，提出基于路网局部索引机制的保护位置隐私路网近邻查询方法.查询客户端通过与LBS服务器的一轮通信获取局部路网信息，生成查询位置所在路段满足l-路段多样性的匿名查询序列，并将匿名查询序列提交LBS服务器，从而避免保护位置隐私查询对可信第三方服务器的依赖.在LBS服务器端，提出基于路网基本单元划分的分段式近邻查询处理策略，对频繁查询请求路网基本单元，构建基于路网泰森多边形和R^*树的局部Vor-R^*索引结构，实现基于索引的快速查找.对非频繁请求路网基本单元，采用常规路网扩张查询处理.有效降低索引存储规模和基于全局索引进行无差异近邻查询的访问代价，在保证查询结果正确的同时，提高了LBS服务器端k近邻查询处理效率.理论分析和实验结果表明，所提方法在兼顾查询准确性的同时，有效地提高了查询处理效率.

Voronoi-R*-based Privacy-preserving k Nearest Neighbor Query over Road Networks

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.