Journal of Computer Applications ›› 2017, Vol. 37 ›› Issue (4): 1021-1025.DOI: 10.11772/j.issn.1001-9081.2017.04.1021

Previous Articles     Next Articles

Range query authentication for outsourced spatial databases

HU Xiaoyan1, WANG Jingyu2, LI Hairong1   

  1. 1. Engineering Training Center, Inner Mongolia University of Science and Technology, Baotou Nei Mongol 014010, China;
    2. Information and Network Center, Inner Mongolia University of Science and Technology, Baotou Nei Mongol 014010, China
  • Received:2016-10-31 Revised:2016-12-20 Online:2017-04-10 Published:2017-04-19
  • Supported by:
    This work is partially supported by the National Natural Science Foundation of China (61462056,71363040), the Natural Science Foundation of Inner Mongolia (2016MS0609).

面向外包空间数据库的范围查询验证

胡晓燕1, 王静宇2, 李海荣1   

  1. 1. 内蒙古科技大学 工程训练中心, 内蒙古 包头 014010;
    2. 内蒙古科技大学 网络中心, 内蒙古 包头 014010
  • 通讯作者: 胡晓燕
  • 作者简介:胡晓燕(1980-),女,内蒙古凉城人,讲师,硕士,主要研究方向:云计算、数据库管理;王静宇(1976-),男,河南开封人,副教授,博士,CCF会员,主要研究方向:云计算、信息安全;李海荣(1976-),女,内蒙古巴彦淖尔人,副教授,硕士,主要研究方向:云存储。
  • 基金资助:
    国家自然科学基金资助项目(61462056,71363040);内蒙古自然科学基金资助项目(2016MS0609)。

Abstract: In existing spatial range query authenticating methods such as VR-tree and MR-tree, the transmission cost of the server to the client is high and the verification efficiency of the client is low because the Verification Object (VO) contains too much authentication information. To resolve these problems, a new index structure MGR-tree was proposed. First of all, by means of embedding a R-tree in each leaf node of Grid-tree, the size of VO decreased, and the efficiency of query and authentication was improved. In addition, an optimal index MHGR-tree which takes advantage of the property of Hilbert curve and a filter policy were proposed to accelerate the verification. Experimental results show that the proposed method has a better performance compared with MR-tree. In the best case, the verification object size and authentication time of MHGR are 63% and 19% of MR respectively.

Key words: mobile Internet, location-based service, database outsourcing, query authentication, Verification Object (VO)

摘要: 针对空间范围查询验证方法(例如VR-tree和MR-tree)普遍存在验证对象(VO)中包含大量的节点验证信息,造成服务器到客户端的传输代价较大以及客户端验证效率较低等问题,提出一种新的验证索引结构(ADS)MGR-tree。首先利用拆分思想,通过在Grid-tree的叶子节点中嵌入R-tree,并结合Merkle哈希树的验证方法,极大地减小VO的大小,提高查询和验证的效率。在此基础上,利用Hilbert曲线降维的特性,构建了优化的索引结构MHGR-tree,并提出一种过滤策略,进一步提高验证的效率。实验结果表明,所提方法具有更好的表现。在最好情况下,MHGR的VO大小和验证时间仅为MR的63%和19%。

关键词: 移动互联网, 位置服务, 数据库外包, 查询验证, 验证对象

CLC Number: