Evolutionary Clustering of Moving Objects

The widespread deployment of smartphones, net-worked in-vehicle devices with geo-positioning capabilities, and vessel tracking technologies renders it feasible to collect the evolving geo-locations of populations of land- and sea-based moving objects. The continuous clustering of such data can enable a variety of real-time services, such as road traffic management and vessel collision risk assessment. However, little attention has so far been given to the quality of moving-object clusters-for example, it is beneficial to smooth short-term fluctuations in clusters to achieve robustness to exceptional data and to improve existing applications. We propose the notion of evolutionary clustering of moving objects, abbreviated ECM, that enhances the quality of moving object clustering by means of temporal smoothing that prevents abrupt changes in clusters across successive timestamps. Employing the notions of snapshot and historical costs, we formalize ECM and formulate ECM as an optimization problem. We prove that ECM can be performed approximately in linear time, thus eliminating iterative processes employed in previous studies. Further, we propose a minimal-group structure and a seed-point shifting strategy to facilitate temporal smoothing. Finally, we present all algorithms underlying ECM along with a set of optimization techniques. Extensive experiments with three real-life datasets offer insights into ECM and show that it outperforms state-of-the-art solutions in terms of both clustering quality and clustering efficiency.