隐私保护下的组最近邻查询算法研究

摘要

针对现有的组最近邻 GNN（Group Nearest Neighbor）查询的隐私保护算法没有考虑地图匹配攻击的问题，在无可信第三方的模型下，提出基于三阶段的保护用户位置隐私的组最近邻算法 SFR（Send-Filter-Refine）。发送阶段中用户向服务商发送可防御地图匹配攻击的矩形区域来代替精确位置；过滤阶段中服务商利用各区域计算所有可能成为结果的数据点并回传给用户；求精阶段为了防止发起查询的用户间的隐私泄露，通过用户间的无序交互来得到最终的查询结果，并提出多个剪枝策略来加快查询速度。基于真实路网的实验结果表明，SFR 与传统方法相比，有更高的查询效率和更低的受攻击率。%Existing private-preserving algorithm for group nearest neighbour (GNN)query ignores map matching attacks.To avoid this problem,we proposed a GNN algorithm for preserving the privacy of users location,which is based on three phases of send-filter-refine (SFR),in the model of no-trusted third party.In sending phase,users send the rectangular regions capable of defending map matching attacks instead of accurate locations to location service provider (LSP).In filtering phase,LSP utilises these regions to calculate all the points possibly being the GNN results and returns them to users.And in refining phase,in order to prevent revealing the privacies among those users initiating queries,the final query result is obtained by unordered interactions between users,and we proposed a couple of pruning strategies to speed up the query.Result of the experiment based on real road network showed that SFR had higher query efficiency and lower rate of being attacked than the traditional algorithm.