Adaptive Execution of Stream Window Joins in a Limited Memory Environment

A sliding window join (SWJoin) is becoming an integral operation in every stream data management system. In some streaming applications the increasing volume of streamed data as well as the multiplicity of concurrent queries requires an adaptive SWJoin algorithm for the limited memory resources. Previous algorithms of SWJoin address the memory limitation by exploiting external-memory resources while imposing timely ordered arrival of input data streams. In this paper we propose an external-memory sliding-window join algorithm (EM-SWJoin) that addresses general arrival patterns of input streams and exploits disk- based data structures. The algorithm runs in two phases. The first phase partially joins the arriving data of one stream with the memory-resident data of the other streams. The second phase completes the processing of the partially joined data by considering the disk-resident data from the corresponding streams. Swapping from one phase to the other improves the response time of the input data. A comparative study between EM-SWJoin and other related algorithms illustrates the superiority of the proposed algorithm.