Clustering Algorithms for Content-Based Publication-Subscription Systems

We consider efficient communication schemes based on both network-supported and application-level multicast techniques for content-based publication-subscription systems We show that the communication costs depend heavily on the network con&urations, distribution of publication and subsctiptions. We propose to use clustering algorithms to form multicast groups. We devise new algorithms and adapt partitional data clustering algorithms for these content-basedpublication-subscriprion systems. These algorithms can be used to determine multicast groups with
as much commonality as possible, based on the totality of subscribers’ interests. These algotithms perform well in the context of highly heterogeneous subscriptions, and they also scale well. An efficiency of 60% to 80% with respect to the
ideal solution can be achieved with a small number of multicast groups (less than 100 groups in our experiments). 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 matchedsubscribers. We demonstrate the quality of our algorithms via a set of simulation experiments.