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

doi:10.19678/j.issn.1000-3428.0054001

计算机工程 ›› 2020, Vol. 46 ›› Issue (3): 114-119,128. doi: 10.19678/j.issn.1000-3428.0054001

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

任德志¹, 陈炬光², 王勇², 段晓冉², 郝玉洁², 吴晓华¹

1. 电子科技大学信息与软件工程学院, 成都 610054;
2. 电子科技大学计算机科学与工程学院, 成都 611731

收稿日期:2019-02-25 修回日期:2019-04-08 发布日期:2020-03-14
作者简介:任德志(1994-),男,硕士研究生,主研方向为网络信息安全;陈炬光,硕士;王勇(通信作者),副教授、博士;段晓冉,硕士;郝玉洁,教授;吴晓华,副教授、博士。
基金资助:
国家重点研发计划（2016QY04W0802）；四川省科技计划项目（2016JY0007）；中央高校基本科研业务费专项资金（ZYGX2016J216）。

Spatial Query Authentication Method Based on MIR Tree

REN Dezhi¹, CHEN Juguang², WANG Yong², DUAN Xiaoran², HAO Yujie², WU Xiaohua¹

1. School of Information and Software Engineering, University of Electronic Science and Technology of China, Chengdu 610054, China;
2. School of Computer Science and Engineering, University of Electronic Science and Technology of China, Chengdu 611731, China

Received:2019-02-25 Revised:2019-04-08 Published:2020-03-14

摘要/Abstract

摘要： 在数据外包服务中，空间多项式函数查询能确保返回用户查询信息的真实性，因而具有较高的应用价值。为解决MIR树中倒排索引文件通信代价过高的问题，采用位图替代倒排索引文件，构造一种支持查询验证的数据索引结构——MRH树，在此基础上构造验证对象生成算法验证查询结果。实验结果表明，在保证查询结果可靠、正确和完整的前提下，相较于MIR树，MRH树能显著地降低通信开销和计算时间。

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

Abstract: 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.

Key words: Spatial Polynomial Function(SPF) query, data outsourcing, query verification, Authentication Data Structure(ADS), Merkle Hash(MH) tree

中图分类号:

TP309.2

任德志, 陈炬光, 王勇, 段晓冉, 郝玉洁, 吴晓华. 基于MIR树的空间查询验证方法[J]. 计算机工程, 2020, 46(3): 114-119,128.

REN Dezhi, CHEN Juguang, WANG Yong, DUAN Xiaoran, HAO Yujie, WU Xiaohua. Spatial Query Authentication Method Based on MIR Tree[J]. Computer Engineering, 2020, 46(3): 114-119,128.

https://www.ecice06.com/CN/Y2020/V46/I3/114

图/表 7

20200321084936

20200321084940

20200321084944

20200321084947

20200321084950

20200321084953

20200321084957

参考文献

