Efficient Matching Algorithm for Content-based Publish/Subscribe Systems with Compound Predicates
Authors: 
Xilai Lv, Yongqiang DongAuthors Info & Claims
Pages 99 - 103
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.
Recommendations
Parallel Matching Algorithms of Publish/Subscribe System
ITNG '11: Proceedings of the 2011 Eighth International Conference on Information Technology: New GenerationsPublish/subscribe systems form an important communication paradigms in distributed systems. However, how to leverage current chip multi-processors to increase throughput and reduce the matching time still need further research. In this paper, we present ...
Publish/Subscribe Driven Matching Algorithm
ICICSE '09: Proceedings of the 2009 Fourth International Conference on Internet Computing for Science and EngineeringThe characteristics of publish/subscribe technology are of asynchronism and loosely coupled. This phenomenon makes producers and consumers are de-communicated in temporal and spatial domains during processing. It requires develop a dynamic integration ...
Securing Broker-Less Publish/Subscribe Systems Using Identity-Based Encryption
The provisioning of basic security mechanisms such as authentication and confidentiality is highly challenging in a content-based publish/subscribe system. Authentication of publishers and subscribers is difficult to achieve due to the loose coupling of ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
June 2016
126 pages
ISBN:9781450341813
DOI:10.1145/2935663
Copyright © 2016 ACM.
Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]
In-Cooperation
- AsiaFI: Asia Future Internet
Publisher
Association for Computing Machinery
New York, NY, United States
Publication History
Published: 15 June 2016
Check for updates
Author Tags
Qualifiers
- Short-paper
- Research
- Refereed limited
Funding Sources
- National High Technology Research and Development Program (863 Program) of China
- National Natural Science Foundation of China
Conference
CFI '16
CFI '16: The 11th International Conference on Future Internet Technologies
June 15 - 17, 2016
Nanjing, China
Acceptance Rates
Overall Acceptance Rate 29 of 55 submissions, 53%
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- 0Total Citations
- 93Total Downloads
- Downloads (Last 12 months)1
- Downloads (Last 6 weeks)0
Reflects downloads up to 12 Nov 2024
Other Metrics
Citations
View Options
Get Access
Login options
Check if you have access through your login credentials or your institution to get full access on this article.
Sign in