Approximate covering detection among content-based subscriptions using space filling curves

We consider a problem that arises during the propaga-tion of subscriptions in a content-based publish-subscribe system. Subscription covering is a promising optimization that reduces the number of subscriptions propagated, and hence, the size of routing tables in a content-based publish-subscribe system. However, detecting covering relation-ships among subscriptions can be an expensive computa-tional task that potentially reduces the utility of covering as an optimization. We introduce an alternate approach approximate sub-scription covering, which provide much of the benefits of subscription covering at a fraction of its cost. By forgoing an exhaustive search for covering subscriptions in favor of an approximate search, it is shown that the time complex-ity of covering detection can be dramatically reduced. The trade off between efficiency of covering detection and the approximation error is demonstrated through the analysis of indexes for multi-attribute subscriptions based on space filling curves. 1