基于内容发布/订阅系统中的事件匹配和路由算法

基于内容的发布/订阅是一种新型的通信方式。在这样的系统中,事件通知的发布者不必给消息明确的目的地址,消息的目的地址由匹配订阅者申明的选择谓词的消息内容确定。因此,订阅与事件的匹配,路由成为基于内容发布订阅系统中面临的关键问题。详细分析了几个有影响的基于内容发布/订阅系统原型中使用的事件匹配和路由算法,和算法的特点和适用范围     

基于黄金分割法的订阅间隔树区间划分算法设计

在发布订阅系统中,匹配算法的主要作用是负责高效地找到与给定的服务相匹配的所有订阅条件,算法的匹配速度及转发开销是影响发布订阅系统整体性能的一个关键因素.针对采用订阅间隔树模型的发布订阅系统,提出了一种基于黄金分割法的订阅间隔划分算法(IDAGSM).该方法利用匹配树原理,把多个订阅组织成一个树形索引结构,即订阅间隔树,利用黄金分割法对区间进行划分,并对订阅间隔树进行深度优先遍历,通过从查找匹配时间与构建订阅间隔树的深度与二分法进行实验对比,证明该方法能使事件与订阅之间的匹配效率得到一定的提高,并有效地减少转发开销.     

基于混合索引树的空间文本匹配算法

针对空间文本对象流和订阅流的匹配,采用一种混合索引树来组织数据对象,包括多叉树空间索引、谓词索引和倒排文件三个部分,其中多叉树空间索引用于空间区域管理,谓词索引和倒排文件用于订阅谓词管理.在此基础上,提出了谓词索引建立算法、空间文本对象与倒排项匹配算法和混合索引树检索算法.与基于空间网格加倒排文件的检索方法进行了对比实验,结果表明:所提出的算法提高了用户的检索效率,并验证了其有效性.     

基于内容的发布/订阅模型中高效的匹配算法

高效的匹配算法是大规模基于内容的发布订阅系统所要研究的热点问题之一.提出了一种快速有效的算法,算法根据逻辑表达式的特点,对所有订阅按照优先级进行预处理操作,使相同属性的比较次数小于等于1次,从而降低了匹配的代价.适合应用于大规模分布式基于内容的发布订阅系统中.     

基于内容的发布/订阅模糊匹配路由过滤器

基于模糊匹配的优化思想,设计基于内容的发布／订阅模糊匹配路由过滤器,对基于覆盖路由的模糊匹配过滤器的构造原理、模糊函数的构造和匹配规则、属性的隶属度函数和匹配阀值进行研究,并给出模糊匹配过滤器的算法描述和实验结果。研究结果表明:采用模糊匹配算法对属性进行过滤,可以快速找到符合订阅要求的发布事件消息,有效地提高系统性能。     

基于位置的发布/订阅索引结构

为了使空间文本数据的处理更加快捷准确,针对基于位置的发布/订阅提出了将R-tree与布尔表达式有效结合的索引结构TR-tree.TR-tree主要由文本索引与空间索引组成,其中文本索引根据订阅中谓词的数量和不同的关键谓词将空间文本数据进行订阅分组和谓词分组.文本索引中使用了操作符列表储存谓词,以达到避免重复储存谓词、减少内存使用的目的.空间索引根据关键谓词与谓词数量构建不同的R-tree,增强了空间修剪的性能.实验结果表明TR-tree具有高效的匹配能力与较好的内存管理性能.     

基于CPN的pub/sub系统中事件订阅的分析

提出了一种基于着色petri网（CPN）理论的pub／sub系统协议分析方法,并就一种p2p网络之上的pub／sub系统协议,用CPN对系统中的订阅事件的消息处理进行形式化描述和建模。用CPN Tools对模型进行模拟仿真,通过对模型的可达图进行分析,证明了协议具有活性、可达性和有界性等,验证了协议的可用性。     

基于拼音索引的中文模糊匹配算法

