Research On Fast Matching Algorithm Based On Matching Tree's Publishing Subscription

In recent years,with the rapid development of Internet,the application scope of distributed computing is more and more wide and the use scale is more and more big.In the present,the information publishing system based on distributed computing has been widely used.The traditional information publishing system has the characteristics of high coupling,it is difficult to apply to the needs of large-scale,asynchronous and multicast communication.Because of its own asynchronous and multi point communication characteristics,the Publish/subscribe system can be applied to the demand of the low coupling communication of the large Internet Information publishing/subscribing system well.The Publish/Subscribe system can be divided into a theme based,channel and content-based publish/subscribe system,in which the topic-based and channel based publish/subscribe system is simple,but its expressive ability is not suitable for large-scale distributed systems,and the content-based Publishing/subscribing system has rich expressive ability and flexible subscription.,and can be used to retrieve the event,which is more suitable for the large-scale distributed system.In a content-based publish/subscribe system,the system's subscriptions need to match the events to the subscription criteria,and the system forwards the data to subscribers based on matching results,and when the number of subscriptions is very large,there are a lot of events and subscriptions in the system that can cause a lot of blocking in the system.The purpose of the matching algorithm,is responsible for the publish /subscription system can efficiently and reliably find a given event matching the subscription,therefore,how to implement an efficient matching algorithm,and to build a large-scale publishers and subscribers to parallel interaction of efficient publish/subscribe system,is currently the focus of domestic and foreign scholars.At present,the method used in most systems is to index the subscription condition through the tree structure,to improve the matching efficiency,but there are still some problems such as excessive matching time consuming and duplicate matching.In order to solve these problems,this paper makes improvements based on the existing algorithms,In this paper,a matching algorithm based on multilevel constrained search tree is proposed,based on which,combined with inverted index,an efficient matching scheme is constructed,which adapts to the parallel interaction between large publishers and subscribers,and the main research work is as follows:1? A fast matching algorithm for multi-layer constrained search trees,namely MCTF,is designed.The algorithm based on the constraint search tree,although the same conditions only need to match once,but the subscription conditions and events need to traverse the entire search tree,the system overhead is still lager.To solve this problem,a multi-layer constraint search tree fast matching algorithm namely MCTF is design.MCTF increases the multi-layer constraint condition and establishes the coverage relationship between the constraints.When the subscription condition satisfies the constraint condition in the matching,the traversal will terminated.It does not continue to traverse the entire constraint search tree,which improves the matching efficiency and reduces the maintenance overhead.Experiments show that matching consumption time of MCTF is significantly reduce.2? A matching mechanism of pub/sub system based on inverted index,namely IFMA,is designed.MCTF(Multi-constraint search tree fast matching algorithm)reduces some problems of duplicate matching,when an event has multiple subscription conditions.However,there exist still some problems of duplicate matching,when there are multiple events for multiple subscription conditions.To solve these problems,by introducing the inverted index based on multi-layer constraint search tree,an efficient matching mechanism,namely IFMA,is constructed.IFMA is suitable for parallel interaction between large-scale publishers and subscribers.By analyzing the coverage relationship between the subscription conditions and events depending on the inverted index,IFMA reduces the number of matches for subscription conditions and events,and further improves the matching efficiency.