Range query authentication for outsourced spatial databases

doi:10.11772/j.issn.1001-9081.2017.04.1021

Journal of Computer Applications ›› 2017, Vol. 37 ›› Issue (4): 1021-1025.DOI: 10.11772/j.issn.1001-9081.2017.04.1021

Previous Articles Next Articles

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

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

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

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

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

Abstract

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)

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

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

CLC Number:

TP311

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

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

References

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

[1]	BAO Xuan, CHEN Hongmei, XIAO Qing. Time-incorporated point-of-interest collaborative recommendation algorithm [J]. Journal of Computer Applications, 2021, 41(8): 2406-2411.
[2]	XU Jiangfeng, TAN Yulong. Optimization of multidimensional index query mechanism based on HBase [J]. Journal of Computer Applications, 2020, 40(2): 571-577.
[3]	FU Yu, WANG Hong. Virtual trajectory filling algorithm for location privacy protection [J]. Journal of Computer Applications, 2019, 39(8): 2318-2325.
[4]	CUI Weirong, DU Chenglie. Fast proximity testing method with privacy preserving in mobile social network [J]. Journal of Computer Applications, 2017, 37(6): 1657-1662.
[5]	ZHAO Dapeng, SONG Guangxuan, JIN Yuanyuan, WANG Xiaoling. Query probability-based location privacy protection approach [J]. Journal of Computer Applications, 2017, 37(2): 347-351.
[6]	KONG Yangxin, JIN Cheqing, WANG Xiaoling. Population flow analysis based on cellphone trajectory data [J]. Journal of Computer Applications, 2016, 36(1): 44-51.
[7]	WANG Fuqiang, PENG Furong, DING Xiaohuan, LU Jianfeng. Location-based asymmetric similarity for collaborative filtering recommendation algorithm [J]. Journal of Computer Applications, 2016, 36(1): 171-174.
[8]	YUAN Xi, LI Qiang. Research and development of intelligent healthy community system based on mobile Internet [J]. Journal of Computer Applications, 2015, 35(1): 239-242.
[9]	LIU Zhaobin LIU Wenzhi FANG Ligang TANG Yazhe. Channel allocation model and credibility evaluation for LBS indoor nodes [J]. Journal of Computer Applications, 2013, 33(03): 603-606.
[10]	ZHANG Yong-hui LIN Zhang-xi LIU Jian-hua LIANG Quan. Delay tolerant network routing resource allocation model on general k-anycast [J]. Journal of Computer Applications, 2012, 32(12): 3494-3498.
[11]	YUAN Shu-han CHEN Wei-bin FU Shun-kai. User behavior similarity analysis of location based social network [J]. Journal of Computer Applications, 2012, 32(02): 322-325.
[12]	TAN Rong GU Jun-zhong LIN Xin CEHN Peng. Range-based approach for multi-object convergence problem [J]. Journal of Computer Applications, 2011, 31(09): 2389-2394.
[13]	. Trusted anonymity communication protocol for mobile Internet [J]. Journal of Computer Applications, 2010, 30(10): 2669-2671.
[14]	Qin ZHU . Digital watermark-based authentication of queries in outsourced database [J]. Journal of Computer Applications, 2008, 28(3): 605-608.
[15]	ZHONG Shi-ming,ZHANG Sheng,GU Zhi-li,ZHU Cai-lian. Design and implementation of mobile agent-based LBS application platform [J]. Journal of Computer Applications, 2005, 25(10): 2306-2309.

Range query authentication for outsourced spatial databases

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

PDF

Knowledge

Abstract

Cite this article

share this article

References

Related Articles 15

Recommended Articles

Metrics