A concise summary of spatial anomalies and its application in efficient real-time driving behaviour monitoring

Abstract

This work is motivated by a smart car application which analyses streams of data generated from cars to enhance transportation safety. We treated the problem as real-time abnormal driving behaviour detection using spatio-temporal data collected from mobile devices including GPS location, speed and steering angle. A concise summary was proposed to summarise spatial patterns from GPS trajectory data for eficient real-time anomaly detection. An approach solving this problem by nearest neighbour search has O(n) space and O(log(n) + k) query time complexity, where k is the neighbourhood size and n is the data size. On the other hand, the concise summary approach requires only O(ϵn) memory space and has O(log(ϵn)) query time complexity, where ϵ is several orders of magnitude smaller than one. Experiments with two large datasets from Porto and Beijing showed that our method used only a few megabytes to summarise datasets with n = 80 million data points and was able to process 30K queries per second which was several orders of magnitude faster than the baseline approach. Besides, in the work, interesting spatio-temporal patterns regarding abnormal driving behaviours from the real-world datasets are also discussed to demonstrate potential application of the work in many industries including insurance, transportation safety enhancement and city transport management.