Event Probability Based Priority Filter for Efficient Event Matching

Abstract:

Event matching plays a critical role in content-based publish/subscribe system. Most traditional methods focus on existing subscriptions separation and combination. However, an event usually comes with certain probability distribution in each dimension. Thus taking both existing subscriptions and probable coming event into consideration can improve event matching time efficiency. Based on that, we put forward PF (Priority Filter), a highly efficient event matching algorithm. By building up a unified model with historical subscriptions for continuous and discrete attributes, we derive formulas to calculate each attribute’s filtering rate. Besides, in order to guarantee time efficiency both in matching, inserting, and deleting, a red-black tree regarded as a priority filter is built up on all attributes according to filtering rate. Experiments demonstrate that PF has a 30% faster speed compared to existing methods with acceptable insertion and deletion time and memory consumption.

• Periodical: Applied Mechanics and Materials (Volumes 687-691)
• Pages: 1672-1676
• DOI: https://doi.org/10.4028/www.scientific.net/AMM.687-691.1672
• Online since: November 2014
• Authors: Wen Hao Fan, Lei Ding, Bi Hua Tang, Fan Wu*, Hong Guang Zhang
• Keywords: Event Matching, Existing Subscription, Priority Filter, Probability of Event

References

[1] Guo X, Wei J, and Han D. Efficient event matching in publish/subscribe: based on routing destination and matching history. International Conference on Networking, Architecture, and Storage, 2008: 129-136.

DOI: 10.1109/nas.2008.35

[2] Souleiman Hasan, Sean O'Riain, Edward Curry. Approximate semantic matching of hetetogeneous events. 6th ACM International Conference on Distributed Event-Based Systems. 2012: 252–263.

DOI: 10.1145/2335484.2335512

[3] Zhao Y, and Wu J. Towards approximate event processing in a large-scale content-based network. 31st International Conference on Distributed Computing Systems. 2011: 790-799.

DOI: 10.1109/icdcs.2011.67

[4] Jerzak Z, Fetzer C. Bloom filter based routing for content-based publish/subscribe. The second international conference on Distributed event-based systems. ACM, 2008: 71-81.

DOI: 10.1145/1385989.1385999

[5] Whang S E, Garcia-Molina H, Brower C, and et al. Indexing boolean expressions. Proceedings of the VLDB Endowment. 2009, 2(1): 37-48.

DOI: 10.14778/1687627.1687633

[6] 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 on parallel and distributed systems. (2014).

DOI: 10.1109/tpds.2014.2323262

[7] Sadoghi M, Jacobsen H A. BE-Tree: An index structure to efficiently match Boolean expressions over high-dimensional discrete space. Proceedings of the 2011 ACM SIGMOD International Conference on Management of data. 2011: 637-648.

DOI: 10.1145/1989323.1989390

[8] Jayaram K R, Eugster P. Split and subsume: Subscription normalization for effective content-based messaging. 31st International Conference on Distributed Computing Systems. 2011: 824-835.

DOI: 10.1109/icdcs.2011.85

[9] Zhenhui Shen and Srikanta Tirthapura. Approximate covering detection among content-based subscriptions using space filling curves. Journal of Parallel and Distributed Computing. (2012).

DOI: 10.1016/j.jpdc.2012.09.002

[10] Breslau L, Cao P, Fan L, and et al. Web caching and Zipf-like distributions: Evidence and implications. 18nd Annual Joint Conference of the IEEE Computer and Communications Societies. 1999, 1: 126-134.

DOI: 10.1109/infcom.1999.749260