Time: 1:00pm Tuesday, 17th May 2016.
Location: SIT 459
Speaker: Michael Horton, University of Sydney
Title: Compact Flow Diagrams for State Sequences
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 to compute a flow diagram of minimum size exist. More specifically, the problem is W-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.
This is joint work with:
Kevin Buchin — TU Eindhoven
Maike Buchin and Stef Sijben — Ruhr-Universität Bochum
Joachim Gudmundsson — The University of Sydney