GENERAL AND AUTOMATIC APPROACH TO INCREMENTALLY COMPUTING SLIDING WINDOW AGGREGATES IN STREAMING APPLICATIONS

摘要

A method of incrementally computing an aggregate function of a sliding window in a streaming application includes receiving a plurality of data tuples in the sliding window, extracting at least one data tuple from the sliding window, and storing the at least one extracted data tuple in a data structure in a memory. The data structure is a balanced tree and the at least one data tuple is stored in leaf nodes of the balanced tree. The method further includes maintaining at least one intermediate result in at least one internal node of the balanced tree. The at least one intermediate result corresponds to a partial window aggregation. The method further includes generating a final result in the balanced tree based on the at least one intermediate result, and outputting the final result from the balanced tree. The final result corresponds to a final window aggregation.