Adaptive Disorder Control in Data Stream Processing

Year, pages: 2012, 393 - 410

Out-of-order tuples in continuous data streams may cause inaccurate query results since conventional window operators generally discard those tuples. Existing approaches use a buffer to fix disorder in stream tuples and estimate its size based on the maximum network delay seen in the streams. However, they do not provide a method to control the amount of tuples that are not saved and discarded from the buffer, although users may want to keep it within a predefined error bound according to application requirements. In this paper, we propose a method to estimate the buffer size while keeping the percentage of tuple drops within a user-specified bound. The proposed method utilizes tuples' interarrival times and their network delays for estimation, whose parameters reflect real-time stream characteristics properly. Based on two parameters, our method controls the amount of tuple drops adaptively in accordance with fluctuated stream characteristics and keeps their percentage within a given bound, which we observed through our experiments.

Kim, H., Kim, C., Kim, M. 2012. Adaptive Disorder Control in Data Stream Processing. In Computing and Informatics, vol. 31, no.2, pp. 393-410. 1335-9150.

Kim, H., Kim, C., Kim, M. (2012). Adaptive Disorder Control in Data Stream Processing. Computing and Informatics, 31(2), 393-410. 1335-9150.