| 摘要 | 第5-7页 |
| Abstract | 第7-8页 |
| 第1章 绪论 | 第12-20页 |
| 1.1 云计算 | 第12-13页 |
| 1.2 大数据 | 第13-14页 |
| 1.3 迭代计算 | 第14-16页 |
| 1.3.1 搜索引擎 | 第14-15页 |
| 1.3.2 社交网络 | 第15页 |
| 1.3.3 影音推荐 | 第15-16页 |
| 1.3.4 其它领域 | 第16页 |
| 1.4 课题研究背景及意义 | 第16-17页 |
| 1.5 论文主要贡献及组织结构 | 第17-20页 |
| 1.5.1 论文主要贡献 | 第17-18页 |
| 1.5.2 论文组织结构 | 第18-20页 |
| 第2章 大数据迭代计算的相关工作 | 第20-30页 |
| 2.1 通用分布式计算框架MapReduce | 第20-24页 |
| 2.1.1 MapReduce编程模型 | 第20-21页 |
| 2.1.2 MapReduce执行流程 | 第21-22页 |
| 2.1.3 Hadoop | 第22-24页 |
| 2.1.4 Hadoop MapReduce中的迭代计算 | 第24页 |
| 2.2 支持迭代计算的分布式框架 | 第24-27页 |
| 2.3 其它相关工作 | 第27-29页 |
| 2.3.1 平台 | 第27-28页 |
| 2.3.2 计算 | 第28页 |
| 2.3.3 存储 | 第28-29页 |
| 2.4 小结 | 第29-30页 |
| 第3章 iMapReduce：基于MapReduce的迭代计算模型 | 第30-56页 |
| 3.1 MapReduce中的迭代计算 | 第30-34页 |
| 3.1.1 单源最短路径(SSSP) | 第30-31页 |
| 3.1.2 PageRank | 第31-33页 |
| 3.1.3 MapReduce处理迭代计算存在的问题 | 第33-34页 |
| 3.2 iMapReduce设计与实现 | 第34-41页 |
| 3.2.1 迭代处理 | 第34-36页 |
| 3.2.2 数据管理 | 第36-38页 |
| 3.2.3 异步Map任务 | 第38页 |
| 3.2.4 容错机制 | 第38-39页 |
| 3.2.5 负载均衡 | 第39页 |
| 3.2.6 编程接口API | 第39-41页 |
| 3.3 iMapReduce性能测试 | 第41-47页 |
| 3.3.1 实验设置 | 第41-42页 |
| 3.3.2 本地集群实验 | 第42-44页 |
| 3.3.3 Amazon EC2实验 | 第44-47页 |
| 3.4 扩展iMapReduce功能 | 第47-55页 |
| 3.4.1 Reduce到Map的广播 | 第47-51页 |
| 3.4.2 一次迭代多MapReduce过程 | 第51-53页 |
| 3.4.3 辅助MapReduce过程 | 第53-55页 |
| 3.5 小结 | 第55-56页 |
| 第4章 PrIter-优先级迭代计算模型 | 第56-84页 |
| 4.1 PrIter优先级迭代算法实例和正确性证明 | 第56-65页 |
| 4.1.1 单源最短路径(SSSP) | 第56-57页 |
| 4.1.2 PageRank与Personalized PageRank | 第57-63页 |
| 4.1.3 Adsorption | 第63-64页 |
| 4.1.4 Connected Components | 第64页 |
| 4.1.5 其他优先级迭代算法 | 第64-65页 |
| 4.2 基于内存存储的PrIter | 第65-73页 |
| 4.2.1 迭代处理 | 第65-67页 |
| 4.2.2 状态信息维护 | 第67-68页 |
| 4.2.3 优先级调度 | 第68-70页 |
| 4.2.4 收敛条件检测 | 第70页 |
| 4.2.5 Top-k结果反馈 | 第70-71页 |
| 4.2.6 负载均衡与容错 | 第71页 |
| 4.2.7 编程接口API | 第71-73页 |
| 4.3 基于文件存储的PrIter | 第73-75页 |
| 4.3.1 排序文件 | 第73页 |
| 4.3.2 两阶段更新 | 第73-75页 |
| 4.3.3 扩展API | 第75页 |
| 4.4 优先级队列长度讨论 | 第75-77页 |
| 4.5 PrIter性能测试 | 第77-83页 |
| 4.5.1 实验设置 | 第77-78页 |
| 4.5.2 收敛速度 | 第78-80页 |
| 4.5.3 Top-k结果反馈速度 | 第80-81页 |
| 4.5.4 基于文件存储PrIter的收敛速度 | 第81页 |
| 4.5.5 Amazon大规模实验 | 第81-82页 |
| 4.5.6 最优优先级队列长度 | 第82-83页 |
| 4.6 小结 | 第83-84页 |
| 第5章 Maiter：累加迭代计算模型 | 第84-110页 |
| 5.1 Maiter累加迭代计算推导与证明 | 第84-93页 |
| 5.1.1 同步迭代和异步迭代 | 第84-85页 |
| 5.1.2 累加迭代计算 | 第85-88页 |
| 5.1.3 异步累加迭代模型的收敛性 | 第88-90页 |
| 5.1.4 累加迭代模型效率分析 | 第90-92页 |
| 5.1.5 本地调度策略 | 第92-93页 |
| 5.1.6 累加迭代总结 | 第93页 |
| 5.2 Maiter累加迭代算法实例 | 第93-96页 |
| 5.2.1 单源最短路径(SSSP) | 第93-94页 |
| 5.2.2 Adsorption | 第94页 |
| 5.2.3 线性方程迭代法 | 第94-95页 |
| 5.2.4 其它算法举例 | 第95-96页 |
| 5.3 Maiter原型系统设计与实现 | 第96-102页 |
| 5.3.1 计算节点设计 | 第96-99页 |
| 5.3.2 Master节点设计 | 第99页 |
| 5.3.3 迭代终止条件检测 | 第99-100页 |
| 5.3.4 容错机制 | 第100页 |
| 5.3.5 Maiter用户编程接口API | 第100-102页 |
| 5.4 Maiter性能测试 | 第102-109页 |
| 5.4.1 实验准备 | 第102-104页 |
| 5.4.2 收敛时间 | 第104-106页 |
| 5.4.3 累加迭代效率 | 第106-107页 |
| 5.4.4 通信开销 | 第107-108页 |
| 5.4.5 扩展性能 | 第108-109页 |
| 5.5 小结 | 第109-110页 |
| 第6章 结论 | 第110-112页 |
| 参考文献 | 第112-124页 |
| 致谢 | 第124-126页 |
| 作者攻读博士学位期间发表的学术论文 | 第126页 |
