Real-time stream processing is essential for many real-life stream-based applications. Systems designed to run such applications must be prepared to operate under overloaded conditions. In this paper, the load shedding problem is studied for an important class of real-time data stream monitoring applications. In particular, we adopt the deadline model, instead of the commonly used random dropping policy, to capture the QoS requirements of such applications. Based on this model, we propose a Safe lOad Shedding Approach (SOSA) that aims to reduce the workload imposed on the system while at the s...