Minimizing the subscription aggregation cost in the content-based pub/sub system

Considering the heterogeneous subscriptions of the subscribers in the content-based publish/subscribe (pub/sub) system, the subscription aggregation technique is used to optimize the system performance, e.g., reducing the routing table, simplifying the matching procedure. However, introducing this technique also has disadvantages. If some subscribers leave the network, the brokers which aggregate subscriptions should re-configure the subscription aggregation strategy with its descendants. During this period false-positive publications, which are no longer needed by subscribers, are still propagated into the network. Therefore, it becomes paramount to examine the issue of how to conserve network resources through subscription aggregation, while simultaneously minimizing the false positive publication propagation. In this paper, we first prove the above problem is NP-hard. Then, we provide the dynamic programming approach when the re-configuration delay can be regarded as constant time. In the general case, we propose a greedy algorithm, and the corresponding performance bound is analyzed. Finally, we propose an overlay construction scheme to further fit the subscription aggregation. Extensive experimental results show that proposed algorithms achieve a good performance.