VGIscience

Dynamic and Customizable Exploitation of Trajectory Data (Trajectories 2)

  • Timon Behr
    Timon Behr
    Konstanz
  • Stefan Funke
    Stuttgart
  • Sabine Storandt
    Sabine Storandt
    Konstanz
  • Claudius Proissl
    Stuttgart
Trajectories 2

In the first phase we developed novel techniques to index massive amounts of trajectory data, robustly map match raw location measurements and solve fundamental problems in the map visualization domain. The second phase delved further into these topics, here we describe some selected contributions:

Map Matching with unrestricted Trajectories

We investigated how unrestricted trajectories can be dealt with, i.e., trajectories which are not confined to an underlying transportation network. In [6] we developed an approach that efficiently and reliably computes concise representations of such trajectories that maintain their semantic characteristics. Our approach utilizes OpenStreetMap data to not only extract the network but also areas that allow for free movement (as e.g. parks) as well as obstacles (as e.g. buildings).

IMAGE

Figure: Set of trajectories (dashed blue lines) traversing the same free space. The yellow edges indicate their matched paths. Lower left: Trajectory (blue crosses) following the shore line of the lake. The Baseline+ approach matches this trajectory to rather far apart paths as well as several groynes, while the tessellation based approach produces a more sensible match. Right: In the absence of sufficient tessellation edges, a trajectory traversing a large free space might end up being matched to a path with a rather large detour.

Preference-based Trajectory Clustering

In a road network with multicriteria edge costs we considered the problem of computing a minimum number of driving preferences such that a given set of paths/trajectories is optimal under at least one of these preferences. While the exact formulation and solution of this problem appears theoretically hard, we showed in [2] that in practice one can solve the problem exactly even for non-homeopathic instance sizes of several thousand trajectories in a road network of several million nodes. We also presented a parameterized guaranteed-polynomial-time scheme with very good practical performance. The key of our approach is to rephrase the problem as a geometric hitting set problem on preference polyhedra:

IMAGE

Distance Closures: Unifying Search- and Lookup-based Shortest Path Speedup Techniques

Most popular speed-up techniques for shortest path queries in road networks are based either on pruned graph search or clever lookup schemes and allow for answering of shortest path distance queries within continent-sized road networks in less than a milli-(search-based) or even microsecond (lookup-based) compared to several seconds of a normal Dijkstra run. While both paradigms previously have been considered mostly separately, in [3] we presented a framework that unifies these seemingly different views on shortest path computations. Apart from the conceptual novelty, this allows for new and (practically very attractive) space-time tradeoffs for shortest-path computation. To our knowledge we were also the first to report on computational results for the largest connected component of the Open-StreetMap planet road network with more than half a billion nodes.

Visualization of Trajectory and Road Network Data

In [4], we considered the problem of gradual road network simplification, where given an embedded road network the goal is to compute a fine-grained succession of simplifications with decreasing level-of-detail. This allows to render the network on any desired zoom level or with a user-defined number of segments. Previous work has established that this can be achieved based on a Contraction Hierarchies (CH) data structure. CH was originally developed as a graph preprocessing method to speed up shortest path planning in road networks. However, since it is inherently based on a graph simplification mechanism, it can also serve as a basis for rendering. But the existing method exhibits several shortcomings, for example, topological inconsistencies arise on many simplification levels and the preservation of the shape of routes and the overall network for coarser graph representations is insufficient. This severely impairs the navigability of the map. We significantly improved upon the existing method by modifying the CH construction process as well as the rendering algorithm.

IMAGE

Figure: Road Network Simplification. a): Germany, all roads (about 50 million segments), b): Germany simplified (about 130,000 segments). c): Metropolitan area of Stuttgart, full detail (top) vs simplified (bottom). d): Silhouette shrinking problem.

Similar techniques can also be instrumented for the visualization of massive trajectory sets as they occur, e.g., as output of the trajectory indexing data structures developed in the first phase of our project, as was shown in [5]:

IMAGE

Publications

  1. Barth, F., Funke, S., Jepsen, T. S., & Proissl, C. (2020). Scalable unsupervised multi-criteria trajectory segmentation and driving preference mining. Proceedings of the 9th ACM SIGSPATIAL International Workshop on Analytics for Big Geospatial Data, 1–10.
  2. Barth, F., Funke, S., & Proissl, C. (2021). Preference-based Trajectory Clustering: An Application of Geometric Hitting Sets. 32nd International Symposium on Algorithms and Computation (ISAAC 2021).
  3. Bahrdt, D., Funke, S., Makolli, S., & Proissl, C. (2022). Distance Closures: Unifying Search- and Lookup-based Shortest Path Speedup Techniques. 2022 Proceedings of the Twenty-Fourth Workshop on Algorithm Engineering and Experiments (ALENEX).
  4. Baur, L., Funke, S., Rupp, T., & Storandt, S. (2022). Gradual road network simplification with shape and topology preservation. SIGSPATIAL/GIS, 52:1–52:4.
  5. Baur, L., Funke, S., & Rupp, T. (2022). PathfinderVis. SIGSPATIAL/GIS, 55:1–55:4.
  6. Behr, T., van Dijk, T. C., Forsch, A., Haunert, J.-}H., & Storandt, S. (2021). Map Matching for Semi-Restricted Trajectories. GIScience (II), 208, 12:1–12:16.
  7. Beck, M., Spoerhase, J., & Storandt, S. (2023). Mind the Gap: Edge Facility Location Problems in Theory and Practice. CALDAM, 13947, 321–334.
  8. Li, R., Storandt, S., Müller, U., & Weber, D. (2021). Barrier-Free Pedestrian Routing with Contraction Hierarchies. SIGSPATIAL/GIS, 668–669.
  9. Abeywickrama, T., Cheema, M. A., & Storandt, S. (2021). Hierarchical Graph Traversal for Aggregate k Nearest Neighbors Search in Road Networks (Extended Abstract). IJCAI, 4730–4734.