Our VGIscience paper PATHFINDER has been accepted at the SSTD 2019. PATHFINDER is a index structure which is based on the state-of-the-art speed-up technique Contraction-Hierarchy (CH) for shortest path planning and allows to both compress and access huge amounts of trajectory data. For our performance evaluation experiments, we extracted a fine-grained transportation network of europe with over a billion edges from OSM data. With a dataset of millions of synthesized trajectories on this graph, PATHFINDER then allows to retrieve all trajectories within a given space-time cube in a few microseconds per reported trajectory. We also ran smaller experiments on 350.000 real trajectories which we gained from map-matching the openly available GPS-traces of the OSM project on our transportation network graphs.

PATHFINDER achieves its high performance by utilizing the structure of the CH in two ways: Firstly, it makes use of its so-called shortcut edges to compress the trajectories. Secondly, it employs its hierarchical structure to decompose the search space.