Compact flow diagrams for state sequences

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

doi:10.1145/3150525

Compact flow diagrams for state sequences

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

Algorithms

Research output: Contribution to journal › Article › Academic › peer-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 language	English
Article number	a7
Number of pages	23
Journal	Journal on Experimental Algorithmics
Volume	22
Issue number	1
DOIs	https://doi.org/10.1145/3150525
Publication status	Published - 1 Dec 2017

Funding

Joachim Gudmundsson: This research was supported by the Australian Research Council under Grant No. DP150101134 [http://purl.org/au-research/grants/arc/DP150101134]. Authors’ addresses: K. Buchin, Department of Mathematics and Computer Science, Technische Universiteit Eindhoven, Eindhoven, The Netherlands; email: [email protected]; M. Buchin, Department of Mathematics, Ruhr-Universitat Bochum, Bochum, Nordrhein-Westfalen, Germany; email: [email protected]; J. Gudmundsson, School of Information Technologies, University of Sydney, Sydney, NSW, Australia; email: [email protected]; M. Horton, School of Information Technologies, University of Sydney, Sydney, NSW, Australia; email: [email protected], Data61, CSIRO, Sydney, NSW, Australia; S. Sijben, Department of Mathematics, Ruhr-Universitat Bochum, Bochum, Nordrhein-Westfalen, Germany; email: [email protected]. Permission to make digital or hard copies of part or all of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies show this notice on the first page or initial screen of a display along with the full citation. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, to republish, to post on servers, to redistribute to lists, or to use any component of this work in other works requires prior specific permission and/or a fee. Permissions may be requested from Publications Dept., ACM, Inc., 2 Penn Plaza, Suite 701, New York, NY 10121-0701 USA, fax +1 (212) 869-0481, or [email protected]. ©c 2017 ACM 1084-6654/2017/12-ART1.7 $15.00 DOI: https://doi.org/10.1145/3150525 Fig. 1. The input is (a) a set T = {τ1,... ,τm} of sequences of states and (b) a set of criteria C = {C1,..., Ck}. (c) The criteria partition the states into a segmentation. (d) One possible flow diagram representing a valid segmentation of T according to C, with the s–t path for Person 1 (highlighted in red).

Access to Document

10.1145/3150525

Cite this

@article{b4443a5d52b4464e97ae6a92a06d8f9b,

title = "Compact flow diagrams for state sequences",

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.",

author = "Kevin Buchin and Maike Buchin and Joachim Gudmundsson and Michael Horton and Stef Sijben",

year = "2017",

month = dec,

day = "1",

doi = "10.1145/3150525",

language = "English",

volume = "22",

journal = "Journal on Experimental Algorithmics",

issn = "1084-6654",

publisher = "Association for Computing Machinery, Inc.",

number = "1",

}

TY - JOUR

T1 - Compact flow diagrams for state sequences

AU - Buchin, Kevin

AU - Buchin, Maike

AU - Gudmundsson, Joachim

AU - Horton, Michael

AU - Sijben, Stef

PY - 2017/12/1

Y1 - 2017/12/1

N2 - 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.

AB - 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.

UR - https://www.scopus.com/pages/publications/85038915355

U2 - 10.1145/3150525

DO - 10.1145/3150525

M3 - Article

AN - SCOPUS:85038915355

SN - 1084-6654

VL - 22

JO - Journal on Experimental Algorithmics

JF - Journal on Experimental Algorithmics

IS - 1

M1 - a7

ER -

Compact flow diagrams for state sequences

Abstract

Funding

Access to Document

Other files and links

Fingerprint

Cite this