Temporal Coalescing on Window Extents over Data Streams

Mohammed AL-KATEB  Sasi Sekhar KUNTA  Byung Suk LEE  

IEICE TRANSACTIONS on Information and Systems   Vol.E94-D    No.3    pp.489-503
Publication Date: 2011/03/01
Online ISSN: 1745-1361
DOI: 10.1587/transinf.E94.D.489
Print ISSN: 0916-8532
Type of Manuscript: Special Section PAPER (Special Section on Data Engineering)
data streams,  window extents,  temporal coalescing,  

Full Text: PDF(487.4KB)>>
Buy this Article

This paper focuses on the coalescing operator applied to the processing of continuous queries with temporal functions and predicates over windowed data streams. Coalescing is a key operation enabling the evaluation of interval predicates and functions on temporal tuples. Applying this operation for temporal query processing on windowed streams brings the challenge of coalescing tuples in a window extent each time the window slides over the data stream. This coalescing becomes even more involving when some tuples arrive out of order. This paper distinguishes between eager coalescing and lazy coalescing, the two known coalescing schemes. The former coalesces tuples during window extent update and the latter does it during window extent scan. With these two schemes, the paper first presents algorithms for updating a window extent for both tuple-based and time-based windows. Then, the problem of optimally selecting between eager and lazy coalescing for concurrent queries is formulated as a 0-1 integer programming problem. Through extensive performance study, the two schemes are compared and the optimal selection is demonstrated.

open access publishing via