外包空间数据库的完整性保证机制
|
摘要
存储在云计算服务提供商上的用户数据可能被篡改或删除,查询完整性验证方案的作用是确保查询用户能够验证查询结果中的数据是真实的且包含所有满足条件的数据.本文在现有验证树结构基础上进行改进,提出了一种空间验证数据结构VSS-tree.利用SS-tree作为基本结构并为其附加验证信息,采用边界球进行区域划分增大了节点的度,有效降低了验证树的高度,并避免了不必要的磁盘访问,从而提高了空间查询验证的处理效率.实验结果表明,该方案比MR-tree具有更好的性能.
User's data stored on a cloud computing service provider may be tampered or deleted.The query integrity verification scheme enables a query user to verify that the data in the query results is authentic and all the data that meet the criteria are in the query results. As an improvement of the existing authenticated tree schemes,a space authenticated data structure,called verifiable SS-tree( VSS-tree), is proposed to support spatial query and query authentication. The VSS-tree extends each node of SS-tree with authentication information.Boundary sphere is used for region shape which increases the degree of node and thus reduces the height of authenticated tree. Furthermore,it can avoid unnecessary disk access,which improves the processing efficiency of spatial query verification. Experimental results showed that VSS-tree can efficiently support spatial query and has better performance than MR-tree.
User's data stored on a cloud computing service provider may be tampered or deleted.The query integrity verification scheme enables a query user to verify that the data in the query results is authentic and all the data that meet the criteria are in the query results. As an improvement of the existing authenticated tree schemes,a space authenticated data structure,called verifiable SS-tree( VSS-tree), is proposed to support spatial query and query authentication. The VSS-tree extends each node of SS-tree with authentication information.Boundary sphere is used for region shape which increases the degree of node and thus reduces the height of authenticated tree. Furthermore,it can avoid unnecessary disk access,which improves the processing efficiency of spatial query verification. Experimental results showed that VSS-tree can efficiently support spatial query and has better performance than MR-tree.
引文
[1]Yang Y,Papadopoulos S,Papadias D,et al.Authenticated indexing for outsourced spatial databases[J].VLDB Journal,2009,18(3):631-648.
[2]White D A,Jain R.Similarity indexing with the SS-tree[C]//Twelfth International Conference on Data Engineering.New Orleans:IEEE,1996:516-523.
[3]Cheng W,Pang H H,Tan K L.Authenticating multidimensional query results in data publishing[C]//Data and Applications Security Xx,IFIP Wg 11.3 Working Conference on Data and Applications Security.Berlin:Springer,2006:60-73.
[4]Papadopoulos S,Yang Y,Bakiras S,et al.Continuous spatial authentication[J].Lecture Notes in Computer Science,2009,5644:62-79.
[5]Ku W S,Hu L,Shahabi C,et al.A query integrity assurance scheme for accessing outsourced spatial databases[J].Geoinformatica,2013,17(1):97-124.
[6]Nutanong S,Zhang R,Tanin E,et al.The V*-diagram:a query-dependent approach to moving k NN queries[J].Proceedings of the VLDB Endowment,2008,1(1):1095-1106.
[7]Man L Y,Lo E,Yung D.Authentication of moving k NNqueries[C]//International Conference on Data Engineering.Hannover:IEEE,2011:565-576.
[8]Hu L,Ku W S,Bakiras S,et al.Verifying spatial queries using Voronoi neighbors[C]//Proceeding of the 18thSIGSPATIInternational Conference on Advances in Geographic Information Systems.San Jose:ACM,2010:350-359.
[9]Wang H,Yin J,Perng C S,et al.Dual encryption for query integrity assurance[C]//ACM Conference on Information and Knowledge Management.Napa Valley:ACM,2008:863-872.
[10]Xie M,Wang H,Yin J,et al.Integrity auditing of outsourced data[C]//International Conference on Very Large Data Bases.Vienna:DBLP,2007:782-793.
[11]Katayama N,Satoh S.The SR-tree:an index structure for highdimensional nearest neighbor queries[J].ACM Sigmod Record,1997,26(2):369-380.
[2]White D A,Jain R.Similarity indexing with the SS-tree[C]//Twelfth International Conference on Data Engineering.New Orleans:IEEE,1996:516-523.
[3]Cheng W,Pang H H,Tan K L.Authenticating multidimensional query results in data publishing[C]//Data and Applications Security Xx,IFIP Wg 11.3 Working Conference on Data and Applications Security.Berlin:Springer,2006:60-73.
[4]Papadopoulos S,Yang Y,Bakiras S,et al.Continuous spatial authentication[J].Lecture Notes in Computer Science,2009,5644:62-79.
[5]Ku W S,Hu L,Shahabi C,et al.A query integrity assurance scheme for accessing outsourced spatial databases[J].Geoinformatica,2013,17(1):97-124.
[6]Nutanong S,Zhang R,Tanin E,et al.The V*-diagram:a query-dependent approach to moving k NN queries[J].Proceedings of the VLDB Endowment,2008,1(1):1095-1106.
[7]Man L Y,Lo E,Yung D.Authentication of moving k NNqueries[C]//International Conference on Data Engineering.Hannover:IEEE,2011:565-576.
[8]Hu L,Ku W S,Bakiras S,et al.Verifying spatial queries using Voronoi neighbors[C]//Proceeding of the 18thSIGSPATIInternational Conference on Advances in Geographic Information Systems.San Jose:ACM,2010:350-359.
[9]Wang H,Yin J,Perng C S,et al.Dual encryption for query integrity assurance[C]//ACM Conference on Information and Knowledge Management.Napa Valley:ACM,2008:863-872.
[10]Xie M,Wang H,Yin J,et al.Integrity auditing of outsourced data[C]//International Conference on Very Large Data Bases.Vienna:DBLP,2007:782-793.
[11]Katayama N,Satoh S.The SR-tree:an index structure for highdimensional nearest neighbor queries[J].ACM Sigmod Record,1997,26(2):369-380.
© 2004-2018 中国地质图书馆版权所有 京ICP备05064691号 京公网安备11010802017129号 地址：北京市海淀区学院路29号 邮编：100083 电话：办公室：(+86 10)66554848；文献借阅、咨询服务、科技查新：66554700 |