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.
back to list