支持偏好调控的路网隐私保护k近邻查询方法  

Location Privacy Preserving k Nearest Neighbor Query Method on Road Network in Presence of User's Preference

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

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

出　　处：《计算机学报》2015年第4期884-896,共13页Chinese Journal of Computers

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

摘　　要：随着人们对个体隐私的日益关注,位置服务中的隐私保护问题成为数据库领域新兴的研究热点.针对面向路网的隐私保护k近邻查询中,保护位置隐私引发的难以兼顾查询质量问题及查询者对查询效率与准确性间偏好调控需求问题,引入PoI(Points of Interest)概率分布概念,通过分析服务器端PoI邻接关系,生成PoI概率分布.将服务器端查找k近邻PoI过程分解为路网扩张查询阶段和迭代替换阶段,为迭代替换阶段构建基于PoI概率分布的可替换PoI概率预测机制.基于所构建概率预测机制,提出支持用户偏好调控的保护位置隐私k近邻查询方法AdPriQuery(Adjustable Privacy-preserving knearest neighbor Query),查询者通过调节筛选概率阈值,在兼顾位置隐私安全的同时,实现对查询效率与准确性的偏好调控.所提调控机制对已有的基于空间混淆的路网环境保护位置隐私近邻查询方法具有良好的兼容性.理论分析和实验结果表明,所提方法在兼顾保护位置隐私的同时,能有效提高服务器端查询效率,同时支持查询结果准确性与查询效率的偏好调控要求.With the increasing concerning to individual privacy, privacy protection in location based services becomes a hot topic in the domain of database research. In recent years, privacypreserving location based k nearest neighbor querying on road networks receives thriving attentions for its complexity and practical application values. Most of current work in common falls short in ignoring user＇s preferred adjusting requirement in relation to query accuracy and query efficiency, as well as the heavy workload at the server side. Concerning these problems, definition of adjacent PoI （Points of Interest） and probability distribution of PoI are introduced and the method of constructing probability distribution of PoI is devised by analyzing neighboring relation of those PoIs stored at the server side. Further, the server-side querying process is partitioned into two stages, namely incremental network expansion query stage and iteratively replacing stage. In iteratively replacing stage, the probability prediction scheme is elaborated to estimate the probability that there exists some replaceable PoI for current searched k th nearest neighbor PoI within the given number oi search steps. Based on the aforementioned definitions and scheme, an adjustable privacy-preserving k nearest neighbor query method AdPriQuery is proposed, which can provide query users the function to seek trade-off between query efficiency and query accuracy by adjusting the parameter of probability threshold. The scheme can be deployed to those existing cloaking based privacy-preserving nearest neighbor query solutions on road networks. Theoretical analysis and empirical study demonstrate our solution＇s performance.

关 键 词：位置隐私保护 K近邻查询 路网 PoI概率分布 偏好调控 

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