Compact flow diagrams for state sequences

Kevin Buchin, Maike Buchin, Joachim Gudmundsson, Michael Horton, Stef Sijben

Research output: Contribution to journalArticleAcademicpeer-review

Abstract

We introduce the concept of using a flow diagram to compactly represent the segmentation of a large number of state sequences according to a set of criteria. We argue that this flow diagram representation gives an intuitive summary that allows the user to detect patterns within the segmentations. In essence, our aim is to generate a flow diagram with a minimum number of nodes that models a segmentation of the states in the input sequences. For a small number of state sequences we present efficient algorithms to compute aminimal flow diagram. For a large number of state sequences, we show that it is unlikely that efficient algorithms exist. Specifically, the problem is W[1]-hard if the number of state sequences is taken as a parameter. We introduce several heuristics for this problem.We argue about the usefulness of the flow diagram by applying the algorithms to two problems in sports analysis, and evaluate the performance of our algorithms on a football dataset and synthetic data.

Original languageEnglish
Article numbera7
Number of pages23
JournalJournal on Experimental Algorithmics
Volume22
Issue number1
DOIs
Publication statusPublished - 1 Dec 2017

Fingerprint

Dive into the research topics of 'Compact flow diagrams for state sequences'. Together they form a unique fingerprint.

Cite this