Document Open Access Logo

Grouping Time-Varying Data for Interactive Exploration

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

PDF
Thumbnail PDF

File

LIPIcs.SoCG.2016.61.pdf
  • Filesize: 0.61 MB
  • 16 pages

Document Identifiers

Author Details

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

Cite As Get BibTex

Arthur van Goethem, Marc van Kreveld, Maarten Löffler, Bettina Speckmann, and Frank Staals. Grouping Time-Varying Data for Interactive Exploration. In 32nd International Symposium on Computational Geometry (SoCG 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 51, pp. 61:1-61:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016) https://doi.org/10.4230/LIPIcs.SoCG.2016.61

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 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.

Subject Classification

Keywords
  • Trajectory
  • Time series
  • Moving entity
  • Grouping
  • Algorithm
  • Data structure

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. P. Agarwal and J. Matoušek. On Range Searching with Semialgebraic Sets. Disc. &Comput. Geom., 11(4):393-418, 1994. Google Scholar
  2. N. Amato, M. Goodrich, and E. Ramos. Computing the arrangement of curve segments: Divide-and-conquer algorithms via sampling. In Proc. 11th ACM-SIAM Symp. on Disc. Algorithms, pages 705-706, 2000. Google Scholar
  3. G. Andrienko, N. Andrienko, and S. Wrobel. Visual analytics tools for analysis of movement data. ACM SIGKDD Explorations Newsletter, 9(2):38-46, 2007. Google Scholar
  4. M. Bender and M. Farach-Colton. The LCA problem revisited. In LATIN 2000: Theoret. Informatics, volume 1776 of LNCS, pages 88-94. Springer, 2000. Google Scholar
  5. M. Bender and M. Farach-Colton. The level ancestor problem simplified. Theoret. Computer Science, 321(1):5-12, 2004. Google Scholar
  6. M. Benkert, B. Djordjevic, J. Gudmundsson, and T. Wolle. Finding popular places. Int. J. of Comput. Geom. &Appl., 20(1):19-42, 2010. Google Scholar
  7. P. Bovet and S. Benhamou. Spatial analysis of animals' movements using a correlated random walk model. J. of Theoret. Biology, 131(4):419-433, 1988. Google Scholar
  8. K. Buchin, M. Buchin, M. van Kreveld, M. Löffler, R. Silveira, C. Wenk, and L. Wiratma. Median trajectories. Algorithmica, 66(3):595-614, 2013. Google Scholar
  9. K. Buchin, M. Buchin, M. van Kreveld, B. Speckmann, and F. Staals. Trajectory grouping structure. J. of Comput. Geom., 6(1):75-98, 2015. Google Scholar
  10. T. Chan. A dynamic data structure for 3-d convex hulls and 2-d nearest neighbor queries. J. of the ACM, 57(3):16:1-16:15, 2010. Google Scholar
  11. B. Chazelle, L. Guibas, and D. Lee. The power of geometric duality. BIT Numerical Mathematics, 25(1):76-90, 1985. Google Scholar
  12. D. Eppstein, M. Goodrich, and J. Simons. Set-difference range queries. In Proc. 2013 Canadian Conf. on Comput. Geom., 2013. Google Scholar
  13. A. Fujimura and K. Sugihara. Geometric analysis and quantitative evaluation of sport teamwork. Systems and Computers in Japan, 36(6):49-58, 2005. Google Scholar
  14. J. Gudmundsson, M. van Kreveld, and B. Speckmann. Efficient detection of patterns in 2D trajectories of moving points. GeoInformatica, 11:195-215, 2007. Google Scholar
  15. J. Gudmundsson, M. van Kreveld, and F. Staals. Algorithms for hotspot computation on trajectory data. In Proc. 21st ACM SIGSPATIAL GIS, pages 134-143, 2013. Google Scholar
  16. D. Keim, G. Andrienko, J.-D. Fekete, C. Görg, J. Kohlhammer, and G. Melançon. Visual analytics: Definition, process, and challenges. In A. Kerren, J. Stasko, J.-D. Fekete, and C. North, editors, Information Visualization, volume 4950 of LNCS, pages 154-175. Springer, 2008. Google Scholar
  17. I. Kostitsyna, M. van Kreveld, M. Löffler, B. Speckmann, and F. Staals. Trajectory grouping structure under geodesic distance. In Proc. 31th Symp. Computat. Geom. Lipics, 2015. Google Scholar
  18. X. Li, X. Li, D. Tang, and X. Xu. Deriving features of traffic flow around an intersection from trajectories of vehicles. In Proc. IEEE 18th Int. Conf. Geoinformatics, pages 1-5, 2010. Google Scholar
  19. J. Matoušek. Efficient partition trees. Disc. &Comput. Geom., 8(3):315-334, 1992. Google Scholar
  20. M. Mirzargar, R. Whitaker, and R. Kirby. Curve Boxplot: generalization of Boxplot for ensembles of curves. IEEE Trans. on Vis. and Comp. Graphics, 20(12):2654-2663, 2014. Google Scholar
  21. A. Stohl. Computation, accuracy and applications of trajectories - a review and bibliography. Atmospheric Environment, 32(6):947-966, 1998. Google Scholar
  22. Arthur van Goethem, Marc van Kreveld, Maarten Löffler, Bettina Speckmann, and Frank Staals. Grouping time-varying data for interactive exploration. CoRR, abs/1603.06252, 2016. Google Scholar
  23. A. Yao. On constructing minimum spanning trees in k-dimensional spaces and related problems. SIAM J. Comput., 11(4):721-736, 1982. Google Scholar
  24. D. Yellin. Representing sets with constant time equality testing. J. of Algorithms, 13(3):353-373, 1992. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact