在线社交网络分布式存储的数据分配算法研究

发布时间：2017-07-04 14:26

  本文关键词：在线社交网络分布式存储的数据分配算法研究

  更多相关文章： 社交网络 分布式存储 图划分 动态划分复制 存储受限

【摘要】：自诞生之日起，在线社交网络一直保持着快速成长的势头，吸引了大量用户和开发者、研究学者。过去十年中，社交网络的规模呈几何式爆炸增长。随着用户数的进一步增加，单一服务器已经不能满足当代社交网络的整体需求，大部分社交网络的数据信息开始分布式存储在服务器集群上。 这些集群节点相互之间的通信通过网络实现，往往需要较高的通信成本和较长的访问时间。大量的远程访问会导致通信网络的拥塞，成为整个系统的瓶颈，并且大大延迟访问时间，降低用户体验。如何在有限的、分布的存储空间内高性能存储和访问用户数据具有现实意义。 现有研究表明，社交网络中大部分交互行为发生在少部分用户之间，同时，大部分用户只与少数好友交流，具有明显的社团结构。通过对社交网络图合理划分，减少不同划分间的割边能够有效减少网络通信。然而图划分问题是NP完全问题，不存在线性时间内的最优解。 基于以上观察，，一些研究学者根据社交网络的结构特性对现有的图划分算法作出改进，具有一定成效。在研究现有社交网络图划分算法后，本文提出一种基于用户交互行为的动态划分复制算法，利用用户之间的朋友关系和评论行为描述社交网络的结构，周期性划分复制用户数据，从而提高本地访问率，降低网络负载。通过真实数据集验证，该算法相比随机划分和复制算法能够提升本地访问率，降低访问延迟。
【关键词】：社交网络 分布式存储 图划分 动态划分复制 存储受限
【学位授予单位】：上海交通大学
【学位级别】：硕士
【学位授予年份】：2014
【分类号】：TP333;O157.5
【目录】：

• 摘要3-5
• ABSTRACT5-7
• 目录7-10
• 图录10-11
• 表录11-12
• 第一章 绪论12-18
• 1.1 研究背景和意义12-13
• 1.2 国内外研究现状13-15
• 1.2.1 GFS 分布式文件系统和 Bigtable 分布式存储系统13
• 1.2.2 Cassandra 分散式结构化数据存储系统13-14
• 1.2.3 SPAR 分配复制算法14
• 1.2.4 WEPAR 分配复制算法14-15
• 1.3 目前存在的问题15-17
• 1.3.1 社团结构15-16
• 1.3.2 写操作和存储限制16-17
• 1.3.3 动态操作17
• 1.4 研究内容及工作17
• 1.5 论文内容17-18
• 第二章 相关理论技术18-32
• 2.1 图划分的相关定义18-27
• 2.1.1 图划分的相关定义18
• 2.1.2 均衡图划分的困难性18-23
• 2.1.3 图划分的启发式算法23-27
• 2.2 社交网络27-30
• 2.2.1 社交网络的定义28
• 2.2.2 社交网络的拓扑特性28-30
• 2.3 分布式数据存储30-31
• 2.4 本章小结31-32
• 第三章 算法模型及定义32-41
• 3.1 相关符号及定义32-34
• 3.1.1 主本及副本32
• 3.1.2 读操作写操作32
• 3.1.3 关系社交图32-33
• 3.1.4 交互社交图33
• 3.1.5 衰退因子33
• 3.1.6 社交网络的图划分33-34
• 3.1.7 读权重34
• 3.1.8 写权重34
• 3.2 需求分析34-35
• 3.2.1 有限的存储容量34
• 3.2.2 最小化跨节点操作34
• 3.2.3 负载平衡34-35
• 3.2.4 高效并且稳定的在线操作35
• 3.3 问题抽象35-36
• 3.3.1 最小化跨节点写操作35-36
• 3.3.2 最小化跨节点读操作36
• 3.4 动态划分复制算法36-40
• 3.4.1 算法描述36-37
• 3.4.2 触发事件37-40
• 3.4.3 算法时间复杂度分析40
• 3.5 本章小结40-41
• 第四章 社交网络的数据获取41-48
• 4.1 实验流程41-42
• 4.2 数据获取42-45
• 4.2.1 网络爬虫42-44
• 4.2.2 人人网开放平台 API44-45
• 4.2.3 数据爬取45
• 4.3 数据清理及归约45-46
• 4.4 网络结构46-47
• 4.5 本章小结47-48
• 第五章 动态划分复制性能分析48-60
• 5.1 SPAR48-51
• 5.1.1 SPAR 设计思路48-49
• 5.1.2 SPAR 实验效果49-50
• 5.1.3 SPAR 的指导意义50-51
• 5.2 实验设计51-53
• 5.2.1 数据分配51
• 5.2.2 实验流程51
• 5.2.3 UML 图51-52
• 5.2.4 评价指标52-53
• 5.2.5 对比方法53
• 5.3 实验结果53-59
• 5.3.1 本地写率53-54
• 5.3.2 主本交换率54-55
• 5.3.3 本地读率55-57
• 5.3.4 响应时间57-59
• 5.4 本章小结59-60
• 第六章 结束语60-62
• 6.1 论文主要工作60-61
• 6.2 未来工作展望61-62
• 参考文献62-65
• 致谢65-66
• 攻读硕士学位期间已发表或录用的论文66-68

【参考文献】

中国期刊全文数据库 前1条

1 张奎,陈大岳;可满足性(SAT)问题的概率研究[J];数学进展;2001年03期

本文编号：518167