ISU Electrical and Computer Engineering Archives

Indexing for Subscription Covering in Publish-Subscribe Systems

Shen, Zhenhui and Aluru, Srinivas and Tirthapura, Srikanta (2005) Indexing for Subscription Covering in Publish-Subscribe Systems. Publisher UNSPECIFIED.

Full text available as:

PDF - Requires Adobe Acrobat Reader or other PDF viewer.


Content based publish-subscribe systems are being increasingly used to deliver information in large distributed environments. Subscription covering is an effective way to reduce the complexity of content-based routing and avoid unnecessary proliferation of subscriptions throughout the system. Although covering detection has been implemented in current systems, their efficient implementation has not been systematically studied so far. In this paper, we propose a general framework for covering detection and for maintaining currently exploited covering relationships. We formalize the interaction between the above two tasks and show that a simple heuristic provides a 2-approximation algorithm for optimizing the number of covering queries on average. We also present efficient indexing schemes for covering queries resulting from range-based numeric subscriptions. We formulate this as a multidimensional range-search problem and explore the use of well-known spatial indexing schemes based on $k$-d trees and space filling curves. Experimental results demonstrate that the proposed indexing schemes offer significant performance gains.

EPrint Type:Technical Report
Uncontrolled Keywords:publish subscribe, subscription covering, relation graph, multidimensional index
Subjects:Computer Engineering > SOFTWARE SYSTEMS > Parallel and Distributed Computing
ID Code:163
Identification Number:TR-2005-07-2
Deposited By:Mr. Zhenhui Shen
Deposited On:08 July 2005

Archive Staff Only: edit this record