Events usually happen within time intervals. Therefore, their computer representations, in terms of data, should be associated with temporal intervals as well. Furthermore, the knowledge extracted from such data can have temporal properties, too. Hence, interest in mining information associated with sequences of temporal intervals has emerged lately.
The problem investigated in this paper is related to arranging temporal intervals for encoded “multiple concurrent labeled events that have a time duration.” After clarifying the concepts of event interval, event-interval sequence, and event arrangement with labels and temporal relations, the authors define the longest common sub-pattern (LCSP) problem specifically. Then, they study algorithms for finding the LCSP shared by two sequences of temporal intervals. They further prove that the precise algorithm for finding LCSP is nondeterministic polynomial-time (NP)-hard, and provide a few approximation algorithms with polynomial time and space. A metric for assessing the quality of approximation is also established and applied in experiments. Among the nine datasets in the experiment, seven were from various application domains such as sign language, medicine, human motion, and sensor networks. Experiments on two synthetic datasets are also provided.
As a matter of fact, the real world is dynamic and consistently changing. Discovered knowledge may only be valid within specified time intervals. In the study of data analysis and knowledge discovery, we should keep knowledge evolution in mind. Furthermore, recent advancements in interval computing and the newly established IEEE 1788-2015 standard for interval arithmetic provide tools for dealing with not only temporal intervals, but also other possible interval-valued attributes in data mining and knowledge discovery.
People working on mining temporal datasets and interval computing may benefit from reading this paper. It provides practical algorithms for searching for LCSP of two sets of time intervals. The authors state that it should have great potential in various kinds of applications. Since this is also a theoretical paper, people working on algorithm and computational complexity may also benefit from reading it.
