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.
Publié le : 2012-07-18
Classification:  Data stream processing; sliding windows; buffer estimation; disorder control; drop ratio
@article{cai946,
     author = {Hyeon Gyu Kim; Korea Atomic Energy Research Institute and Cheolgi Kim; School of EECS, Korea Aerospace University and Myuong Ho Kim; Korea Advanced Institute of Science and Technology},
     title = {Adaptive Disorder Control in Data Stream Processing},
     journal = {Computing and Informatics},
     volume = {28},
     number = {1},
     year = {2012},
     language = {en},
     url = {http://dml.mathdoc.fr/item/cai946}
}
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. Adaptive Disorder Control in Data Stream Processing. Computing and Informatics, Tome 28 (2012) no. 1, . http://gdmltest.u-ga.fr/item/cai946/