基于交互局部性的在线社交网络数据放置策略研究

《基于交互局部性的在线社交网络数据放置策略研究》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、分类号学号M201072437学校代码10487密级硕士学位论文基于交互局部性的在线社交网络数据放置策略研究学位申请人：吴少良学科专业：计算机系统结构指导教师：陈汉华副教授答辩日期：2013年5月29日AThesisSubmittedinPartialFulfillmentoftheRequirementsfortheDegreeofMasterofEngineeringMinimizingInter-serverCommunicationsbyExploitingSelf-similarityinOnlineSocialNetw

2、orksCandidate：ShaoLiangWuMajor：ComputerArchitectureSupervisor：Prof.HanhuaChenHuazhongUniversityofScienceandTechnologyWuhan430074,P.R.ChinaMay,2013独创性声明本人声明所呈交的学位论文是我个人在导师指导下进行的研究工作及取得的研究成果。尽我所知，除文中已经标明引用的内容外，本论文不包含任何其他个人或集体已经发表或撰写过的研究成果。对本文的研究做出贡献的个人和集体，均已在文中以明确方式标明。本

3、人完全意识到，本声明的法律结果由本人承担。学位论文作者签名：日期：年月日学位论文版权使用授权书本学位论文作者完全了解学校有关保留、使用学位论文的规定，即：学校有权保留并向国家有关部门或机构送交论文的复印件和电子版，允许论文被查阅和借阅。本人授权华中科技大学可以将本学位论文的全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或扫描等复制手段保存和汇编本学位论文。本论文属于保密□，在_____年解密后适用本授权书。不保密□。（请在以上方框内打“√”）学位论文作者签名：指导教师签名：日期：年月日日期：年月日华中科技大学硕士学位论文

4、摘要随着在线社交网络飞速发展，数以亿计的用户开始在互联网上使用在线社交网络进行沟通交流。如今大型在线社交网络系统一般使用key-value的方式对用户数据进行存储，这种存储方式一般将用户随机划分到不同的服务器中。随机划分的方法使系统具有很好的可扩展性，但由于在线社交网络中用户频繁交互，随机划分的方法会造成大量的服务器间通信开销。如何将在线社交网络中的用户数据进行合理的划分以减少服务器间的通信开销已成为在线社交网络中迫切需要研究的问题。通过对在线社交网络中的实际数据进行分析，一种全新的在线社交网络数据放置策略被提出。这种数据放置策略

5、能够大大降低服务器间的通信开销。在线社交网络中用户间的交互是造成服务器间通信的主要原因。如何将在线社交网络中频繁交互的用户放入同一个服务器中是解决问题的关键。分析发现，在线社交网络中用户间交互网络的社区结构存在自相似特征。利用这种结构，一种高效的数据划分方法被提出。具有自相似特征的结构耗费的能量能够达到最少，因此所提出的方法在理论上能够使服务器间通信量达到最低。然而在线社交网络中用户间的交互随时间不断变化，因此使用一种动态调整方法对用户交互的动态变化进行处理才能保证在线社交网络中服务器间的通信开销一直保持在较低水平。通过对含有10

6、00万个用户和2400万个交互事件的Facebook实际数据进行分析，发现Facebook交互网络的社区结构存在自相似特征。为了对所提出方法进行评价，一个完备的模拟实验被构建出来。通过使用Facebook系统中真实数据进行测试，发现所提出的方法使在线社交网络中的服务器间通信量和通信延迟都降低了75%。关键字：在线社交网络，服务器间通信，交互网络，自相似性I华中科技大学硕士学位论文AbstractSincetherapiddevelopmentofonlinesocialnetworks(OSNs),hundredsofmillio

7、nsofusershavestartedtouseOSNtocommunicatewithfriendsontheinternet.StoragesystemsusedbypopularOSNsystemsoftenrelyonkey-valuestores,whererandomlypartitioningthedataofusersamongserversacrossthedatacentersisthedefactostandard.Althoughtherandompartitionschemeishighlyscalab

8、leforhostingalargenumberofusers,itleadstocostlyinter-servercommunicationsindatacentersduetothecomplexityofinterconnectionand