Optimized path dataset representation

Abstract

Path-based data is increasingly used in mobility applications. This type of data has multiple uses, among them studying and predicting travelers behavior. Paths are usually represented as a sequence of vertices on a road network graph, sequences of geographical coordinates and omitting its temporal component. In this work, we propose a novel, generic and optimized representation of Path Datasets which can be used for any type of data. Such approach is designed to be efficient for collecting, storing and processing path-based data associated to Road Network trips. This approach is novel, as it considers representing paths collectively by origin vertex using tries to index paths uniquely. In particular, for path storage, where we use two effective techniques: DFUDS and Adaptive Edge Offset Compression. We evaluate this approach with other baseline approaches using synthetically generated Path Datasets, to assess the gains in performance (computation time, memory, and storage size) and explain them mainly through a quantity we define, the overlap θ. Results show this approach is more efficient for higher overlap among the paths stored, and never worse than storing for the generated path datasets. The only exception is for the collection stage, in which time and space complexity are higher in some situations.