  Although many scalable event matching algorithms have been proposed to
achieve scalability for large-scale content-based networks, content-based
publish/subscribe networks (especially for large-scale real time systems) still
suffer performance deterioration when subscription scale increases. While
subscription aggregation techniques can be useful to reduce the amount of
subscription dissemination traffic and the subscription table size by
exploiting the similarity among subscriptions, efficient subscription
aggregation is not a trivial task to accomplish. Previous research works have
proved that it is either a NP-Complete or a co-NP complete problem. In this
paper, we propose DLS (Discrete Label Set), a novel subscription representation
model, and design algorithms to achieve the mapping from traditional Boolean
predicate model to the DLS model. Based on the DLS model, we propose a
subscription aggregation algorithm with O(1) time complexity in most cases, and
an event matching algorithm with O(1) time complexity. The significant
performance improvement is at the cost of memory consumption and controllable
false positive rate. Our theoretical analysis shows that these algorithms are
inherently scalable and can achieve real time event matching in a large-scale
content-based publish/subscribe network. We discuss the tradeoff between
memory, false positive rate and partition granules of content space.
Experimental results show that proposed algorithms achieve expected
performance. With the increasing of computer memory capacity and the dropping
of memory price, more and more large-scale real time applications can benefit
from our proposed DLS model, such as stock quote distribution, earthquake
monitoring, and severe weather alert.
