License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.SoCG.2016.61
URN: urn:nbn:de:0030-drops-59539
Go to the corresponding LIPIcs Volume Portal

van Goethem, Arthur ; van Kreveld, Marc ; Löffler, Maarten ; Speckmann, Bettina ; Staals, Frank

Grouping Time-Varying Data for Interactive Exploration

LIPIcs-SoCG-2016-61.pdf (0.6 MB)


We present algorithms and data structures that support the interactive analysis of the grouping structure of one-, two-, or higher-dimensional time-varying data while varying all defining parameters. Grouping structures characterise important patterns in the temporal evaluation of sets of time-varying data. We follow Buchin et al. [JoCG 2015] who define groups using three parameters: group-size, group-duration, and inter-entity distance. We give upper and lower bounds on the number of maximal groups over all parameter values, and show how to compute them efficiently. Furthermore, we describe data structures that can report changes in the set of maximal groups in an output-sensitive manner. Our results hold in R^d for fixed d.

BibTeX - Entry

  author =	{Arthur van Goethem and Marc van Kreveld and Maarten L{\"o}ffler and Bettina Speckmann and Frank Staals},
  title =	{{Grouping Time-Varying Data for Interactive Exploration}},
  booktitle =	{32nd International Symposium on Computational Geometry (SoCG 2016)},
  pages =	{61:1--61:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-009-5},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{51},
  editor =	{S{\'a}ndor Fekete and Anna Lubiw},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{},
  URN =		{urn:nbn:de:0030-drops-59539},
  doi =		{10.4230/LIPIcs.SoCG.2016.61},
  annote =	{Keywords: Trajectory, Time series, Moving entity, Grouping, Algorithm, Data structure}

Keywords: Trajectory, Time series, Moving entity, Grouping, Algorithm, Data structure
Collection: 32nd International Symposium on Computational Geometry (SoCG 2016)
Issue Date: 2016
Date of publication: 10.06.2016

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI