Compact flow diagrams for state sequences

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

Onderzoeksoutput: Bijdrage aan tijdschriftTijdschriftartikelAcademicpeer review

Samenvatting

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.

Originele taal-2Engels
Artikelnummera7
Aantal pagina's23
TijdschriftJournal on Experimental Algorithmics
Volume22
Nummer van het tijdschrift1
DOI's
StatusGepubliceerd - 1 dec 2017

Vingerafdruk

Duik in de onderzoeksthema's van 'Compact flow diagrams for state sequences'. Samen vormen ze een unieke vingerafdruk.

Citeer dit