图数据隐私保护可达性查询算法研究.pdf

《图数据隐私保护可达性查询算法研究.pdf》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第41卷第2期计算机工程2015年2月VO1．41NO．2ComputerEngineeringFebruary2015·人工智能及识别技术·文章编号：1000．3428(2015)02-0167．06文献标识码：A中图分类号：TP391图数据隐私保护可达性查询算法研究尹树祥，靳婷(复旦大学计算机科学技术学院智能信息处理重点实验室，上海200433)摘要：数据库领域越来越多的数据通过图的结构进行存储，随着图数据规模的快速增长和云计算的兴起，数据拥有者希望将数据外包给具有强大计算能力的服务商为其客户提供查询服务。为解决数据库中

2、的可达性查询问题，提出一种隐私保护的可达性索引和查询方法。对原始的2-hop索引构建方法进行优化，设计maxlSCover启发式方法，给出根据人工节点添加算法建立PP一2一hop索引的unifyIS和unifyLS算法，并在此基础上，给出基于密文域的优化可达性查询方法。实验结果表明，基于maxlSCover优化方法和unifyIS算法建立的索引大小相比于基于原始2一hop索引的方法减小1个一2个数量级。关键词：图数据；可达性查询；2-hop索引；隐私保护；人工节点；查询服务中文引用格式：尹树祥，靳婷．图数据隐私保护可达性查询

3、算法研究[J]．计算机工程，2015，41(2)：167-172．英文引用格式：YinShuxiang，JinTing．ResearchonPrivacyProtectionReachabilityQueryAlgorithmofGraphData[J]．ComputerEngineering，41(2)：167—172．ResearchonPrivacyProtectionReachabilityQueryAlgorithmofGraphDataYINShuxiang，JINTing(KeyLabofIntelligent

4、InformationProcessing，SchoolofComputerScience，FudanUniversity，Shanghai200433，China)【Abstract】Duetothemassivevolumeofgraphdatafromawiderangeofrecentapplicationsandunprecedentedgraphdatagrowth，itisbecomingeconomicallyappealingfordataownerstooutsourcetheirdatatoapower

5、fulServiceProvider(SP)，suchasacloudcomputingplatform，whichprovideshighcomputationalqueryservices．Thispaperstudiesanovelprivacypreserving2-hopindexandqueryalgorithmforafundamentalqueryforgraphsnamelythereachabilityquery．Itoptimizestheexistingmethodforbuilding2-hopin

6、dex，proposesoneoptimizingmethod(maxlSCover)，andtwoalgorithms(unifyISandunifyLS)tobuildprivacypreserving2-hop(PP一2一hop)indexbyaddingsomesurrogatenodes，andraisesupanoptimizedqueryprocessingalgorithmbasedonPP一2一hopindex．Experimentalresultsshowthattheindexsizeofthisalg

7、orithmbasedonmaxlSCoveroptimizationmethodandtheunifyISisreducedby1～2ordersofmagnitude，comparedwiththemethodbasedontheoriginal2-hop．【Keywords】graphdata；reachabilityquery；2-hopindex；privacyprotection；artificialnode；queryserviceDOI：10．3969／j．issn．1000—3428．2015．02．032

8、得信赖的，同时，数据拥有者不希望有未授权的用户1概述知道他们的图数据，所以，安全和隐私保护成为服务随着大数据的发展，越来越多的应用通过图结质量的一个重要衡量指标。构的方式存储数据，如生物信息学、社交网络以及半图数据上的可达性查询是数据库领域中最为结构化数据XML等。尽管图数据的检索和挖掘已