基于C+-树的聚簇图子图检索机制研究

摘要

图由于可以明确记录社交应用中的个体特征以及个体活动和关系而被广泛使用。由于此类数据包含有个体的信息，为了防止恶意攻击者根据个体特定的好友关系将个体还原得到个体的信息，数据拥有者在共享此类图时，采取聚簇化的措施隐藏个体信息和关系，如何在聚簇化后的图集合上实现子图的有效检索成为重要问题。
　　扩展于C-树的C+-树的可以用作解决聚簇化后图集合中子图检索问题的索引结构。索引建立过程：根据给定的衡量标准，将相似度较大的图联合起来，组成两图的closure；在满足参数设置的情况下，重复该过程，直到建立一个树形的索引结构C+-树。子图检索过程：根据子图的结构约束和属性约束从根节点开始层次遍历C+-树，若某节点不满足查询约束，则过滤该节点的子孙节点；若某节点满足查询要求，则继续检测其孩子节点；通过该方式过滤不满足查询约束的数据图，缩小检索范围，提高检索效率。在检索过程中，为了解决查询图与聚簇图匹配时特有的多对一的映射关系问题，提出了VFoCG算法，用于解决匹配过程中多对一的特殊映射问题。
　　为了测试C+-树的检索性能，在真实数据集合和合成数据集合中测试了C+-树的检索性能。测试结果显示，C+-树具有良好的检索能力，平均可过滤掉数据集合中50％的数据图；索引结构的空间开销与数据集合大小之间的线性关系证实了C+-树的良好的可扩展性。

目录

封面

声明

中文摘要

英文摘要

目录

1 绪论

1.1 问题提出

1.2 国内外研究现状

1.3 课题背景和研究内容

1.4 组织结构

2 聚簇图的数据模型

2.1 聚簇图的形式化定义

2.2 信息损失

2.3 问题定义

2.4 复杂度分析

2.5 小结

3 聚簇图子图检索的关键技术

3.1 C+-树索引结构

3.2聚簇图子图匹配算法

3.3子图检索过程

3.4 小结

4 性能测试

4.1 测试环境

4.2 真实数据集合测试结果与分析

4.3 合成数据集合测试结果与分析

4.4 小结

5 总结与展望

致谢

参考文献

附录1 攻读硕士期间发表的论文

附录2 攻读硕士期间申请的国家发明专利

附录3 攻读硕士期间参与的项目