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

Clc Number:

TP309

Fund Project:

National Natural Science Foundation of China (61370077, 61772131)

  • Article
  • |
  • Figures
  • |
  • Metrics
  • |
  • Reference
  • |
  • Related
  • |
  • Cited by
  • |
  • Materials
  • |
  • Comments
    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.

    Reference
    Related
    Cited by
Get Citation

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

Copy
Share
Article Metrics
  • Abstract:
  • PDF:
  • HTML:
  • Cited by:
History
  • Received:November 19,2017
  • Revised:February 06,2018
  • Adopted:
  • Online: December 05,2019
  • Published:
You are the firstVisitors
Copyright: Institute of Software, Chinese Academy of Sciences Beijing ICP No. 05046678-4
Address:4# South Fourth Street, Zhong Guan Cun, Beijing 100190,Postal Code:100190
Phone:010-62562563 Fax:010-62562533 Email:jos@iscas.ac.cn
Technical Support:Beijing Qinyun Technology Development Co., Ltd.

Beijing Public Network Security No. 11040202500063