UB-Tree Based Efficient Predicate Index with Dimension Transform for Pub/Sub System

摘要

For event filtering of publish/subscribe system, significant research efforts have been dedicated to techniques based on multiple one-dimensional indexes built on attributes of subscription. Because such kinds of techniques are efficient only in the case that operators used in predicates are equality operator ( = ) and attributes used in subscriptions are fixed, the flexibility and expressiveness of publish/subscribe system are limited. Event filtering on subscriptions which include not only equality operator ( = ) but also non-equality operators ( < =, = > ) without fixed attributes, is similar to query in high dimensional data space. In this paper, considering dynamic maintenance and space efficiency of publish/subscribe system, we propose an index structure for event filtering based on UB-tree. There, by dimension transform, the event filtering is regarded as high dimensional range query. The feasibility of the proposed index is evaluated in simulated publish/subscription environment. Results show that in almost all the cases, the performance our proposed index is 4 order of magnitude faster than counting algorithm. Because our index can support both equality operator ( = ) and non-equality operators ( < =, > = ), we can conclude that our proposal is efficient and flexible for event filtering of publish/subscribe system under reasonable size of dimension.