Grouping Time-varying Data for Interactive Exploration

Abstract

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 characterize 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 \(\mathbb{R}^d\) for fixed \(d\).

Corresponding Publications

Grouping Time-varying Data for Interactive Exploration

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

Proc. 32th Annual Symposium on Computational Geometry, 2016

Download Local Copy View Slides Export Citation 
@inproceedings{cake2016,
  author = {van Goethem, Arthur and van Kreveld, Marc and L{\"o}ffler, Maarten
                 and Speckmann, Bettina and Staals, Frank},
  title = {Grouping Time-varying Data for Interactive Exploration},
  booktitle = {Proc. 32th Annual Symposium on Computational Geometry},
  year = {2016},
  pages = {61:1--61:16},
  isbn = {978-3-95977-009-5},
  issn = {1868-8969},
  volume = {51},
  url = {https://dx.doi.org/10.4230/LIPIcs.SoCG.2016.61},
  doi = {10.4230/LIPIcs.SoCG.2016.61},
  editor = {S{\'a}ndor Fekete and Anna Lubiw},
  location = {Boston, USA},
  numpages = {16},
  keywords = {trajectories, grouping, moving entity, data structures},
  category = {trajectories},
  series = {Leibniz International Proceedings in Informatics (LIPIcs)},
  publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
}

Grouping Time-varying Data for Interactive Exploration

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

Abstr. 32th European Workshop on Computational Geometry (EuroCG), 2016

Download Local Copy View Slides Export Citation 
@article{cake_eurocg2016,
  author = {van Goethem, Arthur and Van Kreveld, Marc and L{\"o}ffler, Maarten
                 and Speckmann, Bettina and Staals, Frank},
  title = {Grouping Time-varying Data for Interactive Exploration},
  journal = {Abstr. 32th European Workshop on Computational Geometry (EuroCG)},
  year = {2016},
  location = {Lugano, Switzerland},
  numpages = {4},
  category = {trajectories},
  project = {cake2016},
  url = {http://www.eurocg2016.usi.ch/sites/default/files/paper_48.pdf},
}