{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T04:36:02Z","timestamp":1750221362929,"version":"3.41.0"},"reference-count":22,"publisher":"Association for Computing Machinery (ACM)","license":[{"start":{"date-parts":[[2017,12,4]],"date-time":"2017-12-04T00:00:00Z","timestamp":1512345600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/501100000923","name":"Australian Research Council","doi-asserted-by":"crossref","award":["DP150101134"],"award-info":[{"award-number":["DP150101134"]}],"id":[{"id":"10.13039\/501100000923","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["ACM J. Exp. Algorithmics"],"published-print":{"date-parts":[[2017,12,15]]},"abstract":"<jats:p>\n            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 a minimal flow diagram. For a large number of state sequences, we show that it is unlikely that efficient algorithms exist. Specifically, the problem is\n            <jats:italic>W<\/jats:italic>\n            [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.\n          <\/jats:p>","DOI":"10.1145\/3150525","type":"journal-article","created":{"date-parts":[[2017,12,4]],"date-time":"2017-12-04T19:18:27Z","timestamp":1512415107000},"page":"1-23","source":"Crossref","is-referenced-by-count":0,"title":["Compact Flow Diagrams for State Sequences"],"prefix":"10.1145","volume":"22","author":[{"given":"Kevin","family":"Buchin","sequence":"first","affiliation":[{"name":"Technische Universiteit Eindhoven, Eindhoven, The Netherlands"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Maike","family":"Buchin","sequence":"additional","affiliation":[{"name":"Ruhr-Universit\u00e4t Bochum, Bochum, Nordrhein-Westfalen, Germany"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Joachim","family":"Gudmundsson","sequence":"additional","affiliation":[{"name":"University of Sydney, Sydney, NSW, Australia"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-6388-9634","authenticated-orcid":false,"given":"Michael","family":"Horton","sequence":"additional","affiliation":[{"name":"University of Sydney and Data61, CSIRO, Sydney, NSW, Australia"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Stef","family":"Sijben","sequence":"additional","affiliation":[{"name":"Ruhr-Universit\u00e4t Bochum, Bochum, Nordrhein-Westfalen, Germany"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2017,12,4]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/2666310.2666415"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/2660772"},{"volume-title":"Proc. IEEE International Conference on Data Mining Workshops, ICDM Workshops. IEEE, 9--14","author":"Bialkowski A.","key":"e_1_2_1_3_1","unstructured":"A. Bialkowski , P. Lucey , G. P. K. Carr , Y. Yue , S. Sridharan , and I. Matthews . 2014b. Identifying team style in soccer using formations learned from spatiotemporal tracking data . In Proc. IEEE International Conference on Data Mining Workshops, ICDM Workshops. IEEE, 9--14 . A. Bialkowski, P. Lucey, G. P. K. Carr, Y. Yue, S. Sridharan, and I. Matthews. 2014b. Identifying team style in soccer using formations learned from spatiotemporal tracking data. In Proc. IEEE International Conference on Data Mining Workshops, ICDM Workshops. IEEE, 9--14."},{"volume-title":"Proc. 8th Annual MIT Sloan Sports Analytics Conference. MIT","author":"Bialkowski A.","key":"e_1_2_1_4_1","unstructured":"A. Bialkowski , P. Lucey , P. Carr , Y. Yue , and I. Matthews . 2014a. Win at home and draw away: Automatic formation analysis highlighting the differences in home and away team behaviors . In Proc. 8th Annual MIT Sloan Sports Analytics Conference. MIT , Boston, MA, 1--7. A. Bialkowski, P. Lucey, P. Carr, Y. Yue, and I. Matthews. 2014a. Win at home and draw away: Automatic formation analysis highlighting the differences in home and away team behaviors. In Proc. 8th Annual MIT Sloan Sports Analytics Conference. MIT, Boston, MA, 1--7."},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1142\/S0218195911003652"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-012-9654-2"},{"key":"e_1_2_1_7_1","first-page":"33","article-title":"Segmenting trajectories: A framework and algorithms using spatiotemporal criteria","volume":"3","author":"Buchin M.","year":"2011","unstructured":"M. Buchin , A. Driemel , M. van Kreveld , and V. Sacristan . 2011 . Segmenting trajectories: A framework and algorithms using spatiotemporal criteria . Journal of Spatial Information Science 3 (2011), 33 -- 63 . M. Buchin, A. Driemel, M. van Kreveld, and V. Sacristan. 2011. Segmenting trajectories: A framework and algorithms using spatiotemporal criteria. Journal of Spatial Information Science 3 (2011), 33--63.","journal-title":"Journal of Spatial Information Science"},{"key":"e_1_2_1_8_1","doi-asserted-by":"crossref","unstructured":"M. Buchin H. Kruckenberg and A. K\u00f6lzsch. 2013. Segmenting trajectories by movement states. In Advances in Spatial Data Handling: Geospatial Dynamics Geosimulation and Exploratory Visualization (SDH). Springer-Verlag Leiden Netherlands 15--25.  M. Buchin H. Kruckenberg and A. K\u00f6lzsch. 2013. Segmenting trajectories by movement states. In Advances in Spatial Data Handling: Geospatial Dynamics Geosimulation and Exploratory Visualization (SDH). Springer-Verlag Leiden Netherlands 15--25.","DOI":"10.1007\/978-3-642-32316-4_2"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-005-0163-7"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.5555\/642129.642130"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/3054132"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.compenvurbsys.2013.09.004"},{"key":"e_1_2_1_13_1","volume-title":"Proc. 14th International Symposium on Advances in Intelligent Data Analysis","volume":"9385","author":"Van Haaren J.","unstructured":"J. Van Haaren , V. Dzyuba , S. Hannosset , and J. Davis . 2015. Automatically discovering offensive patterns in soccer match data . In Proc. 14th International Symposium on Advances in Intelligent Data Analysis , Vol. 9385 . Springer, 286--297. J. Van Haaren, V. Dzyuba, S. Hannosset, and J. Davis. 2015. Automatically discovering offensive patterns in soccer match data. In Proc. 14th International Symposium on Advances in Intelligent Data Analysis, Vol. 9385. Springer, 286--297."},{"key":"e_1_2_1_14_1","first-page":"1","article-title":"Sub-trajectory clustering algorithm based on speed restriction","volume":"37","author":"Han C.-S.","year":"2011","unstructured":"C.-S. Han , S.-X. Jia , L. Zhang , and C.-C. Shu . 2011 . Sub-trajectory clustering algorithm based on speed restriction . Computer Engineering 37 , 7 (2011), 1 -- 3 . C.-S. Han, S.-X. Jia, L. Zhang, and C.-C. Shu. 2011. Sub-trajectory clustering algorithm based on speed restriction. Computer Engineering 37, 7 (2011), 1--3.","journal-title":"Computer Engineering"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/2093973.2094029"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1109\/CVPR.2013.349"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/185675.306789"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0022-0000(03)00078-3"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(81)90075-X"},{"key":"e_1_2_1_20_1","unstructured":"STATS LLC. 2017. STATS SportVU\u00ae Football Player Tracking. Retrieved from https:\/\/www.stats.com\/sportvu-football\/.  STATS LLC. 2017. STATS SportVU\u00ae Football Player Tracking. Retrieved from https:\/\/www.stats.com\/sportvu-football\/."},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/2783258.2788577"},{"volume-title":"Proc. International Conference on Digital Image Computing: Techniques and Applications. IEEE, 1--8.","author":"Wei X.","key":"e_1_2_1_22_1","unstructured":"X. Wei , L. Sha , P. Lucey , S. Morgan , and S. Sridharan . 2013. Large-scale analysis of formations in soccer . In Proc. International Conference on Digital Image Computing: Techniques and Applications. IEEE, 1--8. X. Wei, L. Sha, P. Lucey, S. Morgan, and S. Sridharan. 2013. Large-scale analysis of formations in soccer. In Proc. International Conference on Digital Image Computing: Techniques and Applications. IEEE, 1--8."}],"container-title":["ACM Journal of Experimental Algorithmics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3150525","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3150525","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T02:26:19Z","timestamp":1750213579000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3150525"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017,12,4]]},"references-count":22,"alternative-id":["10.1145\/3150525"],"URL":"https:\/\/doi.org\/10.1145\/3150525","relation":{},"ISSN":["1084-6654","1084-6654"],"issn-type":[{"type":"print","value":"1084-6654"},{"type":"electronic","value":"1084-6654"}],"subject":[],"published":{"date-parts":[[2017,12,4]]}}}