一种面向发布订阅系统的匹配算法

《一种面向发布订阅系统的匹配算法》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、一种面向发布订阅系统的语义匹配算法1.技术领域本发明涉及一种构建在语义Web上，利用RDF图进行语法和事件的转换，而实现的自适应发布订阅系统匹配算法。2.背景技术发布订阅是新一代的网络计算，是一种以大规模、分散控制、动态性、自治性和松耦合为主要特征的分布式计算。已成为分布式计算领域的重要支撑平台，进入人们的生活、工作、科研等领域，是现代计算和应用的研究热点。支持复杂网络的大规模发布/订阅系统，可以预见的应用场景更是包括面向服务的计算、无线传感器网络、移动计算、普适计算、协同环境、企业应用集成等。如图1所示，发布/订阅模型一般由信息生产者、信息消费者和事件通知服务组成。其流程为

2、信息消费者向事件通知服务注册订阅，表达对特定信息的兴趣；信息生产者以事件形式发送信息到事件通知服务，然后事件通知服务路由匹配的事件到相应的信息消费者。发布/订阅系统的核心机制之一就是匹配算法。匹配算法负责高效地找到与给定事件相匹配的所有订阅条件，其设计目标主要包括：匹配的时间效率、匹配的空间效率和订阅维护的效率。数据模型是匹配算法的基础，不同数据模型的发布/订阅系统的匹配算法都不一样。基于Map的发布订阅系统匹配算法，时间复杂度较低,速度很快,但其空间复杂度为指数级。同时,该算法的订阅维护的成本很高,每当客户增加订阅或取消订阅时,系统难以对该搜索树进行修改以反映订阅的变化,而

3、必须要重建搜索树。基于XML的发布/订阅系统，其表达能力比基于Map的系统有了很大的提高。虽然XML具有很强的表达能力,但是订阅者必须预先知道被发布的XML文档所遵从的XMLSchema,才能根据该Schema定义出相应的订阅条件。以上发布订阅系统的事件/订阅匹配属于精确匹配，而语义匹配算法是一种支持模糊匹配的方法，即在没有特定订阅和发布的精确知识,用户发布或订阅采用的是不精确词汇的情况下，发布和订阅之间仍然能够得到有效匹配的算法。1.发明内容本发明的设计目标是降低事件与订阅匹配的时间，提高事件匹配效率，使得随着订阅和发布事件数目的增加，事件匹配效率不会受到严重的影响，系统性

4、能不会恶化。同时，根据匹配服务器的内核体系结构自适应调整匹配算法，充分利用多核技术提高匹配效率。在本系统中，发布者发布以RDF/XML语法表示的事件后，系统把事件转化为RDF图的数据结构。本发明的RDF事件图有三类节点：空节点、类型节点和文本节点。图2展示了一个RDF事件图，它们的具体实现如下描述：空节点没有URI引用或者不需要URI引用，只是作为RDF事件图中的“过渡”节点。空节点在RDF事件图中很常见，因为很多资源可以使用丰富的属性来说明，因此不需要URI引用；同时很多资源本身可能没有URI引用。当RDF事件图表示为三元组时，空节点的表示使用“_:name”形式的标识符，

5、其中name是由系统任意产生的能唯一标识一个空节点的名字。把RDF事件图序列化成XML格式时，使用rdf:nodeID属性来引用空节点，其属性值也为系统任意产生的能唯一标志一个空节点的标识符，但不必以“_:”开头。空节点标识符仅仅是在把RDF图表示成三元组或者RDF/XML的时候，用来表示和区分RDF图中的空节点。类型节点至少有一个rdf:type属性声明它是某个特定类型或类的实例。允许一个类型节点有多个rdf:type属性，说明该类型节点同时是多个类的实例。把RDF事件图表示为XML格式时，RDF/XML提供了一种特殊的简略形式以描述这些类型节点。在简略形式中，rdf:ty

6、pe属性及其值被移去，而节点对应的rdf:Description元素被替换为一个QName（QualifiedName）元素。一个QName包括一个代表命名空间的前缀，其后是一个冒号，然后是该命名空间内的一个词汇名（或者称为局部名）。文本节点，包括普通文本节点和类型文本节点。例如，以“notebook”和“new”为标签的节点是普通文本节点，其隐含的类型为字符串，说明一个拍卖项的物品名称为笔记本，其质量较新。以“2008-2-29^^xsd:date”为标签的节点是类型文本节点，其中上标符号“^^”指出文本的类型为日期型。由于系统把事件表示为RDF图，所以订阅被描述为创建在R

7、DF图语法之上的有向图模式（directedgraphpatterns），图模式规定了RDF事件图的形状以及对某些节点和弧的约束。订阅图模式如图3所示，订阅图中除了rdf:type属性以外，所有其他的属性均以代替。每个空节点被分配一个独一无二的标识符，形如。URI引用和文本分别被表示为和。所有的都满足。每个变量节点的标签均以打头，表示这个节点是个变量，其后紧跟变量名。在系统中，规定变量名必须以为前缀，其后为字符串。字符串由数字、下划线和英文字母组成，不允许出现其他字符。用户在作订阅条件时，可以按照上述规