Efficient predicate matching is essential to provide real-time responses in processing continuous data streams. Predicate indexes are commonly used to find the predicates matched by continuously arriving tuples in a timely manner. In this paper, we propose a hybrid indexing method to support fast insertion of predicates in data stream processing. Our method deals with open and closed interval predicates separately. We use shared ordered lists of the PB+-tree scheme to process open interval predicates efficiently, while use an algorithm of the IBS-tree to process closed interval ones. Our experimental results show that (1) the proposed method provides approximately 3 times better insertion performance than the IBS-tree when there are both of open and closed interval predicates with ratio of 1:1 and (2) their performance gap can be more than 12 times as the ratio of open interval predicates increases.
['Hyeon Gyu Kim', 'Myoung Ho Kim']
A Hybrid Method for Fast Predicate Matching in Data Stream Processing