移动k-支配最近邻查询验证研究

Research on Authentication of Moving k-Dominant NN Queries

现有的基于位置服务(Location-Based Services,LBS)查询结果都是直接基于LBS服务商返回的结果.但LBS服务提供商是易被勾结的和不受信任的,所以给用户提供一种可信查询服务是非常必要的.因此,研究可信环境下的空间数据库查询具有重要意义.该文关注在移动过程中的k-支配最近邻查询和验证,该查询本质上是k-最近邻(k-Nearest Neighbor,kNN)和轮廓(Skyline)查询的结合.其目标是对于一个给定的查询q,返回在空间属性和非空间属性上不受支配的且距离最接近查询点q的k个点.为了有效解决移动k-支配最近邻查询验证问题,该文提出了一种新的安全区域(Safe Region,SR)和验证数据结构(Authenticated Data Structure,ADS)Merkle Verifiable Voronoi R-tree(MV2 R-tree)用于产生查询结果和验证对象(Verification Object,VO).在此基础上,该文基于比较分析提出了Rectangle-based验证策略用于验证查询结果和安全区域.最后,通过大量的实验验证了提出的方法的有效性.

With the rapid development of smart mobile terminal and mobile network, the process of Location-based services （LBS） has been promoted in a large extent and extracted a lot of researchers’ attention. In Location-based services, various spatial queries have been proposed, e.g., k NN queries and Skyline queries, but these queries do not take spatial and non-spatial attributes into consideration simultaneously. In addition, existing query results in Location-based services are returned from Location-based services provider directly. But Location-based services provider is colluded easily and is not trusted which may collude with attackers or merchants for some interests and returns the garbled or incorrect results to users, it is necessary to provide users with trusted query services and supporting authentication of spatial queries in LBS has become more and more significant for LBS applications to provide high quality and trusted services. Hence, it has important significance to study spatial query under trusted environment. In this paper, in order to make users trust the query results, we mainly focus on the problem of authentication of moving k-dominant nearest neighbor queries, which is a natural combination of k NN queries and Skyline queries. For a given query q, k-dominant NN queries returns k points which are not dominated by spatial and non-spatial attributes and are nearest between all objective points and query q . In order to solve the problem of authentication of moving k -dominant nearest neighbor queries effectively, we first adopt the approach of safe region to address the problem of continuously updating query. Safe region guarantees that the results of moving k-dominant NN query are unchanged as long as the query locates in safe region. Within the safe region, the client does not need to communicate to services provider frequently, thus it can save calculation cost and communication cost. Then we propose a definition about node impact region and design a novel authenticated data structure （ADS） MV 2 R-tree for implementing k -dominant NN query motivated by MR-tree and VoR-tree. With authenticated data structure （ADS）, services provider not only implements k-dominant NN query, but also generates verification object （VO） with verification region. Moreover, to construct the verification regions of the query results and safe region, we propose two methods, denoted as circle-based and rectangle-based, to authenticate the query results and safe region. We have analyzed that rectangle-based method has a better performance than circle - based method. In addition, we also specify the updating process of locations of the client. We propose an updating strategy which can reduce communication cost obviously when the user move out the safe region. Through this way it can reduce communication cost since the client does not need to communicate with services provider frequently. In order to reduce communication cost further, we utilize the method of reusing the previous verification object to solve this problem. At last, we conduct a comprehensive performance evaluation using real dataset and synthetic database to validate our ideas and the proposed algorithms, and the experiment results show that the proposed method can efficiently implement k -dominant nearest neighbor query and verify the query results.