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.

主权项

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