Open Access

Cui Qin

• Stream processing is a popular paradigm to process huge amounts of unbounded data, which has gained significant attention in both academia and industry. Typical stream processing applications such as stock trading and network traffic monitoring require continuously analyzed results provided to end-users. During processing, the characteristics of data streams such as volume or velocity can vary, e.g., peak load or bursty streams can occur at certain points. In order to cope with such situations, it requires the analytical systems to be able to adapt the execution of stream processing as quickly as possible. In literature, different approaches adapting data stream processing such as load-shedding and elastic parallelization do exist. However, each of them have their different shortcomings like skewed results (due to the dropped data) or strong limits on the adaptation due to the parallelization overhead. One specific challenge motivating us is to minimize the impact of runtime adaptation on the overall data processing, in particular for real-time data analytics. Moreover, while the need to create adaptive stream processing systems is well known, there is currently no systematic and broad analysis of the solution range of creating adaptation mechanisms for stream processing applications. In this dissertation, we focus on algorithm switching as a fundamental approach to the construction of adaptive stream processing systems. Algorithm switching is a form of adaptation, where stream processing algorithms, with fundamentally similar input-/output-characteristics but different runtime tradeoffs like resource consumption or precision, are replaced to optimize the processing. As our overall goal, we present a general algorithm switching framework that models a wide range of switching solutions (called switch variants) in a systematic and reusable manner as well as characterizes the switch variants with their quality guarantees. Concretely, we focus on developing a general model of algorithm switching to systematically capture possible variants of different switching behavior. We also present a theoretical specification to predict the timeliness-related qualities for the switch variants. Moreover, from the practical perspective, we also develop a component-based design to ease the realization effort of the algorithm switching variants. Finally, we provide a validation of the algorithm switching framework against the realized switch variants.