{'fraction_non_alphanumeric': 0.015410958904109588, 'fraction_numerical': 0.0008561643835616438, 'mean_word_length': 5.796511627906977, 'pattern_counts': {'":': 0, '<': 0, '<?xml version=': 0, '>': 0, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Indexing for Subscription Covering in Publish-Subscribe Systems

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 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 rangesearch problem and explore the use of two well-known spatial indexes, k-d tree and space filling curve. Experimental results demonstrate that the proposed indexing schemes offer significant performance gains.