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.

Keywords

Cite this article

@article{cai-19140,
  author  = {Hyeon Gyu Kim and Cheolgi Kim and Myoung Ho Kim},
  title   = {Adaptive Disorder Control in Data Stream Processing},
  journal = {Computing and Informatics},
  volume  = {31},
  number  = {2},
  pages   = {393--410},
  year    = {2012},
  issn    = {1335-9150},
  url     = {https://cai.type.sk/content/2012/2/adaptive-disorder-control-in-data-stream-processing/}
}
Download .bib