Indexing for Subscription Covering in Publish-Subscribe Systems.
Zhenhui Shen, Srinivas Aluru, Srikanta Tirthapura · 2005
Abstract — Content based publish-subscribe systems are being increasingly used to deliver information in large dis-tributed 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 imple-mented 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 be-tween 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. I.