[1] HACIGUMUS H,IYER B,MEHROTRA S.Providing database as a service[C]//Proceedings of the 18th International Conference on Data Engineering.Washington D.C.,USA:IEEE Press,2002:29-38.
[2] CHEN Qian,HU Haibo,XU Jianliang.Authenticating top-k queries in location-based services with confidentiality[J].Proceedings of the VLDB Endowment,2013,7(1):49-60.
[3] CHENG W,TAN K L.Authenticating KNN query results in data publishing[C]//Proceedings of Workshop on Secure Data Management.Berlin,Germany:Springer,2007:47-63.
[4] PANG H H,JAIN A,RAMAMRITHAM K,et al.Verifying completeness of relational query results in data publishing[C]//Proceedings of 2005 ACM SIGMOD International Conference on Management of Data.New York,USA:ACM Press,2005:407-418.
[5] MERKLE R C.A certified digital signature[C]//Proceedings of Conference on the Theory and Application of Cryptology.Berlin,Germany:Springer,1989:218-238.
[6] SU Sen,YAN Han,CHENG Xiang,et al.Authentication of top-k spatial keyword queries in outsourced databases[C]//Proceedings of International Conference on Database Systems for Advanced Applications.Berlin,Germany:Springer,2015:567-588.
[7] WU D,CHOI B,XU J,et al.Authentication of moving top-k spatial keyword queries[J].IEEE Transactions on Knowledge and Data Engineering,2014,27(4):922-935.
[8] YANG Y,PAPADOPOULOS S,PAPADIAS D,et al.Spatial outsourcing for location-based services[C]//Proceedings of the 24th International Conference on Data Engineering.Washington D.C.,USA:IEEE Press,2008:1082-1091.
[9] YANG Y,PAPADOPOULOS S,PAPADIAS D,et al.Authenticated indexing for outsourced spatial databases[J].The VLDB Journal,2009,18(3):631-648.
[10] YUAN Duobao,WANG Xiaoming.Query authentication method based on Merkle Hash tree in outsourced database[J].Computer Engineering,2010,36(4):115-117.(in Chinese) 袁多宝,王晓明.基于MH树的外包数据库查询验证方法[J].计算机工程,2010,36(4):115-117.
[11] HONG Jun,WEN Tao,YE Zhengwang,et al.Integrity assurance of outsourced spatial database[J].Journal of Northeastern University(Natural Science),2019,40(3):327-333.(in Chinese) 洪军,温涛,叶正旺,等.外包空间数据库的完整性保证机制[J].东北大学学报(自然科学版),2019,40(3):327-333.
[12] ZHANG Yanhui,WANG Xiaoming.Improved authentication of queries in outsourced database[J].Computer Engineering and Application,2012,48(6):73-76.(in Chinese)张艳辉,王晓明.一种改进的外包数据库查询验证技术[J].计算机工程与应用,2012,48(6):73-76.
[13] ZHANG Yanhui.Research on query and validation technology of outsourcing XML database[D].Guangzhou:Jinan University,2012.(in Chinese)张艳辉.外包XML数据库查询验证技术研究[D].广州:暨南大学,2012.
[14] ZHAO Meng,WANG Lei,KUANG Lin'ai,et al.Range query integrity verification based on Merkle Hash tree[J].Journal of Southeast University(Natural Science Edition),2017,47(S1):118-122.(in Chinese)赵蒙,王雷,匡林爱,等.基于Merkle哈希树的范围查询验证技术[J].东南大学学报(自然科学版),2017,47(增刊):118-122.
[15] PANG H H,MOURATIDIS K.Authenticating the query results of text search engines[J].Proceedings of the VLDB Endowment,2008,1(1):126-137.
[16] WANG Yong,GAO Shimeng,ZHANG Junhao,et al.Authenticating multiple user-defined spatial queries[C]//Proceedings of the 40th Annual Computer Software and Applications Conference.Washington D.C.,USA:IEEE Press,2016:471-480.
[17] WANG Yong,DUAN Xiaoran,YANG Xiaodong,et al.Processing multiple-user location-based keyword queries[J].IEICE Transactions on Information and Systems,2018,101(6):1552-1561.
[18] DUAN Xiaoran,WANG Yong,CHEN Juguang,et al.Authenticating preference-oriented multiple users spatial queries[C]//Proceedings of the 41st Annual Computer Software and Applications Conference.Washington D.C.,USA:IEEE Press,2017:602-607.
[19] ZHANG Rui,SUN Jingchao,ZHANG Yanchao,et al.Secure spatial top-k query processing via untrusted location-based service providers[J].IEEE Transactions on Dependable and Secure Computing,2014,12(1):111-124.
[20] LI Z,LEE K C K,ZHENG B,et al.IR-tree:an efficient index for geographic document search[J].IEEE Transactions on Knowledge and Data Engineering,2010,23(4):585-599.
[21] CAO Xin,CONG Gao,GUO Tao,et al.Efficient processing of spatial group keyword queries[J].ACM Transactions on Database Systems,2015,40(2):1-48.

选择文件类型/文献管理软件名称

选择包含的内容

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

Spatial Query Authentication Method Based on MIR Tree

RichHTML

PDF

可视化

被引次数

摘要/Abstract

引用本文

使用本文

图/表 7

参考文献

相关文章 4

编辑推荐

Metrics

本文评价

[1]	于莹莹, 丁红发, 蒋合领. 图数据精确最短距离的隐私保护外包计算方案[J]. 计算机工程, 2023, 49(9): 158-171.
[2]	吴兴华,张爱新,李建华. 基于向量承诺与代理重加密的数据外包及分享方案[J]. 计算机工程, 2018, 44(10): 1-5.
[3]	张艳辉, 王晓明. 外包XML数据库查询验证技术[J]. 计算机工程, 2012, 38(20): 49-51.
[4]	袁多宝;王晓明. 基于MH树的外包数据库查询验证方法[J]. 计算机工程, 2010, 36(4): 115-117.

模态框（Modal）标题

选择文件类型/文献管理软件名称

选择包含的内容

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

Spatial Query Authentication Method Based on MIR Tree

RichHTML

PDF

可视化

被引次数

摘要/Abstract

引用本文

使用本文

图/表 7

参考文献

相关文章 4

编辑推荐

Metrics

本文评价