Analyzing and comparing arrangements of temporal intervals
Loading...
URL
Journal Title
Journal ISSN
Volume Title
School of Science |
Master's thesis
Unless otherwise stated, all rights belong to the author. You may download, display and print this publication for Your own personal use. Commercial use is prohibited.
Authors
Date
2011
Department
Major/Subject
Tietojenkäsittelyteoria
Mcode
T-79
Degree programme
Language
en
Pages
vi + 48
Series
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.Description
Supervisor
Orponen, PekkaThesis advisor
Papapetrou, PanagiotisKeywords
arrangements, temporal intervals, event-interval sequences, distance measure, longest common sub-pattern, LCSP, lower bound