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

摘要

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