Efficient Matching Algorithm for Content-based Publish/Subscribe Systems with Compound Predicates

ABSTRACT

Publish/Subscribe paradigm has been widely used in large-scale distributed systems, as well as in information-centric networks (ICNs) due to its properties of asynchronous, loosely-coupled and many-to-many communications. This paper focuses on matching algorithms which support compound predicates for content-based Publish/Subscribe systems. By using index structures and transforming the complex subscription expressions, our algorithms can not only find proper recipients for emerging events, but also identify matched events for new subscription requests. Theoretical analysis and experimental results show that transforming the subscription expression by appropriate methods can enhance matching efficiency in terms of event and subscription matching time.

References

1. Fotiou N, Trossen D, Polyzos G C. Illustrating a publish-subscribe Internet architecture{J}. Tele- communication Systems, 2012, 51(4):233--245.
2. Akbar M S, Khaliq K A, Bin Rais R N, et al. Information-Centric Networks:Categorizations, challenges, and classifications{C}. Wireless and Optical Communication Conference. IEEE, 2014: 1--5.
3. Mühl G, Parzyjegla H, Prellwitz M. Analyzing content-based publish/subscribe systems{C}. Proceedings of the 9th ACM International Conference on Distributed Event-Based Systems. ACM, 2015: 128--139.
4. Whang S E, Garcia-Molina H, Brower C, et al. Indexing boolean expressions{J}. Proceedings of the VLDB Endowment, 2009, 2(1): 37--48.
5. Kazemzadeh R S, Jacobsen H A. Opportunistic multipath forwarding in content-based publish/subscribe overlays{C}. Proceedings of the 13th International Middleware Conference. 2012: 249--270.
6. Campailla A, Chaki S, Clarke E, et al. Efficient Filtering in Publish-Subscribe Systems using Binary Decision Diagrams {C}. International Conference on Software Engineering. 2001: 443-- 452.
7. Li G, Hou S, Jacobsen H A. A unified approach to routing, covering and merging in publish/subscribe systems based on modified binary decision diagrams{C}. Distributed Computing Systems, 2005.
8. Ma X, Wang Y, Pei X, et al. A general scalable and elastic matching service for content-based publish/subscribe systems{J}. Concurrency & Computation Practice & Experience, 2014, 27(1): 94--118.
9. Sadoghi M, Jacobsen H A. BE-Tree: An index structure to efficiently match Boolean expressions over high dimensional discrete space{C}. Proceedings of the ACM SIGMOD International Conference on Management of Data. 2011: 637--648.
10. Jiafeng Hu, Reynold Cheng, Dingming Wu, et al. Efficient Top-k, Subscription Matching for Location-Aware Publish/Subscribe{M}. Advances in Spatial and Temporal Databases. Springer International Publishing, 2015: 333-- 351.
11. Yu M, Li G, Wang T, et al. Efficient Filtering Algorithms for Location-Aware Publish/Subscribe{J}. IEEE Transactions on Knowledge & Data Engineering, 2015, 27(4): 950--963.