TIRPClo: efficient and complete mining of time intervals-related patterns

Abstract

Mining frequent Time Intervals-Related Patterns (TIRPs) from series of symbolic time intervals offers a comprehensive framework for heterogeneous, multivariate temporal data analysis in various application domains. While gaining a growing interest in recent decades, the efficient mining of frequent TIRPs is still a high computational challenge which has also not yet been investigated in its full complexity. The majority of previous methods discover only the first instances of the TIRPs within each series of symbolic time intervals, whereas their re-occurring instances are ignored. This eventually results in an incomplete discovery of frequent TIRPs, a problem that lies also in the challenge of mining only the frequent closed TIRPs, which was only recently investigated for the first time. In this paper, we introduce TIRPClo—an efficient algorithm for the complete mining of either the entire set of frequent TIRPs, or only the frequent closed TIRPs. The algorithm proposes a non-ambiguous sequential representation of symbolic time intervals series through the intervals’ end-points, as well as a memory-efficient index and a novel method for data projection, due to which it is the first algorithm to guarantee a complete discovery of frequent closed TIRPs. The experimental evaluation conducted on eleven real-world and four synthetic datasets demonstrates that TIRPClo is up to 10 times faster when mining the entire set of frequent TIRPs, and up to more than 100 times faster when mining only the frequent closed TIRPs compared to four state-of-the-art methods, while also reporting lower memory measurements.

Appendices

Appendix A: Real-world datasets

Detailed information is provided on the real-world datasets which have been used to evaluate the proposed TIRPClo algorithm (datasets 1–11 in Table 1).

• American Sign Language (ASL) The dataset was created by the National Center for Sign Language and Gesture Resources at Boston University (Papapetrou et al. 2009). It consists of a collection of 884 utterances, in which each utterance associates a segment of video with a detailed transcription and contains several ASL gestures and grammatical fields (e.g., eyebrow raised, head tilted forward) occurring over a time interval.

• Diabetes The dataset was provided by Moskovitch and Shahar (2015c) as part of a collaboration with Clalit Health Services (Israel’s largest HMO). It contains data on 2038 patients having type II diabetes, collected monthly from 2002 to 2007. The dataset contains six variables recorded over time for each patient: hemoglobin-A1c values, blood glucose levels, cholesterol values, and several medications the patients purchased: diabetic (insulin-based) medications, cholesterol reducing statins, and beta blockers.

• MavLab Smart-home The dataset was provided by Jakkula and Cook (2011). It contains data from the readings of ninety-nine sensors installed in a computerized apartment, describing the activity of people and various appliances scattered around the apartment.

• ASL-BU (Mörchen and Fradkin 2010) The dataset contains STIs which are transcriptions from videos of American Sign Language expressions. An entity’s series of STIs represents a single sentence.

• ASL-GT (Mörchen and Fradkin 2010) STIs were derived from sixteen dimensional numerical time series with features extracted from videos of American Sign Language expressions. The dataset includes a larger number of entities’ STIs series and a smaller number of symbol types compared to the previous dataset.

• Auslan2 (Mörchen and Fradkin 2010) STIs were derived from the publicly available Australian Sign Language dataset in the UCI repository. An entity’s series of STIs represents a single word.

• Blocks (Mörchen and Fradkin 2010) Contains STIs which represent visual primitives drawn from videos of a human hand stacking colored blocks. An entity’s STIs series represents one of eight different scenarios including either atomic actions (e.g., move-right) or complete scenarios (e.g., assemble).

• Context (Mörchen and Fradkin 2010) STIs were derived from categorical and numerical data that describe the context of a mobile device carried by humans in different situations. An entity’s series of STIs represents one of five scenarios (e.g., meeting or street).

• Pioneer (Mörchen and Fradkin 2010) STIs were derived from the Pioneer-1 dataset in the UCI repository, which contains data collected from sensor readings of the Pioneer-1 mobile robot. An entity’s STIs series describes one of the robot’s three moving scenarios—either gripper, move or turn.

• Skating (Mörchen and Fradkin 2010) The dataset contains STIs derived from fourteen dimensional numerical time series, which describe the muscle activity and leg position of six professional In-Line Speed Skaters during controlled tests. An entity’s series of STIs describes a complete movement cycle.

• Hepatitis (Patel et al. 2008) The dataset contains STIs describing tests conducted to patients suffering from either Hepatitis B or C over a time period of 10 years. An entity’s STIs series represents the tests conducted to a single patient.

Appendix B: Distribution of time gaps between non-overlapping STIs

Figure 18 shows the distribution of time durations of the before temporal relation, i.e., the time gaps between non-overlapping pairs of STIs, in the ASL, diabetes, smart-home, context, and pioneer datasets which have been used for the maximal gap analysis in experiment 5.

Fig. 18

Histograms showing the distribution of time durations of the before temporal relation, i.e., the time gaps between non-overlapping pairs of STIs in the datasets used for the maximal gap analysis in experiment 5

Appendix C: Worst-case complexity analysis of sequential pattern mining

In Sect. 3.6.2, a simplified worst-case assessment of the complexity of the proposed TIRPClo algorithm, as a representative of sequence-based TIRP mining methods, was provided. In this appendix, we follow similar notations to those introduced in Sect. 3.6.2, and also concisely assess the complexity of the more basic task of sequential pattern mining.

Assume:

• S—number of event-types

• N—total number of events in the dataset

• n—maximal number of events within an entities’ event-sequence

• L—maximal number of events within a frequent sequential pattern

In sequential pattern mining, both the input data and the discovered patterns only consist of time point-based events. Thus, the discovery of a k-sized sequential pattern requires k pattern extension steps, i.e., by a single event at a time, while having at most S candidates generated in each step, given a total of S event-types or symbols. That is unlike in sequence-based TIRP mining, where the input STIs data are broken into their start and finish tieps, which consequently doubles the number of pattern extension steps required to discover a k-sized TIRP as well as the maximal number of generated candidates, as described in Sect. 3.6.2. Hence, including the initial sorting of entities’ event-sequences, the overall time complexity of the more basic task of sequential pattern mining can be typically assessed by $O(N\cdot S^{L}+n\cdot log(n))$ in the worst-case.