SCIENCE CHINA Information Sciences, Volume 59, Issue 2: 022315(2016) https://doi.org/10.1007/s11432-015-5500-x

Toward high efficiency for content-based multi-attribute event matching via hybrid methods

More info
  • ReceivedJul 7, 2015
  • AcceptedSep 30, 2015
  • PublishedJan 5, 2016


Event matching is a core in decoupled end-to-end communications, which are extensively applied to various areas. Event matching seeks the subscriptions that match a given event from a subscription set, however, this work becomes increasingly complicated in content-based multi-attribute scenarios, where events and subscriptions are formed in content, and described by multiple attributes. In addition, large-scale systems are easier to suffer from severe degradation in event matching performance. To this end, this paper presents a high-efficiency content-based multi-attribute event matching algorithm, called HEM (hybrid event matching), which is hybridized by 2 different methods. In HEM, the matching on each single attribute (called single-attribute matching) is processed by a triangle-based matching method or a direct matching method dynamically. All single-attribute matchings are sorted via a fast near-optimal algorithm, and each of them is carried out sequentially. In this manner, the searching space of event matching shrinks gradually, so that the searching performance is boosted along with the process of event matching. Experiments are conducted to evaluate HEM comprehensively, where it is observed that HEM outperforms 3 state-of-the-art counterparts (TAMA, H-TREE and REIN) in main criteria, such as event matching time, insertion time and deletion time. Moreover, the gap of performance between HEM and the counterparts enlarges with the increase of system scale.


[1] Eugster P T, Felber P A, Guerraoui R, et al. ACM Comput Surv, 2003, 35: 114-131 CrossRef Google Scholar

[2] Ma X K, Wang Y J, Sun W D. Sci China Inf Sci, 2014, 57: 052103-131 Google Scholar

[3] Muhl G, Ulbrich A, Herrman K. IEEE Internet Comput, 2004, 8: 46-53 Google Scholar

[4] Guinard D, Trifa V, Karnouskos S, et al. IEEE Trans Serv Comput, 2010, 3: 223-235 CrossRef Google Scholar

[5] Cao F, Singh J~P. Efficient event routing in content-based publish-subscribe service networks. In: 23rd Annual Joint Conference of the IEEE Computer and Communications Societies, Hong Kong, 2004, 2: 929--940. Google Scholar

[6] Jayaram K, Jayalath C, Eugster P. Parametric subscriptions for content-based publish/subscribe networks. In: Middleware. Berlin: Springer, 2010. 128--147. Google Scholar

[7] Kr{\"u}gel C, Toth T, Kerer C. Decentralized event correlation for intrusion detection. In: Information Security and Cryptology-ICISC 2001. Berlin: Springer, 2002. 114--131. Google Scholar

[8] Layer R~M, Skadron K, Robins G, et al. Bioinformatics, 2013, 29: 1-7 CrossRef Google Scholar

[9] Zhao Y, Wu J. Towards approximate event processing in a large-scale content-based network. In: 31st International Conference on Distributed Computing System (ICDCS), Minneapolis, 2011. 790--799. Google Scholar

[10] Qian S, Cao J, Zhu Y, et al. IEEE Trans Parall Distr Syst, 2014, 99: 1-11 Google Scholar

[11] Qian S, Cao J, Zhu Y, et al. Rein: a fast event matching approach for content-based publish/subscribe systems. In: Proceedings of IEEE INFOCOM, Toronto, 2014. 2058--2066. Google Scholar

[12] Jerzak Z, Fetzer C. Bloom filter based routing for content-based publish/subscribe. In: Proceedings of the 2nd International Conference on Distributed Event-based Systems, Rome, 2008. 71--81. Google Scholar

[13] Whang S E, Garcia-Molina H, Brower C, et al. Proc VLDB Endowment, 2009, 2: 37-48 CrossRef Google Scholar

[14] Jafarpour H, Mehrotra S, Venkatasubramanian N, et al. Mics: an efficient content space representation model for publish/subscribe systems. In: Proceedings of the 3rd ACM International Conference on Distributed Event-based Systems, Nashville, 2009. 7--12. Google Scholar

[15] Shen Z, Tirthapura S. J Parall Distrib Comput, 2012, 72: 1591-1602 CrossRef Google Scholar

[16] Jayaram K, Wang W, Eugster P. IEEE Trans Parall Distrib Syst, 2014, 99: 1-11 Google Scholar

[17] Wang Y M, Qiu L, Verbowski C, et al. ACM SIGCOMM Comput Commun Rev, 2004, 34: 59-74 CrossRef Google Scholar

Copyright 2019 Science China Press Co., Ltd. 《中国科学》杂志社有限责任公司 版权所有