Monitoring of timing constraints and streaming events with temporal uncertainties

There are many emerging applications which need a functionality of monitoring of streaming events. In most extant work for monitoring streaming events, the exact occurrence time of every event is assumed to be known. However, there are practical situations where we are not sure about the exact occurrence time of an event but we are able to limit the range of the temporal uncertainty. In this thesis, we study how to monitor timing constraints and streaming events with uncertain timestamps. Time intervals are adopted to represent the temporal uncertainties in the timestamps of events. New specification schemes for timing constraints over interval timestamps and efficient monitoring algorithms are presented. Firstly, we introduce two modalities, certain and possible, to impose timing constraints over interval timestamps. The satisfaction of a timing constraint having the certain modality means that the condition of the timing constraint is met for sure. A timing constraint with the possible modality is deemed to be satisfied if there is any chance that the condition of the timing constraint is met. The algorithms for monitoring such timing constraints and the techniques for deriving implicit constraints from a set of timing constraints are also introduced. Then, we propose another timing constraint specification method using a probabilistic approach. A user can state a confidence threshold in a timing constraint specification denoting the minimum acceptable probability for the timing constraint. To detect violations of timing constraints efficiently, we derive the maximum satisfaction probability graph for deadline constraints. Given a threshold we can compute with this graph the earliest time at which we can declare a timing violation when the waiting event needed for satisfying the constraint is absent. Lastly, we introduce a new type of stream join operator, the interval timing join. The interval timing join enables users to correlate streaming events from various stream sources by assessing temporal conditions over the interval timestamps of the events. We present an effective technique for range searching in stream buffers for within timing predicates. Various interval timing join algorithms are designed and performance experiments are done for showing the effectiveness of our proposed technique.