Lightweight road network learning for efficient trajectory pattern mining

摘要

Individual trajectory traces of different lengths often amount to hundreds or thousands of trajectory points distributed over continuous spatial space. This makes fast trajectory pattern mining very challenging. For road network constrained trajectories like vehicle trajectories, mapping raw trajectory points to road links is a natural calibration procedure that can greatly alleviate the complexity of subsequent pattern mining. However, road map is generally proprietary and imposes limitations on commercial applications. Although a variety of map inference approaches were proposed for the generation of general-purpose road map on the basis of trajectory traces, those procedures are generally too heavy to be applied in the calibration for trajectory pattern mining. In this paper, we propose the first lightweight approach to generate road network from trajectory traces in order to support trajectory pattern mining. The approach is composed of three steps: trajectory density map construction, a cell aggregation step and the final network links/nodes clustering. Only one input data scan and two iterations over trajectory dense areas are necessary during the whole progress. Equipped with the obtained road network, the mapping of trajectory points to road network elements is performed by simple spatial projection operations instead of map-matching process, the result of which supports an efficient trajectory pattern mining.