主流商业搜索引擎主要基于关键词精确匹配技术。为提高在用户的输入错误时的检索效率,提出了有索引的汉语模糊匹配算法。该算法采用汉字、拼音和拼音改良的编辑距离这3种汉字相似程度的不同度量方式,对用户查询进行扩展,将模糊匹配转化为多个精确匹配,对精确匹配的结果按与查询串的相似程度进行排序。在实验中,将该方法应用于网页文本语料库中。在使用基于拼音改良的编辑距离度量方式时,在时间和空间复杂度增长不大的情况下,该方法取得了60.42%的准确率与50.41%召回率。     

基于移动平台的异构并行字符串匹配算法

针对信息处理中常见的字符串匹配问题,通过对经典的Brute Force算法和KnuthMorris-Pratt算法进行分析,根据GPU异构并行计算任务的分配特性,设计一种针对Knuth-Morris-Pratt算法的数据重叠划分并行方案,并提出一种基于移动平台的异构并行字符串匹配算法KMP_MOP.在PowerVR移动平台环境下使用千万级长度的字符串数据对算法的性能进行测试,同时对算法在其他平台的执行情况进行比较,验证了并行算法的性能可移植性.实验结果表明,KMP_MOP算法能充分利用移动平台中的GPU性能,有效提高具有GPU的移动平台设备的字符串匹配效率.     

一种改进的基于区域划分的综合索引方法

为解决现有基于区域划分的自动制图综合索引方法中层次划分简单固定和没有考虑综合数据的空间分布特点等问题,提出了一种改进的基于区域划分的综合索引方法。该方法的不同之处在于对数据进行了空间聚类和基于缓冲区的冲突探测,将需要综合的空间数据分为四个层次：第一层为整个综合区域;第二层为进行聚类和冲突探测后的区域划分;第三层是利用境界、水系和道路网分割所得的区域划分;第四层是单个目标。实验表明,该方法扩展了索引层次,有效地弥补了原方法的缺点。     

基于XML的发布/订阅系统的评测算法研究

提出了在XML数据流上有效评测XPath订阅的技术和方法。根据XPath层次结构的语义特征, 设计了基于非确定有限状态自动机的动态索引结构, 使得具有相同前缀的XPath查询可以共享存储索引的空间和共享查找索引的计算。基于栈的新评测算法设计了高速缓存软件预取技术, 以处理评测过程中频繁出现的cache缺项问题。系统取得了很高的性能, 通过全面的实验表明, 系统可以有效处理超过百万以上XPath查询的负载量。     

基于机群系统的并行划分聚类算法

从划分聚类要求的时间和空间上看，传统的串行算法已很难适应海量的数据，有必要研发高性能、可扩展的并行算法来解决这一问题，基于一些主要的并行划分聚类算法所存在的问题，提出了在机群系统上采取数据并行策略设计的并行划分聚类算法思想。     

中文切分词典的最大匹配索引法

提高自然语言词典的检索速度是提高计算机处理系统速度的重要途径,考虑到汉语语词的切分中使用词典的特点,参考“Ｔｒｉｅ索引”方法,提出了一种多层次的词典索引结构和最大匹配待渣汉字串的检索方法,使用这种方法,切分系统每次都能查到所需,大大提高了切分的工作效率,在查一个登录的词时,也较一般的方法快。     

网络拓扑图多层k划分轻点匹配模式研究

鉴于大规模网络进行图划分的需要,针对网络拓扑结构特点提出了轻点匹配算法,应用于多层k划分模式中.通过采用轻点匹配算法对网络模拟图进行划分试验,并与重边匹配算法和有选择的重边匹配算法进行对比分析,证明该法具有较小的边切割和很好的平衡性.     

基于消息侦听的高效快速发布/订阅路由算法

