Campus Units

Electrical and Computer Engineering, Computer Science

Document Type

Article

Publication Version

Accepted Manuscript

Publication Date

12-2012

Journal or Book Title

Journal of Parallel and Distributed Computing

Volume

72

Issue

12

First Page

1591

Last Page

1602

DOI

10.1016/j.jpdc.2012.09.002

Abstract

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.

Comments

This is a manuscript of an article published as Shen, Zhenhui, and Srikanta Tirthapura. "Approximate covering detection among content-based subscriptions using space filling curves." Journal of Parallel and Distributed Computing 72, no. 12 (2012): 1591-1602. DOI: 10.1016/j.jpdc.2012.09.002. Posted with permission.

Creative Commons License

Creative Commons Attribution-Noncommercial-No Derivative Works 4.0 License
This work is licensed under a Creative Commons Attribution-Noncommercial-No Derivative Works 4.0 License.

Copyright Owner

Elsevier Inc.

Language

en

File Format

application/pdf

Published Version

Share

COinS