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

Subscription covering is an 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 relationships among subscriptions can be a costly computational task; this cost can potentially reduce the utility of covering as an optimization. We introduce an alternate approach called approximate subscription covering, that can provide much of the benefits of subscription covering at a fraction of the cost. By forgoing an exhaustive search for covering subscriptions in favor of an approximate search, it is shown that the time complexity of covering detection can be dramatically reduced. The tradeoff 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.

► Expensive to find covering relationships among content-based subscriptions.
► Introduce notion of approximate covering among subscriptions.
► It can be much cheaper to detect approximate covering relationships.
► Algorithm based on space filling curves.
► Upper and Lower Bounds, additional evaluation through simulations.