图上可达性查询的隐私保护方法研究

《图上可达性查询的隐私保护方法研究》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、万方数据指导小组成员名单周水庚教授万方数据复旦大学硕士学位论文目录摘要．．．．．．．．Abstract．．+．．目录12第一章引言，．--．．．-·．。··········----·-····3t．1研究背景和意义，．，．．，．．．．．．．．．．．．．．．．．312研究内容和研究成果．．．．，，．．．．．．．，．．．．．．．．．，，41．3本文结构．．．．．．．．．．．．．．．．．．，．．．．．．．．．．．6第二章相关工作·．·，···--···t-····-······一t72．1图数据库上隐私保护方法概述．．。．．．．．．．．．．．．．．．．．72．2图数据库查询验证．．．．．．．．

2、．．．．．．．．．．．，，．．．82．3基于隐私保护的图查询服务．．．．．．．．．．．．．．．．．．．82．4可达性查询算法概述．．．．．．．．．．．．．．．．．，，．．．92．5本章小结．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．13第三章问题定义与系统概述．．一·-·····，···。-’。·。143．12-hop索引方法．．．．．．．．．．．．．．．，．．．．．．．．．．．．143．2密码学知识．．．．．．．．．．．．．，．．．．．．．．．．．．．．．．．163．3可达性查询的隐私保护问题定义．．．．．．．．．．．．．．．173．4本章小结．．．．．．．．．．．

3、．．．．，．．．．．．．．．．．18第四章图上可达性查询的隐私保护算法-·······-一·-···194．1具有Imax感知的2一hop算法．．．．．．．．．．．．．．．．．．．．194．2代理节点的添加算法．．．．．．．．．．．．，．．．．，．．．．．，．．2l4．2．1交集大小归一化．．．．．．．．．．．．．．．．，．．．．．．214．2．2LiⅡ$口Lout大，4、归一化．．．．．．．．．．．．．．．，．，．254．3索弓l加密处理算法．．．．．．．．．．．．．．．．．．．．．．．．．27i万方数据复旦大学硕士学位论文目录4．4隐私保护的可达性查询处理．．．，．．4．5图上可达性

4、查询的隐私保护算法的隐私分析4．6实验结果．．．．．．．．．．．．．．．．．．4．6．1合成数据集上的实验．．．．．．．4．6．2真实数据集上的实验．．．．．．．．4．7本章小结．．．．．．．．．．．．．．．．．．第五章稀疏图上可达性查询隐私保护方法···5．1m一2一hop索引算法．．．．．．5．1．1m一2一hop算法分析．．．．．．．．．5．1．2基于启发式方法的m-2一hop构建算法5．2基于m一2一hop的W达性查询的隐私保护算法5．3实验结果．，．，．．．．．5．4本章小结．第六章总结与展望参考文献．．．．．．学术论文．．．．．．致谢．．．-．．-·上l船∞弛鲳拍{号钾盯鼹册

5、姐乾船必诣加驵万方数据摘要在数据库领域中，越来越多的数据通过图结构的方式进行存储，比如社交网络、生物信息学以及XML数据等。针对这些图数据的查询，很多时候需要更强大的计算机资源进行处理。为解决该问题，比较经济实用的方法是将这些数据外包给一个第三方的服务提供商(ServiceProvider，SP)，让它去为我们提供查询服务。然而，SP并不是一直可以值得信赖，它可能对外包到它上面的数据比较感兴趣，以获得商业利益。除此之外，数据拥有者(DataOwner)不希望他的数据被不信任的人获取，同时查询者也不希望他的查询内容被他人得知。可达性查询作为数据库领域一个最基础的问题，本文针对可达性查询过程

6、中可能产生的隐私问题，提出了图数据上可达性查询的隐私保护方法。我们的隐私保护目标主要包括：客户端查询信息和图数据结构信息。针对我们提出的隐私保护目标，我们在基于传统的2．hop索引方法上，根据图数据不同的稀疏性质，提出了pp一2一hop和ppm-2一hop两种索引方法。在这两种索引方法中，我们对原始的2一hop索引通过不同的添加人工代理中心点策略，使得对于任何的可达性查询，其查询结果大小一致，进而‘SP无法从相同大小的查询结果中获取关于查询的信息。同时，我们通过对索引进行加密，使得所有的可达性查询在密文域中进行，进一步阻止SP对索引内容进行推理。本文对两种索引算法分别在基于密文攻击和基于

7、集合大小的攻击模式下进行安全性分析。最后，分别对两种索引算法在合成数据集和真实数据集上进行实验研究。关键词：图数据、可达性查询、2-hop索引、隐私保护、查询服务中图分类号：TP311万方数据复旦大学硕士学位论文AbstractDuetothemassivevolumeofgraphdatafromawiderangeofrecentappli—cations，suchaSsocialnetwork；bioinformaticsan