一种基于兴趣点分布的匿名框kNN查询方法

摘要

基于位置的服务(Locarion-based Service, LBS)推动了移动智能终端各类型应用的快速发展，为用户的生活提供了方便。针对利用匿名框实现的兴趣点k近邻(kNN)查询带来的通信开销大、时延长等问题,提出了基于单一兴趣点Voronoi划分和四叉树层次化组织的kNN查询方法.首先,LBS服务器将同类兴趣点进行Voronoi图划分,利用四叉树进行层次化组织.然后,用户根据四叉树信息找到最近的目标兴趣点,并以之作为出发点查找其它k-1个兴趣点.最后,用户构造包含k个目标兴趣点在内的匿名框,将附有的虚假查询一起发送给LBS服务器,并最终根据返回的查询候选集获取k个目标兴趣点的详细描述信息.由于查询目的性较强,相对传统匿名框查询,在不牺牲位置隐私保护质量的同时,降低了查询通信开销,注入虚假查询请求保护了用户的真实查询内容.性能分析及对比实验表明本方法具有良好的工作效率.