论文部分内容阅读
发布/订阅系统是一个满足信息的生产者和消费者互动的分布式中间件系统,它的出现改变了人们处理信息的方式。发布/订阅系统的主要设计目标包括:表达能力、高效性、可靠性和扩展性等方面。一个典型的发布/订阅系统包括拓扑结构、数据模型、匹配算法和路由算法等,而本文中我们重点讨论了作为其关键技术的匹配算法的实现细节。发布/订阅系统的匹配算法负责高效地找到与给定的事件消息相匹配的所有订阅谓词对应的订阅,进而由路由算法通知订阅者,其设计目标主要包括:匹配的时间效率、匹配的空间效率和订阅维护的效率。
发布/订阅系统的匹配算法总是依赖于特定的数据模型,在本文中我们首先介绍了基于内容的发布/订阅系统的数据模型,与原有的一些使用决策树或有限自动机的过滤算法不同的是,我们使用了多维索引来处理事件消息的匹配问题。特别的我们使用了UB树索引,它的特点在于用来维护索引的代价非常小。
其次我们介绍了基于维转换的映射方法,并结合我们的对称的数据模型提出了适用于对称的发布/订阅系统的匹配算法,所谓维转换的方法不过是将N维上的区间映射成2N维空间上的点,藉此来使用点的包含查询替代空间的相交查询,从而提高匹配效率。接下来我们又详细介绍了对于原有的Counting算法的在对称情况下的改进,最后我们进行了实验分析,来比较这些我们设计出来的方法的可行性,实验证明,这些方法对于维数和数据量的扩展性是线性的,并且除UB-树索引方法外,在对称情况下的过滤性能基本没有变化;而谓词比率和选择度的变化对于算法的性能影响很小,从而我们的方案可以高效的适应发布/订阅系统的需求。