Compact flow diagrams for state sequences

K.A. Buchin, M.E. Buchin, J. Gudmundsson, M.J. Horton, S. Sijben

Onderzoeksoutput: Hoofdstuk in Boek/Rapport/CongresprocedureConferentiebijdrageAcademicpeer review

3 Citaten (Scopus)

Samenvatting

We introduce the concept of compactly representing a large number of state sequences, e.g., sequences of activities, as a flow diagram. We argue that the flow diagram representation gives an intuitive summary that allows the user to detect patterns among large sets of state sequences. Simplified, our aim is to generate a small flow diagram that models the flow of states of all the state sequences given as input. For a small number of state sequences we present efficient algorithms to compute a minimal flow diagram. For a large number of state sequences we show that it is unlikely that efficient algorithms exist. More specifically, the problem is W[1]-hard if the number of state sequences is taken as a parameter. We thus 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. We evaluate the performance of our algorithms on a football data set and generated data.
Originele taal-2Engels
TitelExperimental Algorithms
Subtitel15th International Symposium, SEA 2016, St. Petersburg, Russia, June 5-8, 2016, Proceedings
Plaats van productieCham
UitgeverijSpringer
Pagina's89-104
ISBN van elektronische versie978-3-319-38851-9
ISBN van geprinte versie978-3-319-38850-2
DOI's
StatusGepubliceerd - 2016
EvenementInternational Symposium on Experimental Algorithms: 15th International Symposium - St. Petersburg, Rusland
Duur: 5 jun 20168 jun 2016
http://link.springer.com/book/10.1007/978-3-319-38851-9

Publicatie series

NaamLecture Notes in Computer Science
Volume9685

Congres

CongresInternational Symposium on Experimental Algorithms
Verkorte titelSEA 2016
LandRusland
StadSt. Petersburg
Periode5/06/168/06/16
Internet adres

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

Citeer dit