针对MANET环境中密度驱动的发布/订阅路由算法在相邻Hill间转发消息过程中存在较大时延和冗余控制开销问题,提出一种消息侦听的高效快速发布/订阅路由算法(FEPML).该算法通过边缘节点侦听机制,快速构建相邻Hill之间的双向传输路径,提高内容匹配的效率;利用心跳消息转发时的捎带信息,避免向边缘状态的Hill转发消息,减少绕路;同时压缩消息头部字段,减少冗余开销.仿真结果显示:与现有的典型相关算法相比,FEPML可以有效地降低数据传输开销,快速实现发布消息和订阅节点的匹配,降低平均端到端时延.     

空间关键字任务匹配算法

互联网的发展带动了电商等应用的普及,产生了大量具有临时匹配性质的服务。这些服务需要考虑任务的类型与人员具备技能的匹配,同时最小化匹配对象间的路程开销。针对以上实际需求,提出了空间关键字任务匹配问题,给定具有空间位置及关键字的任务集与成员集,在所有任务均可完成的前提下,使所有匹配的任务与成员的距离之和最小。所提出的问题考虑了任务由不同的关键字表示,由于任务和成员数量的海量性及关键字的多样性使得高效求解高质量的匹配结果成为挑战。该文提出了k近邻增量优化策略,引入关键字设计了k近邻空间关键字任务匹配算法,提高了任务匹配质量;提出了基于空间划分的分组优化匹配算法,以适应海量数据的任务匹配情况。针对真实数据集进行了充分测试,验证了算法的有效性。     

发布/订阅系统语义Web匹配算法

将语义Web技术引入发布/订阅系统中,结合领域本体,提出一种智能匹配算法.以双索引哈希邻接表,结合谓词表、变量约束表和变量类型表作为订阅条件RDF图模式的数据结构,采用元语句级匹配计数方法,使原子订阅条件仅匹配一次,原子订阅条件间"与关系"的顺序匹配.定量和定性分析了算法的时间和空间复杂度.实验结果比较表明,所设计的智能匹配算法具有较高的订阅匹配效率,适合于大规模发布/订阅系统.     

LTE中基于ASIC速率匹配算法的并行设计

本文给出一种基于ASIC的LTE速率匹配并行设计方案。速率匹配是LTE物理层比特级处理流程中重要的一步,LTE的高峰值速率要求其并行处理。已有的并行设计方案需要用到大量的小容量RAM,用于ASIC时会增加片上存储的面积。本文深入分析速率匹配算法的特性,通过优化设计,只用了少量的RAM实现了8bit并行处理。在Synopsys VCS平台仿真并用Synopsys DC工具综合,结果表明本方案性能达到要求,而存储面积相比现有方案[5]大概只有其15%。     

基于并行特征匹配的车牌定位与识别算法

针对智能交通系统中车牌定位速度慢,信息识别准确度低的问题,提出了一种高性能的车牌定位及字符识别算法.进行车牌图像预处理,在彩色图像中搜索边缘密度快速突起的矩形域,在搜索后的矩形区域内采集相似走向的双边曲线,筛选出双边走向具有突出相似特征的区域,以此定位出包含字符的真实车牌区域,通过改进的神经网络模型进行多模板同位权值匹配,将待匹配模板逐层剔除,接着进行相似模板的异位权值匹配,准确识别出车牌图像里的字符信息.该算法抓住了车牌的矩形特征和字符具有的并行双边走向的重要特点,利用新型的同异位并行模板剔除方法,提高了车牌定位的速度和字符识别的准确度.     

基于等价类划分的并行频繁闭项集挖掘算法

针对海量数据的关联规则挖掘问题,提出了一种有效的基于等价类划分的并行频繁闭项集挖掘算法.该算法在MapReduce框架下,通过等价类的产生与划分、数据集的分配、异步频繁闭项集挖掘和汇总等步骤,不但较好地解决了多节点间的负载均衡问题,而且易于获得可靠的频繁闭项集.实验表明,该算法能有效克服传统算法挖掘效率低、冗余规则较多的缺点,整体上具有较高的性能.