Approximate Covering Detection among Content-Based Subscriptions Using Space Filling Curves
Shen, Zhenhui and Tirthapura, Srikanta (2007) Approximate Covering Detection among Content-Based Subscriptions Using Space Filling Curves. Publisher UNSPECIFIED.
This is the latest version of this eprint.
Full text available as:
We consider a problem that arises during the propagation 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 relationships among subscriptions can be an expensive computational task that potentially reduces the utility of covering as an optimization. We introduce an alternate approach approximate subscription 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 complexity 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.
Available Versions of this Item
Archive Staff Only: edit this record