基于MIR树的空间查询验证方法  

Spatial Query Authentication Method Based on MIR Tree

作　　者：任德志 陈炬光 王勇[2] 段晓冉 郝玉洁[2] 吴晓华[1] REN Dezhi;CHEN Juguang;WANG Yong;DUAN Xiaoran;HAO Yujie;WU Xiaohua(School of Information and Software Engineering,University of Electronic Science and Technology of China,Chengdu 610054,China;School of Computer Science and Engineering,University of Electronic Science and Technology of China,Chengdu 611731,China)

机构地区：[1]电子科技大学信息与软件工程学院,成都610054 [2]电子科技大学计算机科学与工程学院,成都611731

出　　处：《计算机工程》2020年第3期114-119,128,共7页Computer Engineering

基　　金：国家重点研发计划(2016QY04W0802);四川省科技计划项目(2016JY0007);中央高校基本科研业务费专项资金(ZYGX2016J216)。

摘　　要：在数据外包服务中,空间多项式函数查询能确保返回用户查询信息的真实性,因而具有较高的应用价值。为解决MIR树中倒排索引文件通信代价过高的问题,采用位图替代倒排索引文件,构造一种支持查询验证的数据索引结构——MRH树,在此基础上构造验证对象生成算法验证查询结果。实验结果表明,在保证查询结果可靠、正确和完整的前提下,相较于MIR树,MRH树能显著地降低通信开销和计算时间。In the data outsourcing service,Spatial Polynomial Function(SPF)query can ensure the authenticity of the query information returned to users,so it has high application value.In order to solve the problem of high communication cost of Inverted File(IF)in MIR tree,by replacing the IF with bitmap,this paper constructs MRH tree,a data index structure supporting query authentication.On this basis,the generation algorithm of Verification Object(VO)is presented to verify the query results.Experimental results show that MRH tree can significantly reduce the communication overhead and computing time of query compared with MIR tree on the premise of ensuring the reliability,correctness and integrity of query results.

关 键 词：空间多项式函数查询 数据外包 查询验证 认证数据结构 默克尔哈希树 

分 类 号：TP309.2[自动化与计算机技术—计算机系统结构]