The Algorithm Of Event Matching In Content-Based Publish/Subscribe Systems

Distributed object-oriented communication middleware aims at solving the problem of interoperability among distributed software in heterogeneous network environments, which can hide the detail of network communication and improve the portability. These it has been applied in many fileds and has became the major technology for implementing distributed computation. With the rapid development of Internet, the pattern of software has shifted from closed, the local familiar user groups and relative static tight-coupled form to open, public accessing and dynamic coordination loosely-coupled form. The single synchronous communication mechanism which is provided by traditional object-oriented middleware based on RPC(Remote Procedure Call) mechanism can't satisfy the dynamic characteristic of Internet. To coupe with this challenge, it is necessary to provide an asynchronous and loosely coupled communication paradigm for building distributed application at top layer.Publish/Subscribe is a communication paradigm based on event. Compared with asynchronous RPC, distributed shared memory and message queuing, it provides complete decoupling in space, time and control flow for participants. So it can satisfy the requirement of loosely coupled communication. It has gotten broad attention and deep research.Publish/Subscribe can be divided into channel-based, topic-based and content-based system according to the notification selection mechanism. Channel-based and topic-based publish/subscribe is simple, but content-based publish/subscribe has more powerful, more flexible and broad abroad adaptive character. So content-based publish/subscribe is one of the basic infrastructure to construct new pattern distributed applications in the future. But compared with topic-based publish/subscribe, content-based publish/subscribe is more complex. In order to grow into a practical infrastructure to support large scale distributed applications in deed, there are many key technologies to be solved yet. One bottleneck restricting its development is events matching. For content-based Publish / Subscribe systems, because of the need to make matching and judging for all the filtered attributes, finding all matching subscription is a very challenging thing, the majority matching algorithms which have been using at present are based on such thought: for all the repeating constraints of each subscribers, only judging one time to optimize, and make full use of subscriptions index structure so as to shorten the matching time.This thsis puts forward a new matching algorithm--Algorithm Based On Multidimensional Indexing Structure(MIS/AL), analysing the predecessors'algorithm, and balancing time-efficiency of matching, space-efficient of matching and the costs of maintenance the subscriptions three factors. MIS/AL algorithm compares with the traditional method has the following advantages:Fist: this algorithm can also support "and" and "or" two basic logical operation, so it is needless to transform all the "or" operation into "and" operation in pretreatment like other algorithms.Second: this algorithm introduces a multidimensional indexing structure, which not only greatly optimizes the matching time efficiency, but also reduces the costs of maintaining subscription.The experiments showed that its efficiency has improved greatly than other commonly used algorithm, and with extensibility. It is suitable for large-scale, distributed and content-based Publish/Subscribe system.