Research On Novel Composite Event Detection Techniques For Markov Chains

With the rapid development of the RFID and sensor network, the complex event processing (CEP) for RFID data has attracted wide attention in many fields, such as the event alerting and event monitoring. Existing work about CEP are devoted to searching composite events by accurately matching certain atomic events. However, in practical applications, the atomic events are uncertain and correlated due to the leakage reading, etc. Moreover, the similar detection is requested in some scenarios. Meanwhile, it is important to protect private information when processing sensitive data. Therefore, we research on accurately matching, similar detection and privacy protecting of the composite event detection for the Markov event sequence.Firstly, for the uncertain event sequence which meets the Markov character, this thesis gives the formal definition of the matching event set and the uncertain composite event query (UCEQ), and then puts forward the methods based on sequence-first (seqF_Q) and correlation-first (corF_Q) to handle UCEQ. The two methods can solve UCEQ in polynomial time. Considering that seqF_Q and corF_Q are affected by many factors, we evaluate them on real data sets and synthetic data sets. Experiment results show that the performance of corF_Q is better than that of seqF_Q.Secondly, this thesis settles the problem of similar detection for the Markov event sequence. It defines the similar distance of composite events and the uncertain composite event similar query (UECSQ). For UECSQ, we construct the MCE-Index to improve the processing efficiency. By integrating the MCE-Index with seqF_Q and corF_Q, we propose the similar composite event query methods based on sequence-first (seqF_SQ) and correlation-first (corF_SQ) separately. Furthermore, we improve corF_SQ by designing the cache mechanism, namely corF_ca_SQ. Experiment results on real data sets and synthetic data sets validate the feasibility of the three methods and the performance of corF_sa_SQ outperforms that of the other two methods.Finally, in order to solve the problem of privacy preserving for the Markov event sequence, we introduce the related concepts for privacy preserving. We first give the function of utility gain, and then propose two suppression strategies based on event types (Type_S) and instances (Instance_S) respectively. We implement them by utilizing the corF_Q method. Experiments compare the utility gain and processing time of the two strategies. Type_S has better processing efficency, while Instance_S can achieve higher utility. Therefore, we can choose the reasonable method according to the special scenario.In conclusion, this thesis studies the uncertainty and correlation of data, and then proposes efficient solutions to address the key problems of the composite event detection for the Markov event sequence from three aspects:accuracy matching, similar matching and privacy preserving. Extensive experiments validate the efficiency and accuracy of our methods.