| With the rapid proliferation of the GPS-equipped devices, a myriad of trajectory data representing the mobility of the various moving objects in two-dimensional space have been generated. By mining these trajectory data, we can discover the secret behind the data.Under this background, extensive researchers are encouraged in trajectory pattern mining,such as life pattern mining, popular routes discovering, transportation mode mining, adjoint pattern mining and trajectory outlier detection. This paper aims to detect the anomalous trajectories by means of the large trajectory dataset.Some trajectory outlier detection methods have been proposed in recent years. But there are two major insufficiencies in these methods. The first insufficiency is that most existing solutions have a high time complexity. This makes them only suitable for small dataset detection and they are not suitable for large dataset detection. The second insufficiency is that existing solutions do not take the time constraint into consideration when judging if a trajectory is an outlier. Ignoring time constraint leads to miscarriage of justice.In order to address the problems mentioned above, this article puts forward a trajectory outlier detection solution based on the time-dependent popular routes. Both of spatial and temporal abnormalities are taken into consideration simultaneously to improve the accuracy of the detection. There are two missions in this solution. The first one is finding out all outliers from a large dataset without any training data. The second one is evaluating a ongoing trajectory based on a large dataset. When this ongoing trajectory has a tendency to be an outlier, this solution will give people a warning. After this trajectory stops at somewhere,this solution can tell which subpart of this trajectory is responsible for the abnormity.This article puts forward two algorithms(TPROO and TPROR) to fulfil above two tasks. TPROO focuses on detecting outliers from a historical static trajectory dataset and TPROR focuses on detecting an ongoing trajectory. TPROO adopts a group-and-detection strategy, which avoids lots of unnecessary calculation. So the time complexity is greatly reduced. Besides, TPROO proposes a novel time-dependent distance measure which is based on edit distance in both spatial and temporal domain. TPROR is the upgrade version of TPROO. The time-dependent transfer index and hot time-dependent transfer graph cache are put forward in TPROR to speed up the detection progress. The experiment result shows that TPROR is more efficient and more suitable for real-time trajectory outlier detection.In summary, this article puts forward a detection solution based on time-dependent popular routes, which is suitable for large dataset detection and both of spatial and temporal abnormalities are taken into consideration. The idea proposed in this article makes contributions in both research aspect and practical aspect. |
