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

doi:10.11772/j.issn.1001-9081.2017.04.1021

计算机应用 ›› 2017, Vol. 37 ›› Issue (4): 1021-1025.DOI: 10.11772/j.issn.1001-9081.2017.04.1021

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

胡晓燕¹, 王静宇², 李海荣¹

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

收稿日期:2016-10-31 修回日期:2016-12-20 出版日期:2017-04-10 发布日期:2017-04-19
通讯作者: 胡晓燕
作者简介:胡晓燕(1980-),女,内蒙古凉城人,讲师,硕士,主要研究方向:云计算、数据库管理;王静宇(1976-),男,河南开封人,副教授,博士,CCF会员,主要研究方向:云计算、信息安全;李海荣(1976-),女,内蒙古巴彦淖尔人,副教授,硕士,主要研究方向:云存储。
基金资助:
国家自然科学基金资助项目（61462056，71363040）；内蒙古自然科学基金资助项目（2016MS0609）。

Range query authentication for outsourced spatial databases

HU Xiaoyan¹, WANG Jingyu², LI Hairong¹

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).

摘要/Abstract

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

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

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)

中图分类号:

TP311

胡晓燕, 王静宇, 李海荣. 面向外包空间数据库的范围查询验证[J]. 计算机应用, 2017, 37(4): 1021-1025.

HU Xiaoyan, WANG Jingyu, LI Hairong. Range query authentication for outsourced spatial databases[J]. Journal of Computer Applications, 2017, 37(4): 1021-1025.

参考文献

[1] DEVANBU P, GERTZ M, MARTEL C, et al. Authentic third-party data publication[M]//THURAISINGHAM B, VAN DE RIET R, DITTRICH K R, et al. Data and Application Security. Berlin: Springer, 2000: 101-112.
[2] MERKLE R C. A certified digital signature[C]//CRYPTO 1989: Proceedings on Advances in Cryptology. Berlin: Springer, 1989: 218-238.
[3] PANG H H, TAN K L. Authenticating query results in edge computing[C]//Proceedings of the 20th International Conference on Data Engineering. Piscataway, NJ: IEEE, 2004: 560-571.
[4] PANG H H, JAIN A, RAMAMRITHAM K, et al. Verifying completeness of relational query results in data publishing[C]//SIGMOD 2005: Proceedings of the 2005 ACM SIGMOD International Conference on Management of Data. New York: ACM, 2005: 407-418.
[5] NARASIMHA M, TSUDIK G. DSAC: integrity of outsourced databases with signature aggregation and chaining[C]//CIKM 2005: Proceedings of the 14th ACM International Conference on Information and Knowledge Management. New York: ACM, 2005: 235-236.
[6] CHENG W, PANG H H, TAN K. Authenticating multi-dimensional query results in data publishing[C]//DBSEC 2006: Proceedings of the 20th IFIP WG 11.3 Working Conference on Data and Applications Security. Berlin: Springer, 2006: 60-73.
[7] LI F, HADJIELEFTHERIOU M, KOLLIOS G, et al. Dynamic authenticated index structures for outsourced databases[C]//SIGMOD 2006: Proceedings of the 2006 ACM SIGMOD International Conference on Management of Data. New York: ACM, 2006: 121-132.
[8] YANG Y, PAPADOPOULOS S, PAPADIAS D, et al. Authenticated indexing for outsourced spatial databases[J]. The VLDB Journal, 2009, 18(3): 631-648.
[9] YANG Y, PAPADOPOULOS S, PAPADIAS D, et al. Spatial outsourcing for location-based services[C]//ICDE 2008: Proceedings of the 2008 IEEE 24th International Conference on Data Engineering. Washington, DC: IEEE Computer Society, 2008: 1082-1091.
[10] MOURATIDIS K, SACHARIDIS D, PANG H H. Partially materialized digest scheme: an efficient verification method for outsourced databases[J]. The VLDB Journal, 2009, 18(1): 363-381.
[11] 谢晴晴, 王良民.基于PMD的外包数据流范围查询验证方案[J]. 计算机科学与探索, 2015, 9(10): 1209-1218.(XIE Q Q, WANG L M. Data stream range query authentication scheme based on PMD in outsourced database[J]. Journal of Frontiers of Computer Science and Technology, 2015, 9(10): 1209-1218.)
[12] HU H, XU J, CHEN G, et al. Authenticating location-based services without compromising location privacy[C]//SIGMOD 2012: Proceedings of the 2012 ACM SIGMOD International Conference on Management of Data. New York: ACM, 2012: 301-312.

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

Range query authentication for outsourced spatial databases

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 11

编辑推荐

Metrics

[1]	元广杰, 李小东, 江照意, 苑鹏, 郭志潍. 路测数据驱动的移动终端定位方法[J]. 计算机应用, 2016, 36(12): 3515-3520.
[2]	孔扬鑫, 金澈清, 王晓玲. 基于手机轨迹数据的人口流动分析[J]. 计算机应用, 2016, 36(1): 44-51.
[3]	王付强, 彭甫镕, 丁小焕, 陆建峰. 基于位置的非对称相似性度量的协同过滤推荐算法[J]. 计算机应用, 2016, 36(1): 171-174.
[4]	袁熙, 李强. 基于移动互联的智慧健康社区系统的研发[J]. 计算机应用, 2015, 35(1): 239-242.
[5]	刘昭斌刘文芝方立刚唐亚哲. 基于位置服务室内节点的信道分配模型与可信度评估[J]. 计算机应用, 2013, 33(03): 603-606.
[6]	张永晖林漳希刘建华梁泉. 容迟网络广义k选播路由资源分配模型[J]. 计算机应用, 2012, 32(12): 3494-3498.
[7]	周彦伟吴振强乔子芮. 移动互联网可信匿名通信模型[J]. 计算机应用, 2010, 30(10): 2669-2671.
[8]	朱勤陈继红乐嘉锦. 基于数字水印的外包数据库查询验证[J]. 计算机应用, 2008, 28(3): 605-608.
[9]	秦宇锋曾广周 . 迁移工作流系统中位置服务体系结构的研究与设计[J]. 计算机应用, 2007, 27(10): 2595-2597.
[10]	沈军;曹元大;张树东. Ad Hoc网络位置辅助广播协议[J]. 计算机应用, 2005, 25(11): 2492-2495.
[11]	沈军, 曹元大, 张树东. 一种改进的位置信息服务方法[J]. 《计算机应用》唯一官方网站, 2005, 25(03): 530-532.