同构发布订阅系统的系统最优化与并行查询算法的研究与实现

《同构发布订阅系统的系统最优化与并行查询算法的研究与实现》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、万方数据分类号UDC密级学位论文同构发布／订阅系统的系统最优化与并行查询算法的研究与实现作者姓名：指导教师：申请学位级别：学科专业名称：论文提交日期：学位授予日期：评阅入：刘增兰王波涛教授东北大学信息科学与工程学院硕士学科类别：工学计算机软件与理论2014年6月论文答辩日期：2014年6月21日2014年7月答辩委员会主席：乔建忠教授吴刚副教授张大波教授东北大学2014年6月万方数据AThesisinComputerSoftwareandTheoryResearchandImplementationofSystemOptimazationandPar

2、allelQueryAlgorithms。。rHegSymmetricPublish／SubscribelorHomoReneousnblish／SUbscribeSystemByLiuZenglanSupervisor：ProfessorWangBomoNortheasternUniversityJune2014万方数据独创性声明本人声明，所呈交的学位论文是在导师的指导下完成的。论文中取得的研究成果除加以标注和致谢的地方外，不包含其他人己经发表或撰写过的研究成果，也不包括本人为获得其他学位而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均己

3、在论文中作了明确的说明并表示谢意。学位论文作者签名：交心璃兰日期：2pI4．石．聊学位论文版权使用授权书本学位论文作者和指导教师完全了解东北大学有关保留、使用学位论文的规定：即学校有权保留并向国家有关部门或机构送交论文的复印件和磁盘，允许论文被查阅和借阅。本人同意东北大学可以将学位论文的全部或部分内容编入有关数据库进行检索、交流。作者和导师同意网上交流的时间为作者获得学位后：半年口一年口一年半口两年∥学位论文作者签名：刹鸺兰签字日期：如l印．丘．24导师签名：王认殳厨签字日期：2u14'·莎．2铲万方数据东北大学硕士学位论文摘要同构发布／订阅系统的系

4、统最优化和并行查询算法的研究与实现摘要发布／订阅系统是一种提供给信息的生产者和消费者互动平台的分布式中间件系统，其中同构发布／订阅系统的一类应用是易物服务、物品交换等，该系统的目的是使尽可能多的用户参与匹配、提高系统的收益能力，因此逐渐获得了电商的关注。近年来，云计算作为计算平台中一种新型模型出现，覆盖了多数计算领域。云计算的兴起为高效、大规模计算平台的产生提供了可能性。如何在发布／订阅系统中使尽可能多的用户参与匹配并且使系统具有良好的扩展性是发布／订阅系统的追求目标，也是发布／订阅系统的关键技术。本文主要工作包含两部分，第一是针对系统最优化问题设计

5、出高效的算法，找出尽可能多的订阅用户成功参与匹配，另一工作是利用云计算平台的计算资源和技术，设计出具有良好扩展性的发布／订阅系统。针对提高系统中参与匹配用户数目的系统最优化问题，本文应用了兼顾用户满意度的贪心算法和启发式算法。现有的发布／订阅相关的研究中，针对系统最优化问题的研究相对较少。己知在环匹配长度大于等于3的前提下，系统最优化问题是N-PC问题，为系统找到一个近似最优解是本文的一个研究重点。而本文主要从系统收益和用户满意度两个角度出发，应用了兼顾两者的贪心算法和启发式算法。其中，贪心算法从考虑用户满意度的角度获取系统近似最优解；而启发式算法中

6、，针对长度为3的环匹配提出了两种归约规则，通过归约规则逐步降低问题规模，并最终获取系统近似最优解。实验结果证明，两种算法执行时间基本相同，启发式算法的结果集中包含的订阅数比贪心算法结果集中订阅数多出9％到24％。针对发布／订阅系统扩展性这一问题，本文提出了基于TwitterStorm的发布／订阅并行框架。目前虽然存在部分有关于云计算和发布／订阅相结合的研究工作，还没有关于实时处理系统TwitterStorm与发布／订阅的整合工作。本文提出的基于TwitterStorm的发布／订阅框架的目的是在大规模数据下，使事件与订阅进行快速的匹配。首先，对于云环境

7、下缺少有效的索引结构，本文针对订阅数据建立基于HBase存储的R-树索引，通过维转换和空间填充技术，可以高效地进行事件的查询匹配。其次，针对事件匹配工作，本文设计框架及算法采用并行查询模式，有效地提高了事件的匹配速度，从而提高系统的吞吐量。最后，通过实验分析，索引结构的存在大大减少数据查询时间，并证明了并行框架的扩展性。．TT．万方数据东北大学硕士学位论文摘要关键词：发布／订阅；系统最优化；并行匹配；多维索引；TwitterStorm．．III．．万方数据东北大学硕士学位论文AbstractResearchandImplementationofSys

8、temOptimizationandParallelQueryAlgorithmsforHomogeneou