基于匹配树的发布订阅中快速匹配算法研究

发布时间：2020-05-24 20:44

【摘要】：近年来,随着Internet的飞速发展,分布式计算的应用范围越来越广、使用规模越来越大。在当下,基于分布式计算的信息发布系统得到广泛的应用。传统的信息发布系统具有高耦合的特点,很难适用于大规模、异步、多点通讯的需要。而发布/订阅系统由于其自身具有异步、多点通讯的特点,能够很好的应用到大型互联网信息发布/订阅系统低耦合通讯的需求。发布/订阅系统可分为基于主题、渠道和基于内容的发布/订阅系统,其中基于主题和基于渠道的发布/订阅系统虽然实现简单,但其表达能力有限,不适用于大规模的分布式系统中;而基于内容的发布/订阅系统具有丰富的表达能力、订阅较为灵活,并能对事件进行检索,更适合应用于大规模的分布式系统中。在基于内容的发布/订阅系统中,系统的订阅需要将事件与订阅条件进行匹配,且系统会根据匹配的结果把数据转发给订阅者,当订阅的数量非常大的时候,系统中存在大量的事件和订阅,有可能导致系统大量的阻塞。匹配算法的目的,是负责发布/订阅系统能够高效的、可靠的找到给定事件相匹配的订阅,因此,如何实现一个高效的匹配算法,并构建一个适应于大规模发布者和订阅者并行交互的高效发布/订阅系统,是目前国内外学者研究的重点。目前大多数系统中所采用的方法是通过树形结构对订阅条件建立索引,从而提高了匹配效率,但仍存在匹配时间消耗过大、重复匹配等问题。针对这些问题,本文通过在现有算法基础上进行改进,提出了基于多层约束搜索树的匹配算法,在此基础上,结合倒排索引,构建了适应于大规模发布者和订阅者并行交互的高效匹配方案,主要研究工作如下:1、设计了多层约束搜索树的快速匹配算法—MCTF。基于约束搜索树的算法,虽然相同条件只需匹配一次,但订阅条件与事件匹配时需要遍历整棵搜索树,系统开销仍然较大。针对这样的问题,设计了多层约束搜索树快速匹配算法—MCTF,MCTF通过增加多层约束条件和建立约束之间的覆盖关系,在匹配时当订阅条件满足约束条件时,遍历即终止,不再继续遍历整颗约束搜索树,从而提高了匹配效率,降低了维护开销。实验表明MCTF匹配消耗时间得到了明显的降低。2、设计了基于倒排索引的pub/sub系统的匹配机制—IFMA。多层约束搜索树快速匹配算法MCTF,当一个事件对多个订阅条件时,通过约束覆盖减少了重复匹配;但在多个事件对多个订阅条件时,仍存在较多重复匹配问题。为了解决这个问题,通过在多层约束搜索树基础上引入倒排索引,构建了适应于大规模发布者和订阅者并行交互的高效匹配机制—IFMA,通过倒排索引解析订阅条件和事件间的覆盖关系,减少了订阅条件和事件的匹配次数,进一步提高了匹配效率。
【图文】：

2.1.1 概念为了更好的了解发布/订阅系统，，如图 2-1，显示了一个典型的发布/订阅系统。发布系统是一个信息交互的中间件系统，将信息的生产者和系统的消费者关联在一起，信息的生产者称为发布者(publisher)，信息的发布者称为订阅者(subscriber)，发布负责把信息传递给消息中间件，订阅者只负责向中间件订阅自己感兴趣的信息，如费者不感兴趣，也可以取消事件订阅。信息具体的发布和传递则由发布/订阅系统负其中匹配算法(matcher)是能够准确的找到订阅者事件与发布者事件进行快速的匹配种算法。

所有匹配了的谓词放入到集合 satisfied-preds（初始状态为空 satisfied-preds 中的谓词集合，判断 e 使 S 中哪些订阅满足条件ity=kaifeng) and (temperature<30) 满 足 时 ， 那 么 S=(Cityure<40)必定满足。后面的谓词就不用在进行判断。如图 2-2 所示
【学位授予单位】：河南大学
【学位级别】：硕士
【学位授予年份】：2018
【分类号】：TP301.6

【相似文献】

相关期刊论文 前10条

1 张莉;李甫;吴开腾;;无方向的三角形匹配指纹识别[J];中国图象图形学报;2017年09期

2 万莛;;最大匹配算法研究[J];微型机与应用;2012年08期

3 唐俊;赵晓娟;;一种用于入侵检测系统的可变r匹配算法[J];计算机应用研究;2010年02期

4 刘思含;贾美娟;;树匹配算法在网页分类中的应用[J];电脑学习;2010年04期

5 耿庆宦;吕良双;;产生式系统规则匹配算法研究[J];计算机与现代化;2009年11期

