Indexing for Subscription Covering in Publish-Subscribe SystemsShen, Zhenhui and Aluru, Srinivas and Tirthapura, Srikanta (2005) Indexing for Subscription Covering in Publish-Subscribe Systems. Publisher UNSPECIFIED. Full text available as:
AbstractContent 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.
Archive Staff Only: edit this record |
