Multi-granular Time-Based Sliding Windows over Data Streams Full text

K. Patroumpas and T. Sellis
Proceedings of the 17th International Symposium on Temporal Representation and Reasoning (TIME 2010), pp. 146-153, Paris, France, September 2010
Abstract. We introduce a multi-level window operator that concurrently spans temporal extents of increasing granularity over a streaming dataset. This windowing construct is inherently sliding with time, essentially providing at each granularity a varying, but always finite portion of the most recent stream items. After a careful algebraic formulation of its semantics, we investigate interesting properties and suggest a suitable data structure that can efficiently maintain tuples qualifying for each granular level. Moreover, we propose techniques for evaluating advanced continuous requests against multiple time horizons, achieving near real-time response at reduced overhead. Finally, this framework is empirically validated against streaming data, offering concrete evidence of its benefits to online stream processing.