Analyzing and comparing arrangements of temporal intervals

Abstract

This thesis focuses on comparing and analysing arrangements of temporal intervals. Such arrangements are sets of concurrent events that are not instantaneous, but are characterized by duration.

We study two major problems. The first problem is comparing arrangements of event-intervals and acquiring their distance. To the best of our knowledge, we are the first to formally define the problem. Furthermore, we present three polynomial-time distance functions which we study and benchmark through rigorous experimentation. The proposed methods were tested on three datasets: American Sign Language utterances, sensor data and Hepatitis patient data.

In addition, we provide a linear-time lower bound for one of the distance measures. The distance measures can be applied to event-interval sequences, too. In this case, neither the event-interval durations nor the absolute time values are considered.

The second problem which we study is finding the longest common sub-pattern (LCSP) of arrangements of temporal intervals. We prove hardness results for the problem and devise an exact algorithm for computing the LCSP of pairs of arrangements.