Grouping Time-varying Data for Interactive Exploration

Time-varying data (e.g., trajectories, time-series, and ensembles) describe for a set of entities how their governing variables (e.g., location or temperature) change over time. There is a large body of algorithms research on finding patterns in such data. Many of these algorithms involve several parameters that define what constitutes a pattern. Unfortunately, there is often no a priori knowledge on the correct parameter values to use for a specific data set. To find a fitting setting interactive exploration of the data is required. It is therefore important that the algorithms support changing their parameters efficiently. We study this problem for the case of finding maximal groups, as defined by Buchin et al. Groups are sufficiently large sets of entities that move together during a sufficiently long time interval. As a consequence we have three parameters: group-size, group-duration, and inter-entity distance. We bound the number of maximal groups over all parameter values, and show how to compute them efficiently. Furthermore, we show how to store maximal groups to allow reporting the changes in the set of maximal groups in an output-sensitive manner. Our results apply to entities moving in arbitrary, but constant, dimension d.

keywords: Computational Geometry, Data Structures, Geographical Information Analysis, Trajectories

Conference Proceedings (peer-reviewed)

Arthur van Goethem, Bettina Speckmann, Frank Staals, Maarten Löffler, Marc van Kreveld
Grouping Time-varying Data for Interactive Exploration
Proc. 32nd International Symposium on Computational Geometry
LIPIcs, 51, 61:1–61:16, 2016
http://drops.dagstuhl.de/opus/volltexte/2016/5953

Workshop or Poster (weakly reviewed)

Arthur van Goethem, Bettina Speckmann, Frank Staals, Maarten Löffler, Marc van Kreveld
Grouping Time-varying Data for Interactive Exploration
Proc. 32nd European Workshop on Computational Geometry
7–10, 2016

Archived Publication (not reviewed)

Arthur van Goethem, Bettina Speckmann, Frank Staals, Maarten Löffler, Marc van Kreveld
Grouping Time-varying Data for Interactive Exploration
1603.06252, 2016
http://arXiv.org/abs/1603.06252

back to list