ISU Electrical and Computer Engineering Archives

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.

EPrint Type:Technical Report
Subjects:Computer Engineering > SOFTWARE SYSTEMS > Parallel and Distributed Computing
ID Code:306
Identification Number:TR-2007-03-1
Deposited By:Mr. Zhenhui Shen
Deposited On:19 March 2007

Available Versions of this Item

Archive Staff Only: edit this record