Research on Reachability Indexing for Very Large Graphs
| 摘要 | 第4-5页 |
| Abstract | 第5页 |
| 第一章 绪论 | 第8-13页 |
| 1.1 研究背景 | 第8-9页 |
| 1.2 国内外研究现状 | 第9-11页 |
| 1.3 研究内容 | 第11-12页 |
| 1.4 论文组织结构 | 第12-13页 |
| 第二章 相关技术与研究 | 第13-23页 |
| 2.1 图的基本存储结构 | 第13页 |
| 2.2 图上可达性查询索引技术 | 第13-23页 |
| 2.2.1 2-Hop标签 | 第13-16页 |
| 2.2.2 区间索引 | 第16-19页 |
| 2.2.3 混合2-Hop标签和区间索引 | 第19-20页 |
| 2.2.4 传递闭包的压缩编码 | 第20-21页 |
| 2.2.5 预处理压缩图规模 | 第21-23页 |
| 第三章 TLBCS：阶递增的2-Hop标签 | 第23-34页 |
| 3.1 引言 | 第23-24页 |
| 3.2 针对k-partite图 | 第24-29页 |
| 3.2.1 标签定义 | 第24-26页 |
| 3.2.2 正确性证明 | 第26-29页 |
| 3.3 对跨边的处理 | 第29-32页 |
| 3.3.1 标签定义 | 第29-30页 |
| 3.3.2 正确性证明 | 第30-32页 |
| 3.4 对比TF标签 | 第32-33页 |
| 3.5 本章小结 | 第33-34页 |
| 第四章 TLBCS标签的建立与查询算法 | 第34-39页 |
| 4.1 TLBCS标签的建立算法 | 第34-37页 |
| 4.1.1 拓扑层次数生成算法 | 第34页 |
| 4.1.2 减序列和增序列生成算法 | 第34-36页 |
| 4.1.3 标签生成算法 | 第36-37页 |
| 4.1.4 正确性证明 | 第37页 |
| 4.2 标签的查询算法 | 第37-38页 |
| 4.3 本章小结 | 第38-39页 |
| 第五章 TLBCS标签的优化 | 第39-42页 |
| 5.1 虚点删除 | 第39-40页 |
| 5.2 删除基于虚边的高度数的点 | 第40-41页 |
| 5.3 本章小结 | 第41-42页 |
| 第六章 实验 | 第42-49页 |
| 6.1 大规模实际数据集 | 第42-46页 |
| 6.1.1 数据集 | 第42-43页 |
| 6.1.2 评估删除基于虚边的高度数的点的影响 | 第43-44页 |
| 6.1.3 对比实验 | 第44-46页 |
| 6.2 大规模合成数据集 | 第46-49页 |
| 6.2.1 指标选取 | 第46-47页 |
| 6.2.2 合成数据集生成方法 | 第47页 |
| 6.2.3 实验分析 | 第47-49页 |
| 第七章 结论与展望 | 第49-50页 |
| 致谢 | 第50-51页 |
| 参考文献 | 第51-53页 |
