Adaptive selection of tuples over data streams for efficient load shedding

摘要

In recent years, data stream processing algorithms have been actively proposed. In terms of computing performance, they mainly focus on the restriction of their memory usage and minimization of their processing time per data element. However, if the number of data elements in a time slot is greater than the number of those that can be processed for the time slot, some of them cannot be processed in real time even though the processing time per data element is minimized. In this paper, a selection method of frequent tuples over a data stream for efficient load shedding is proposed. Furthermore, considering the change of the data stream, a threshold for the tuples to be selected is adaptively controlled by a prediction mechanism for the frequency of a tuple. Through this mechanism, the number of selected tuples is maximized within the capacity of the main-processing operation.