Efficient predicate matching and disorder control over continuous data streams

Abstract

In this dissertation, we discuss two issues on processing window queries over continuous data streams: efficient predicate matching and disorder control. Regarding the first, window queries can be specified with filtering conditions. Given a lot of queries with filtering conditions, a predicate index can be used to help finding candidate queries efficiently whose conditions are satisfied by input events. We propose a predicate indexing method which handles equality and inequality tests separately. Our method uses a hash table for the equality test and a balanced binary search tree for the inequality test. Such a separate structure reduces a height of the search tree and the number of comparisons per tree node, as well as the cost for tree rebalancing. We compare the proposed method with the IBS-tree which is one of the popular indexing methods suitable for data stream processing. Our experimental results show that the proposed method provides better insertion and search performances than the IBS-tree. Regarding the second, out-of-order tuples may cause inaccurate query results since conventional window operators discard those tuples. To resolve this issue, we propose a method to fix disorder of stream tuples while keeping a percentage of tuple drops within a user-specified bound. The proposed method utilizes tuples` interarrival times and their network delays for estimation, whose parameters reflect real-time stream characteristics properly. Based on two parameters, our method controls the amount of tuple drops adaptively in accordance with fluctuated stream characteristics. We compare our method with an existing method which controls disorder based on the maximum network delay seen in the stream. We show through our experiments that (i) it is hard to control the amount of tuple drops in the existing method, and (ii) the proposed method observes a user-specified drop ratio over data streams whose characteristics are dynamically changed.