New Algorithms for Content-Based Publication-Subscription Systems

This paper introduces new algorithms specifically designed for content-based publication-subscription systems. These algorithms can be used to determine multicast groups with as much commonality as possible, based on the totality of subscribers' interests. The algorithms are based on concepts borrowed from the literature on spatial databases and clustering. These algorithms perform well in the context of highly heterogeneous subscriptions, and they also scale well. Based on concepts borrowed from the spatial database literature, we develop an algorithm to match publications to subscribers in real-time. We also investigate the benefits of dynamically determining whether to unicast, multicast or broadcast information about the events over the network to the matched subscribers. We call this the distribution method problem. Some of these same concepts can be applied to match publications to subscribers in real-time, and also to determine dynamically whether to unicast, multicast or broadcast information about the events over the network to the matched subscribers. We demonstrate the quality of our algorithms via a number of realistic simulation experiments.