DISCOVERING TIMED SEQUENTIAL PATTERNS FROM STATIC AND DYNAMIC TIMED SEQUENCE DATABASES

Abstract

Mining sequential patterns is one of the data mining tasks that aims to find the subsequences that frequently occur in a specific timestamp order within a sequence database. For example, a patient’s health history database is a type of sequence database that records medical events (such as diagnoses and treatments) in chronological order. Discovering sequential patterns in such a database can help predict the symptoms of an impending heart attack, assist healthcare providers with diagnosis, enable timely treatment, and facilitate early intervention in critical cases. However, clinical decision-making requires not only pattern identification but also precise temporal forecasting of when symptoms may occur. This necessitates the discovery of sequential patterns that incorporate temporal information, referred to as timed sequential patterns (TSP). For example, patients typically develop high cholesterol first; within three to four days, this progresses to high blood pressure, followed by elevated body temperature after another one to two days. Ultimately, a heart attack may occur within the following one to two months. Identifying interesting, useful, and temporally accurate patterns is valuable for many real-world applications, such as illness symptom prediction, weather forecasting, and transportation and arrival time analysis. While several approaches have been proposed for mining sequential patterns, most overlook the temporal relationships between the events in the subsequence. As a result, they fail to discover patterns that include this critical temporal information. To address this, some studies have incorporated temporal information into sequential patterns; however, challenges remain. For instance, some approaches require users to provide time-related inputs to identify temporal relations, rather than enabling algorithms to discover them automatically. Others consider only the first occurrence of a pattern when calculating temporal relations, ignoring other possible occurrences in the database. Furthermore, most existing sequential pattern mining algorithms assume static databases, despite the inherently dynamic nature of real-world data, which undergoes frequent insertions, deletions, and modifications. The dynamic nature complicates the efficient discovery of a complete set of sequential patterns without re-scanning the entire database. The problem is compounded by the accelerating growth of databases due to the widespread use of tracking devices, increased social media activity, and the general rise in stored data. Therefore, there is an increasing need for efficient and scalable algorithms that leverage parallelism to manage this rapid expansion effectively. This dissertation addresses these challenges through three novel algorithms: Minits+, Minits-AllOcc, and MinitsDays. Minits+ and Minits-AllOcc are designed to identify frequent timed sequential patterns in static sequence databases. While Minits+ does not consider all possible occurrences of a pattern, Minits-AllOcc does. MinitsDays, on the other hand, efficiently discovers frequent timed sequential patterns in dynamic sequence databases without requiring a complete database rescan. Due to the large scale of sequence data, significant computational power is required. To ensure scalability, parallelized versions, MMinits+, MMinits-AllOcc, and MMinitsDays, were developed for multi-core architectures. To evaluate the effectiveness and efficiency of the proposed algorithms, extensive theoretical and experimental evaluations conducted using both real-world and synthetic datasets under various parameters. The results demonstrate that the algorithms can efficiently discover accurate frequent timed sequential patterns. Minits+ outperformed the existing timed sequential pattern mining algorithm SID-PrefixSpan by 9% in execution time, while MinitsDays showed a 42% improvement over Minits-AllOcc. The parallel multi-core versions, MMinits+, MMinits-AllOcc, and MMinitsDays, achieved an average execution time improvement of 50% compared to their single-core counterparts.