Joining Multiple Data Streams with Window Constraints

This paper introduces a class of join algorithms, termed stream window join (W-join for short), for joining multiple infinite data streams.W-join addresses the infinite nature of the data streams by joining stream.data items that lie within a sliding window and that match a certain join can• dition.Many practical queries can be answered efficiently with W-join, especially in multi-sensor networks.We describe new algOrithIIlli for W-join, and address variations and local/global optimizations related to specifying the nature of the window constraints.In contrast to existing stream join algorithms that store the entire stream prefixes in intermediate structures, we avoid repeated iterations over non-window-related tuples.We present a variety of non-blocking and pipelined algorithms for performing W-join and its variations.These algorithms include nested.loop,hash, and merge-join implementations of W-join (NLW-join, HW-join, and MW-join, respectively).The algorithms utilize a filter-refine paradigm to handle the variations in window constraints and filter out false-positive answers.For comparison purposes, we adapt existing stream join algorithms in the literature to handle the W-join operation.We experiment with the new and existing algorithms in a prototype stream database system, developed at Purdue, using both real and synthetic data streams.We demonstrate that the newly proposed W-join algorithms outperform the existing algorithms by an order of magnitude under a va• riety of stream data rates and stream delays.