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.

There is a more recent version of this eprint available. Click here to view it.

Full text available as:

PDF - Requires Adobe Acrobat Reader or other PDF viewer.

Abstract

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

• Approximate Covering Detection among Content-Based Subscriptions Using Space Filling Curves (deposited 19 March 2007) [Currently Displayed]
  • Approximate Covering Detection among Content-Based Subscriptions Using Space Filling Curves (deposited 04 May 2007)

Archive Staff Only: edit this record