Compact flow diagrams for state sequences

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

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

3 Citations (Scopus)

Abstract

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.
Original languageEnglish
Title of host publicationExperimental Algorithms
Subtitle of host publication15th International Symposium, SEA 2016, St. Petersburg, Russia, June 5-8, 2016, Proceedings
Place of PublicationCham
PublisherSpringer
Pages89-104
ISBN (Electronic)978-3-319-38851-9
ISBN (Print)978-3-319-38850-2
DOIs
Publication statusPublished - 2016
EventInternational Symposium on Experimental Algorithms: 15th International Symposium - St. Petersburg, Russian Federation
Duration: 5 Jun 20168 Jun 2016
http://link.springer.com/book/10.1007/978-3-319-38851-9

Publication series

NameLecture Notes in Computer Science
Volume9685

Conference

ConferenceInternational Symposium on Experimental Algorithms
Abbreviated titleSEA 2016
CountryRussian Federation
CitySt. Petersburg
Period5/06/168/06/16
Internet address

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

  • Cite this

    Buchin, K. A., Buchin, M. E., Gudmundsson, J., Horton, M. J., & Sijben, S. (2016). Compact flow diagrams for state sequences. In Experimental Algorithms: 15th International Symposium, SEA 2016, St. Petersburg, Russia, June 5-8, 2016, Proceedings (pp. 89-104). (Lecture Notes in Computer Science; Vol. 9685). Springer. https://doi.org/10.1007/978-3-319-38851-9_7