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 condition. Many practical queries can be answered efficiently with W-join, especially in multi-sensor networks. We describe new algorithms 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 pre-
fixes 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 variety of stream data rates and stream delays.