6 何伟方;;DP动态匹配算法实现语音的实时识别[J];浙江丝绸工学院学报;1987年02期

7 徐志才;最大权匹配算法的改进与实现[J];电子科学学刊;1988年04期

8 涂国防;徐佩霞;;运动补偿图象编码中的Block自适应匹配算法[J];遥测遥控;1988年06期

9 姜勤;潘士光;;一种松弛标记体视匹配算法[J];信号处理;1988年04期

10 何伟方,青木由直;DP动态匹配算法实现语音的实时识别[J];数据采集与处理;1989年01期

相关会议论文 前10条

1 杜云峰;许娜;孙爽;许立永;董彦荣;;一种基于排除的串匹配算法[A];2007北京地区高校研究生学术交流会通信与信息技术会议论文集（上册）[C];2008年

2 李晓雷;黄新生;王亦平;徐婉莹;;稳健快速的匹配算法研究[A];'2008系统仿真技术及其应用学术会议论文集[C];2008年

3 吉大纯;李学军;侯金宝;;基于坡的时间规整快速影像匹配算法[A];图像图形技术研究与应用(2010)[C];2010年

4 姚益平;卢锡城;;基于移动相交信息的动态区域匹配算法[A];仿真计算机与软件、仿真方法与建模学术交流会论文集[C];2004年

5 郭莉;刘燕兵;谭建龙;;基于存储压缩的多模式串匹配算法[A];全国第八届计算语言学联合学术会议（JSCL-2005）论文集[C];2005年

6 杨靓;黄巾;卢强;黄士坦;;基于全息相关系数矩阵的匹配算法[A];第十一届全国信号处理学术年会（CCSP-2003）论文集[C];2003年

7 宣琦;吴铁军;;复杂网络间节点匹配算法研究[A];2009年第五届全国网络科学论坛论文集[C];2009年

8 林雪娥;杨鉴;熊艳娇;刘怀憬;李诗心;胡湘兴;;基于拼写规则和最大匹配算法的泰语分词[A];需将论文集名称修改为“第十二届全国人机语音通讯学术会议（NCMMSC2013）论文集[C];2013年

9 郑凯;宫学庆;闫莺;周红福;周傲英;;基于噪声数据流的高效相似匹配算法[A];第二十四届中国数据库学术会议论文集（研究报告篇）[C];2007年

10 徐宝昌;陈哲;;基于神经网络的景像匹配算法研究[A];中国惯性技术学会第五届学术年会论文集[C];2003年

相关重要报纸文章 前1条

1 义川;Web 3.0更有前途？[N];网络世界;2006年

相关博士学位论文 前10条

1 韩雨蓉;水下导航重力匹配算法研究[D];北京理工大学;2017年

2 汪锦岭;面向Internet的发布/订阅系统的关键技术研究[D];中国科学院研究生院（软件研究所）;2005年

3 钱诗友;大规模发布/订阅系统匹配算法研究[D];上海交通大学;2015年

4 杨天龙;面向网络入侵检测的串匹配算法优化[D];哈尔滨工业大学;2014年

5 杨容浩;无控制DEM匹配算法性能比较与改进研究[D];西南交通大学;2012年

6 郭克华;基于微分几何的局部相似目标匹配算法研究[D];南京理工大学;2008年

7 罗楠;图像局部不变特征的匹配算法及应用研究[D];南京理工大学;2015年

8 张树壮;面向网络安全的高性能特征匹配技术研究[D];哈尔滨工业大学;2011年

9 严骏驰;图匹配问题的研究和算法设计[D];上海交通大学;2015年

10 张步阳;半导体芯片封装过程中视觉定位关键技术研究[D];华中科技大学;2016年

相关硕士学位论文 前10条

1 李秉宸;支持交换的近似串匹配算法的研究与实现[D];吉林大学;2019年

2 马晓珂;基于非线性尺度空间的图像特征提取与匹配算法研究[D];河南大学;2019年

3 万季;个性化车辆合乘服务研究[D];郑州大学;2019年

4 吴栋;基于机器学习的多任务多设备匹配算法研究[D];浙江大学;2019年

5 孙琢;多模式车位预约实时匹配算法研究[D];北京邮电大学;2019年

6 杨光;基于FPGA的主动式双目匹配算法研究[D];北京邮电大学;2019年

7 章亚书;不规则边缘图形的快速拼接匹配算法研究[D];哈尔滨理工大学;2019年

8 许文;面向大规模图数据的分布式子图匹配算法研究[D];中北大学;2019年

9 吴晓声;出租车动态共乘匹配优化算法研究[D];长安大学;2018年

10 孔祥雯;面向移动终端的部分指纹匹配算法研究与实现[D];山东大学;2018年

本文编号：2678966