Content-Based Publish/Subscribe Mechanism and Algorithm Based on Predicate Covering

The content-based publish/subscribe system is adapted to large-scale distributed interaction applications well and widely due to its asynchronous, many-to-many and loosely-coupled communication properties. Efficient matching and routing algorithm and dynamic adaptability are the key issues in the large-scale content-based publish/subscribe systems. Consequently, in order to enhance publish/subscribe systems matching and routing efficiency, the methods, which can reduce subscription scale and routing table sizes at internal content-based routing routers and optimize the structure of subscription expressions, are much feasible. On analysis of publish/subscribe systems related technologies, this paper proposes the concept of predicate relation and a new structure called the predicate relation binary tree (PRBT). PRBT describes the relations among predicates; designs and implements the subscription maintaining, unsubscription and matching algorithm based on the PRBT. By optimizing the structure of the predicate relation and subscription selectivity transmitting strategy, it not only reduces the maintained subscription sizes at each internal router, but also enhances the publish/subscribe systems performance, such as events matching and routing efficiency. In addition, this paper explains some cases of publish/subscribe system and proves the validity of the PRBT-* algorithms properties. The theory analysis and extensive experiments reveal that the method of the predicate covering obtains better results in maintenance overhead of subscription scale, algorithms efficiency and publish/subscribe systems performance.