A grid-based clustering method for mining frequent trips from large-scale, event-based telematics datasets

Telematics systems that integrate wireless communications with sensor-based monitoring and location-aware applications have been widely deployed for mobile asset tracking and condition monitoring. In asset tracking field, exploring the data that relate to asset behaviors is critical to understand asset utilization, efficiency, distribution, operation, and many other important aspects in the supply chain. Prior work on analyzing GPS-based patterns has mainly been performed on time-based datasets. In this paper, we describe a scalable clustering algorithm to discover frequently repeated trips from large-scale, event-based telematics datasets collected via a satellite-based tracking system. We first transform GPS traces into a list of trips. Then we present a grid-based hierarchical clustering algorithm to discover frequent spatial patterns among all trips. We evaluate the effectiveness of the proposed algorithm against a large-scale, real-world dataset collected from tracking over a hundred of thousand assets and prove its feasibility. Through these experimental results, we show that the proposed algorithm significantly reduces the computational time needed for clustering as opposed to the traditional hierarchical clustering based on pair-wise comparison.