Compact flow diagrams for state sequences

DOI10.1145/3150525zbMATH Open1414.68038arXiv1602.05622OpenAlexW3121764566MaRDI QIDQ4577949FDOQ4577949

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

Publication date: 6 August 2018

Published in: ACM Journal of Experimental Algorithmics (Search for Journal in Brave)

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.

Full work available at URL: https://arxiv.org/abs/1602.05622

Recommendations

• A heuristic algorithm for drawing of a flow diagram
• scientific article; zbMATH DE number 2042670
• scientific article; zbMATH DE number 1983058
• scientific article; zbMATH DE number 2182443
• Enumeration of structured flowcharts

zbMATH Keywords

network analysisfootballexperimentalflow networkssports analyticsstate sequencegroup segmentation

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Nonnumerical algorithms (68W05)

Cites Work

• On the hardness of approximating minimization problems
• On the parameterized complexity of the fixed alphabet shortest common supersequence and longest common subsequence problems
• Detecting commuting patterns by clustering subtrajectories
• The shortest common supersequence problem over binary alphabet is NP- complete
• Title not available (Why is that?)
• Segmentation of trajectories on non-monotone criteria
• Median trajectories

Cited In (2)

• Synthesizing OMT state diagrams
• Fréchet Distance for Uncertain Curves

This page was built for publication: Compact flow diagrams for state sequences

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4577949)