面向路网隐私保护连续近邻查询的安全区域构建  

Safe Region Scheme for Privacy-Preserving Continuous Nearest Neighbor Query on Road Networks

作　　者：倪巍伟[1,2] 马中希[1,2] 陈萧[1,2] 

机构地区：[1]东南大学计算机科学与工程学院,南京211189 [2]东南大学计算机网络和信息集成教育部重点实验室,南京211189

出　　处：《计算机学报》2016年第3期628-642,共15页Chinese Journal of Computers

基　　金：国家自然科学基金(61370077;61003057)资助~~

摘　　要：保护位置隐私连续查询中查询发起时间的设置关系着查询效率和查询结果使用的正确性,路网的复杂结构使得保护位置隐私路网连续近邻查询中查询发起时间对查询效果的影响更为显著.针对路网环境保护位置隐私连续近邻查询中查询发起时间设置问题,从为查询者构建关于查询结果的有效运动范围角度,引入k近邻安全区域概念,解析安全区域成因,提出路网k近邻分割点定义并给出路网k近邻分割点的判断与定位方法.在此基础上,充分利用可信第三方服务器获取的查询中间结果,提出独立于LBS服务器的基于候选解集的路网k近邻安全区域构建方案和基于安全区域的保护位置隐私路网连续k近邻查询策略.所提基于候选解集的k近邻安全区域机制在兼顾查询者位置隐私的同时对传统基于空间混淆的路网连续k近邻查询有良好的兼容性.理论分析和实验结果表明,所设计的基于候选解集的安全区域机制能有效地解决路网环境保护位置隐私连续查询中查询发起时间设置的问题,所提方案是有效可行的.The time to initiating queries bears close relation to query efficiency and right use of the query result in location privacy aware continuous queries, especially in road network environment. Concerning the problem of querying time in location privacy preserving continuous k nearest neighbor queries on road networks, safe region of k nearest neighbors is leveraged to surmount the problem from view of elaborating the safe moving scale for the query, within which query user＇s vested k nearest neighbor set keeps valid. Further, the splitting point of the k nearest neighbor structure, as well as its locating method, are proposed to identify the boundary of the safe region on road networks. To avoid pushing additional workload to LBS server-side, a safe region generation scheme is demonstrated which is absolutely deployed at the trusted third party. The scheme does not violate the ordinary dealing procedure of location privacy preserving querying on road networks, as well as location privacy of the query user, and hence has good compatibility to existing space cloaking based location privacy preserving k nearest neighbor query methods on road networks. Subsequently, a query strategy is illustrated equipped with our safe region scheme, which can solve querying time problem effectively in location privacy preserving continuous k nearest neighbor queries. Theoretical analysis and empirical study demonstrate our solution＇ s performance.

关 键 词：路网 位置隐私 连续K近邻查询 k近邻安全区域 候选解集 隐私保护 

分 类 号：TP311[自动化与计算机技术—计算机软件与理论]