障碍空间中保持位置隐私的最近邻查询方法

Location Privacy Preserving Obstructed Nearest Neighbor Queries

基于位置服务的隐私保护是近年来空间数据库领域研究的热点.然而,现有的位置隐私保护方法只支持简单的最近邻查询,没有考虑障碍物的空间.但是障碍物的空间在实际中是普遍存在的,因此,研究障碍空间中保持位置隐私的最近邻查询问题是有意义的,也是一个难点.针对这个问题,提出了一种基于第三方可靠服务器的方法.该方法能够保证用户在享受基于位置服务所提供的实际准确答案的同时,其位置信息不被泄露.该方法首先针对用户查询的准确位置,利用第三方可靠服务器来构造一个匿名的区域并发送给位置服务器,进行匿名区域的查询处理.在查询处理过程中,提供了两种查询处理方法:1)基于线段的最大障碍距离的查询处理方法(基本方法),即利用线段的最大障碍距离来扩展匿名区域,返回扩展后的区域内的结果;2)优化查询处理方法,即在基本方法的基础上,进行迭代优化,进一步缩小扩展区域.然后把匿名区域的查询处理的结果返回给第三可信方.最后,第三方可靠服务器根据用户的准确位置,把实际准确结果返回给用户.实验结果和理论表明了这两种查询处理方法的有效性和正确性.

Location privacy has been a hot topic in recent years. However, the methods of existing location privacy preserving only support simple nearest neighbor queries, which do not consider the obstructed space. But in fact, the obstructed space is very popular in our life. Therefore, we study location privacy preserving obstructed nearest neighbor queries. Due to the effect of obstacles, this problem is also very hard. In this paper, we adopt a normal approach based on the third trusted party for privacy preserving obstructed nearest neighbor （ONN） queries. The approach can entertain the location-based service without leaking the user＇s exact location and obtain the exact answer. In our approach, firstly, the third trusted party constructs a cloaked region corresponding to the exact location and sends the cloaked region to the LBS. Then LBS processes the query region. In the process of query processing, we use two methods to return a set of candidate answers with respect to the cloaking region for the actual user location： 1）Basic approach of query processing, which uses the max obstructed distance of segment to expand the region and returning the results in the expanded region; 2）Improved approach of query processing, which further narrows the expanded region based on the basic approach. At last, the third trusted party returns the actual answer to the users corresponding to user＇s exact location . Finally, experimental results and proof theory show the effectiveness and correctness of our approach.