Adaptive Disorder Control in Data Stream Processing

Authors

  • Hyeon Gyu Kim Korea Atomic Energy Research Institute
  • Cheolgi Kim School of EECS, Korea Aerospace University
  • Myuong Ho Kim Korea Advanced Institute of Science and Technology

Keywords:

Data stream processing, sliding windows, buffer estimation, disorder control, drop ratio

Abstract

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.

Downloads

Download data is not yet available.

Downloads

Published

2012-07-18

How to Cite

Kim, H. G., Kim, C., & Kim, M. H. (2012). Adaptive Disorder Control in Data Stream Processing. COMPUTING AND INFORMATICS, 31(2), 393–410. Retrieved from https://www.cai.sk/ojs/index.php/cai/article/view/946