Outlier trajectory detection: a trajectory analytics based approach

Trajectories obtained from GPS-enabled devices give us great opportunities to mine out hidden knowledge about the urban mobility, traffic dynamics and human behaviors. In this paper, we aim to understand historical trajectory data for discovering outlier trajectories of taxis. An outlier trajectory is a trajectory grossly different from others, meaning there are few or even no trajectories following a similar route in a dataset. To identify outlier trajectories, we first present a prefix tree based algorithm called PTS, which traverses the search space on-the-fly to calculate the number of trajectories following similar routes for outlier detection. Then we propose two trajectory clustering based approaches PBOTD and DBOTD to cluster trajectories and extract representative routes in different ways. Outlier detection is carried out on the representatives directly, and the accuracy can be guaranteed by some proven error bounds. The evaluation of the proposed methods on a real dataset of taxi trajectories verifies the high efficiency and accuracy of the DBOTD algorithm.