Change search
ReferencesLink to record
Permanent link

Direct link
Finding the longest common sub-pattern in sequences of temporal intervals
Stockholm University, Faculty of Social Sciences, Department of Computer and Systems Sciences.
Number of Authors: 2
2015 (English)In: Data mining and knowledge discovery, ISSN 1384-5810, E-ISSN 1573-756X, Vol. 29, no 5, 1178-1210 p.Article in journal (Refereed) Published
Abstract [en]

We study the problem of finding the longest common sub-pattern (LCSP) shared by two sequences of temporal intervals. In particular we are interested in finding the LCSP of the corresponding arrangements. Arrangements of temporal intervals are a powerful way to encode multiple concurrent labeled events that have a time duration. Discovering commonalities among such arrangements is useful for a wide range of scientific fields and applications, as it can be seen by the number and diversity of the datasets we use in our experiments. In this paper, we define the problem of LCSP and prove that it is NP-complete by demonstrating a connection between graphs and arrangements of temporal intervals. This connection leads to a series of interesting open problems. In addition, we provide an exact algorithm to solve the LCSP problem, and also propose and experiment with three polynomial time and space under-approximation techniques. Finally, we introduce two upper bounds for LCSP and study their suitability for speeding up 1-NN search. Experiments are performed on seven datasets taken from a wide range of real application domains, plus two synthetic datasets. Lastly, we describe several application cases that demonstrate the need and suitability of LCSP.

Place, publisher, year, edition, pages
2015. Vol. 29, no 5, 1178-1210 p.
Keyword [en]
Temporal intervals, Longest common sub-pattern, Event-interval sequences
National Category
Computer and Information Science
URN: urn:nbn:se:su:diva-120891DOI: 10.1007/s10618-015-0404-3ISI: 000359996900004OAI: diva2:860539
Available from: 2015-10-12 Created: 2015-09-18 Last updated: 2015-10-12Bibliographically approved

Open Access in DiVA

No full text

Other links

Publisher's full text

Search in DiVA

By author/editor
Papapetrou, Panagiotis
By organisation
Department of Computer and Systems Sciences
In the same journal
Data mining and knowledge discovery
Computer and Information Science

Search outside of DiVA

GoogleGoogle Scholar
The number of downloads is the sum of all downloads of full texts. It may include eg previous versions that are now no longer available

Altmetric score

Total: 10 hits
ReferencesLink to record
Permanent link

Direct link