Dynamic and Customizable Exploitation of Trajectory Data (Trajectories 2)

Timon Behr
Konstanz 
Stefan Funke
Stuttgart 
Sabine Storandt
Konstanz 
Claudius Proissl
Stuttgart
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).
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.
Preferencebased 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 nonhomeopathic instance sizes of several thousand trajectories in a road network of several million nodes. We also presented a parameterized guaranteedpolynomialtime 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:
Distance Closures: Unifying Search and Lookupbased Shortest Path Speedup Techniques
Most popular speedup 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 continentsized road networks in less than a milli(searchbased) or even microsecond (lookupbased) 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) spacetime tradeoffs for shortestpath computation. To our knowledge we were also the first to report on computational results for the largest connected component of the OpenStreetMap 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 finegrained succession of simplifications with decreasing levelofdetail. This allows to render the network on any desired zoom level or with a userdefined 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.
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]:
Publications
 Barth, F., Funke, S., Jepsen, T. S., & Proissl, C. (2020). Scalable unsupervised multicriteria trajectory segmentation and driving preference mining. Proceedings of the 9th ACM SIGSPATIAL International Workshop on Analytics for Big Geospatial Data, 1–10.
 Barth, F., Funke, S., & Proissl, C. (2021). Preferencebased Trajectory Clustering: An Application of Geometric Hitting Sets. 32nd International Symposium on Algorithms and Computation (ISAAC 2021).
 Bahrdt, D., Funke, S., Makolli, S., & Proissl, C. (2022). Distance Closures: Unifying Search and Lookupbased Shortest Path Speedup Techniques. 2022 Proceedings of the TwentyFourth Workshop on Algorithm Engineering and Experiments (ALENEX).
 Baur, L., Funke, S., Rupp, T., & Storandt, S. (2022). Gradual road network simplification with shape and topology preservation. SIGSPATIAL/GIS, 52:1–52:4.
 Baur, L., Funke, S., & Rupp, T. (2022). PathfinderVis. SIGSPATIAL/GIS, 55:1–55:4.
 Behr, T., van Dijk, T. C., Forsch, A., Haunert, J.}H., & Storandt, S. (2021). Map Matching for SemiRestricted Trajectories. GIScience (II), 208, 12:1–12:16.
 Beck, M., Spoerhase, J., & Storandt, S. (2023). Mind the Gap: Edge Facility Location Problems in Theory and Practice. CALDAM, 13947, 321–334.
 Li, R., Storandt, S., Müller, U., & Weber, D. (2021). BarrierFree Pedestrian Routing with Contraction Hierarchies. SIGSPATIAL/GIS, 668–669.
 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.