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

来源：计算机应用杂志2017年第4期北京时间：

作者：胡晓燕, 王静宇, 李海荣

单位：1. 内蒙古科技大学 工程训练中心, 内蒙古 包头 014010;2. 内蒙古科技大学 网络中心, 内蒙古 包头 014010

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

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

基金资助：国家自然科学基金资助项目（61462056，71363040）；内蒙古自然科学基金资助项目（2016MS0609）。