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

作者简介:

倪巍伟(1979-),男,江苏淮安人,博士,教授,博士生导师,CCF专业会员,主要研究领域为数据隐私安全保护,复杂数据管理;李灵奇(1994-),女,硕士生,主要研究领域为隐私保护位置服务;刘家强(1992-),男,硕士生,主要研究领域为隐私保护位置服务.

通讯作者:

倪巍伟,E-mail:wni@seu.edu.cn

中图分类号:

TP309

基金项目:

国家自然科学基金(61370077,61772131)


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

Fund Project:

National Natural Science Foundation of China (61370077, 61772131)

  • 摘要
  • |
  • 图/表
  • |
  • 访问统计
  • |
  • 参考文献
  • |
  • 相似文献
  • |
  • 引证文献
  • |
  • 资源附件
  • |
  • 文章评论
    摘要:

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

    Abstract:

    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.

    参考文献
    相似文献
    引证文献
引用本文

倪巍伟,李灵奇,刘家强.基于Voronoi-R*的隐私保护路网k近邻查询方法.软件学报,2019,30(12):3782-3797

复制
分享
文章指标
  • 点击次数:
  • 下载次数:
  • HTML阅读次数:
  • 引用次数:
历史
  • 收稿日期:2017-11-19
  • 最后修改日期:2018-02-06
  • 录用日期:
  • 在线发布日期: 2019-12-05
  • 出版日期:
您是第位访问者
版权所有:中国科学院软件研究所 京ICP备05046678号-3
地址:北京市海淀区中关村南四街4号,邮政编码:100190
电话:010-62562563 传真:010-62562533 Email:jos@iscas.ac.cn
技术支持:北京勤云科技发展有限公司

京公网安备 11040202500063号