Over-the-web retrieval and visualization of massive trajectory sets

Abstract

As the number of cost-effective GPS-supporting devices continues to increase tremendously, the number of recorded trajectories, i.e., measured sequences in time and space, explodes. The enormous potential of this data in terms of information retrieval data mining analysis of various kinds requires advanced storage and retrieval solutions. In [25], Funke et al. presented a data structure Pathfinder (PF) based on a state-of-the-art speed-up technique for shortest path planning allowing for efficient trajectory compression and rather complex query answering. Since PF results are returned in compressed form by default and their complete decompression is only possible with the help of the internal data structure, a separation of a retrieval server and lightweight clients is nontrivial. Even more problematic is the amount of data produced by naively decompressing large queries: transferring the fully unpacked paths is neither meaningful nor feasible taking usual response waiting times into consideration. This work closes the gap by presenting partially decompression and postprocessing methods based on aggregation, pruning, filtering, simplification, and batching in order to accomplish predefined use case goals. The presented methods are theoretically examined, tested on different real-world and synthetic datasets consisting of up to 10 000 000 trajectories, and critically reviewed with regard to applicability. In addition, for the special use case that relies exclusively on spatio- temporally independent queries, a Pathfinder-based static tiling server was included which could be conceptually extended to online tiling for query answering as a prototype showed. [25] S. Funke, T. Rupp, A. Nusser, S. Storandt. “PATHFINDER: Storage and Indexing of Massive Trajectory Sets”. In: Proceedings of the 16th International Symposium on Spatial and Temporal Databases. SSTD ’19. Vienna, Austria: Association for Computing Machinery, 2019, pp. 90–99. isbn: 9781450362801. doi: 10 . 1145 / 3340964 . 3340978 . url: https : //doi.org/10.1145/3340964.3340978 (cit. on pp. 3, 15, 18, 21, 22, 25–27).