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

详细信息    查看全文

• 作者：Wenhao Fan ; Yuanan Liu ; Bihua Tang
• 关键词：event matching ; publish/subscribe ; data dissemination ; end ; to ; end communications ; interval search ; combinatorial optimization ; 022315 ; 事件匹配 ; 发布/订阅 ; 数据分发 ; 端到端通信 ; 区间搜索 ; 组合优化
• 刊名：SCIENCE CHINA Information Sciences
• 出版年：2016
• 出版时间：February 2016
• 年：2016
• 卷：59
• 期：2
• 页码：1-16
• 全文大小：776 KB
• 参考文献：1.Eugster P T, Felber P A, Guerraoui R, et al. The many faces of publish/subscribe. ACM Comput Surv, 2003, 35: 114–131CrossRef
  2.Ma X K, Wang Y J, Sun W D. Feverfew: a scalable coverage-based hybrid overlay for internet-scale pub/sub networks. Sci China Inf Sci, 2014, 57: 052103
  3.Muhl G, Ulbrich A, Herrman K. Disseminating information to mobile clients using publish-subscribe. IEEE Internet Comput, 2004, 8: 46–53CrossRef
  4.Guinard D, Trifa V, Karnouskos S, et al. Interacting with the soa-based internet of things: discovery, query, selection, and on-demand provisioning of web services. IEEE Trans Serv Comput, 2010, 3: 223–235CrossRef
  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
  6.Jayaram K, Jayalath C, Eugster P. Parametric subscriptions for content-based publish/subscribe networks. In: Middleware. Berlin: Springer, 2010. 128–147
  7.Krügel C, Toth T, Kerer C. Decentralized event correlation for intrusion detection. In: Information Security and Cryptology-ICISC 2001. Berlin: Springer, 2002. 114–131CrossRef
  8.Layer R M, Skadron K, Robins G, et al. Binary interval search: a scalable algorithm for counting interval intersections. Bioinformatics, 2013, 29: 1–7CrossRef
  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
  10.Qian S, Cao J, Zhu Y, et al. H-tree: an efficient index structure for event matching in content-based publish/subscribe systems. IEEE Trans Parall Distr Syst, 2014, 99: 1–11
  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
  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–81CrossRef
  13.Whang S E, Garcia-Molina H, Brower C, et al. Indexing boolean expressions. Proc VLDB Endowment, 2009, 2: 37–48CrossRef
  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
  15.Shen Z, Tirthapura S. Approximate covering detection among content-based subscriptions using space filling curves. J Parall Distrib Comput, 2012, 72: 1591–1602CrossRef MATH
  16.Jayaram K, Wang W, Eugster P. Subscription normalization for effective content-based messaging. IEEE Trans Parall Distrib Syst, 2014, 99: 1–11
  17.Wang Y M, Qiu L, Verbowski C, et al. Summary-based routing for content-based event distribution networks. ACM SIGCOMM Comput Commun Rev, 2004, 34: 59–74CrossRef
  
• 作者单位：Wenhao Fan (1) (2)
  Yuanan Liu (1) (2)
  Bihua Tang (1) (2)
  
  1. School of Electronic Engineering, Beijing University of Posts and Telecommunications, Beijing, 100876, China
  2. Beijing Key Laboratory of Work Safety Intelligent Monitoring, Beijing University of Posts and Telecommunications, Beijing, 100876, China
  
• 刊物类别：Computer Science
• 刊物主题：Chinese Library of Science
  Information Systems and Communication Service
  
• 出版者：Science China Press, co-published with Springer
• ISSN：1869-1919

文摘

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. Keywords event matching publish/subscribe data dissemination end-to-end communications interval search combinatorial optimization