A dynamic and fast event matching algorithm for a content-based publish/subscribe information dissemination system in Sensor-Grid

摘要

In this paper, we discuss one of the most important issues in Sensor-Grid, i.e., to develop a fast and flexible content-based publish/subscribe information dissemination (CBPSID) system for automatic fusion, interpretation, sharing and delivery of huge sensor data to consumers as the entire Sensor-Grid environment is very dynamic. Existing works to develop the CBPSID system in Sensor-Grid mostly focus on reducing the effort to define and maintain subscriptions and to handle the difficulty of dynamic changes of publishers and consumers data. However, the performance of a CBPSID system in Sensor-Grid is bounded by the expensive matching/evaluation cost of events. Existing event-matching algorithms are not very efficient, especially for interval range predicates or overlapping predicates in subscriptions which are practical in Sensor-Grid as well as other application areas. So in this paper we discuss the above challenge and propose a dynamic and fast event-matching algorithm called CGIM for the CBPSID system in Sensor-Grid. The algorithm supports range predicates or overlapping predicates very well and provides single and composite event matching. It uses two approaches, called SGIM and DGIM, to group the subscriptions by the predicates and dynamically identifies appropriate number of groups considering different statistical distributions of subscriptions at run time. Also, we present an experimental evaluation of the proposed algorithm in a Sensor-Grid based u-Healthcare scenario using synthetic workloads and compare its performance with existing algorithms. The experimental results show that our algorithm significantly reduces the evaluation cost (on average using SGIM by 79% and DGIM by 88%) comparing with others and guarantees the scalability with respect to the number of subscriptions as well as the number of predicates and events. In addition, further experiments were conducted by applying the CGIM algorithm in other application areas, e.g. in the publish/subscribe system for online job sites, to show its diverse utilization and scalability.