A DATA STRUCTURE FOR CONTENT-BASED ROUTING

摘要

In this paper, we formally define a useful data structure for content-based routing and event delivery. The poset (partially ordered set)-derived forest data structure is induced by the partial order created by the covering relation between event filters. Two extensions of the basic data structure are discussed: colored forests and the weakly merging forest. We give performance figures for the data structure using a workload generator and compare it with the filters poset structure. The experimental results indicate that the poset-derived forest performs considerably better than directed acyclic graph-based structures. The presented algorithms and mechanisms generalize to any covering relations and are thus applicable for different filtering languages.