STL: Online Detection of Taxi Trajectory Anomaly Based on Spatial-Temporal Laws

Abstract

Aiming to promote the standardization of taxi services and protect the interests of passengers, many methods have been proposed to detect taxi trajectory anomaly based on collected large-scale taxi traces. However, most existing methods usually employ a counting-based policy to differentiate normal trajectories from anomalous ones, which may give rise to high false positives. In this paper, we propose an online detection method, named Spatial-Temporal Laws (STL). The basic idea of STL is that, given the displacement from the source point to the current point of a testing trajectory, if the current point is normal, either its driving distance or driving time should lie in a normal range. STL learns the two ranges from historical trajectories by defining two spatial-temporal models: one characterizing the relationship between displacement and driving distance, and another depicting the relationship between displacement and driving time. Consequently, STL is more precise compared with the counting-based methods, greatly reducing the number of false positives. Based on large-scale real-world taxi traces, STL is evaluated through a series of experiments which demonstrate its effectiveness and performance.

1 Introduction

In recent years, many novel methods have been proposed to detect taxi trajectory anomaly [1,2,3, 9, 10, 12,13,14], highlighting their practical value in terms of saving passengers’ time and money. Most existing methods utilize a counting policy to detect anomalous taxi trajectories [1,2,3, 12,13,14]. The rationale underpinning these methods is that trajectories that have been seldom traversed by taxis in the past are considered to be anomalous. Taking Fig. 1 as an example, where S and D represent the source and the destination point respectively, of the seven trajectories shown in the figure, counting-based methods identify $T_2$, $T_6$ and $T_7$ as normal trajectories since they are traversed by most taxis. As normal trajectories appear a significantly greater number of times in the set of historical trajectories, $T_1$, $T_3$, $T_4$ and $T_5$ are labelled anomalous, even though $T_4$ is shorter than the three common trajectories.

Fig. 1.

Example of taxi trajectories between S and D.

It is clear that counting-based detection methods have a major drawback in that they result in a high number of false positives. Furthermore, when detecting a testing trajectory starting from a source to a destination point, if there are fewer historical trajectories with the same source and destination point, counting-based methods may consider the trajectory as anomalous, which means that these methods need a large number of historical trajectories to work properly.

In essence, a trajectory that costs passengers more in both driving time and driving distance should be considered as anomalous. As shown in Fig. 1, the driving distance of both $T_4$ and $T_5$ is not greater than the three normal trajectories, and $T_3$ may be the result of an experienced taxi driver choosing an unusual detour to avoid congestion. In reality, $T_3$, $T_4$ and $T_5$ should not be considered to be anomalous since the cost (either driving distance or driving time) is the same as $T_2$, $T_6$ and $T_7$.

This paper proposes a novel taxi trajectory anomaly detection method, called STL, based on the essential spatial-temporal laws of taxi transportation. The basic idea of STL is that, for a displacement calculated from any point of a normal trajectory to its source point, the costs paid, measured by driving distance and driving time, should lie within normal ranges. STL learns two spatial-temporal models that define two normal ranges from historical taxi trajectories: the D-S model characterizing the relationship between displacement (for short D) and driving distance (S), and the D-T model characterizing the relationship between displacement and driving time (T). Given the two normal ranges, for any point of a testing trajectory, the driving distance and driving time incurred for the displacement are compared to the normal ranges. If both costs are beyond the normal range, it is more likely to be anomalous.

Compared with counting-based methods, STL has three main advantages: (1) it can efficiently detect anomalies in a stream of trajectories online, which means it can immediately respond to the updated taxi traces; (2) taking into consideration the relationships between spatial and temporal features, STL can detect diverse but not malicious trajectories correctly, producing a low number of false positives; and (3) STL is more general, because the transportation characteristics of adjacent areas are similar so their historical trajectories can be gathered to learn the D-S and D-T models, conquering the limitation of existing methods that demand a large volume of historical trajectories to cover the road network.

We evaluate STL on large-scale real-world taxi traces collected from three different cities in one month. In the experiments, we evaluate the performance of STL on different kinds of taxi trajectories in comparison with three other anomalous taxi trajectory detection methods. The results show that STL achieves an excellent performance with a high true positive rate and a low false positive rate in different situations.

2 Problem Definition

On the two-dimensional plane (longitude and latitude), a taxi trajectory can be represented as a collection of points in chronological order. For instance, Fig. 2 shows the trajectory of a taxi in a day, where the red and green points represent the taxi’s status in terms of vacant or occupied, respectively. Since the fraud behaviors of taxis always occur when taxis are occupied, in this paper, we only consider the trajectories of the taxis that are occupied.

Definition 1

(Point). Given a record generated by a GPS device, let x, y be the longitude and latitude of the location and ts be the timestamp of the record. In this way, the spatial information and temporal information of a record can be represented by a point in the form of a triple $\left( x,y,ts\right)$.

Definition 2

(Trajectory). A trajectory T consists of a collection of points in chronological order, $T={<}{p_1,p_2,\ldots ,p_n}{>}$. For any $1\le i<j\le n$, the timestamp of $p_i$ is smaller than the one of $p_j$ and $T_{i \rightarrow j}$ denotes a sub-trajectory ${<}{p_i,\ldots ,p_j}{>}$ of T.

Definition 3

(Displacement, Driving-Distance, Driving Time). No matter whether a trajectory is completed or not, the source point of the trajectory, denoted as $p_1$, is known in advance. For a point $p_i$ observed currently, the displacement, denoted by $d_i$, from $p_i$ to the source point $p_1$ is defined as

$$\begin{aligned} d_i=dist\left( p_i,p_1\right) \end{aligned}$$

where $dist\left( p_i,p_1\right)$ is a function that calculates the geographical distance between the two points.

The driving distance of $p_i$, denoted as $s_i$, is the summation of the geographical distance of all the segments before $p_i$, which is computed as

$$\begin{aligned} s_i=\sum _{j=1}^{i-1}dist\left( p_j,p_{j+1}\right) \end{aligned}$$

Also, we define the driving time, denoted by $t_i$, from point $p_i$ to the source point $p_1$ as

$$\begin{aligned} t_i=p_i.ts-p_1.ts \end{aligned}$$

As shown in Fig. 3, the displacement of $p_i$ is the length of the black dashed line and the driving-distance of $p_i$ is the length of the brown line.

Fig. 2.

One taxi trajectory in a day. (Color figure online)

Fig. 3.

An illustrated example of d and s. (Color figure online)

Definition 4

(Map function). When detecting a testing trajectory, it is necessary to get all the historical trajectories with the same source and destination point as the trajectory. With a huge number of trajectories, the search cost is intolerable without any pre-processing. In order to retrieve historical trajectories more efficiently, we split the road network into equal-sized grid cells and transform a point to a cell by a map function which is defined as

$$\begin{aligned} g_i=map\left( p_i\right) :R^2\rightarrow G \end{aligned}$$

By mapping the coordinates of a point to a grid, a point trajectory (consisting of points) is transformed to a grid-cell trajectory (composed of grid cells). In this way, it is more efficient to identify the trajectories which pass a specific point by searching the trajectories that pass the corresponding grid cell with the help of an inverted index.

Definition 5

(Problem Definition). We define the problem addressed in this paper as follows: Given a set of historical trajectories $S=\{T_1,T_2,\ldots \}$ and a testing trajectory $T=\{p_1,p_2,\ldots \}$ with the source point $p_1$ and the destination point $p_d$, as passengers who use apps like Uber¹ and Didi² to call taxis input their current location and destination, the problem of online trajectory anomaly detection is to find the set of outlier points $P=\{p_i|p_i\in T\}$ in T.

3 Related Work

In general, existing anomaly detection methods are roughly classified into two categories: detection based on spatial features and detection based on temporal features.

3.1 Detection Based on Spatial Features

This type of detection makes use of spatial features to detect anomalies. More specifically, according to the timeliness, this class can be further divided into two sub-categories: offline detection and online detection.

Offline Detection. Lee et al. proposed a novel partition-and-detect framework for trajectory outlier detection which first partitions a trajectory into a set of line segments and then detects outlying segments by a hybrid of the distance-based and density-based approaches [4]. Ge et al. developed a taxi driving fraud detection system based on travel route evidence and driving distance evidence [3]. Zhang et al. proposed an algorithm called iBAT based on the idea that anomalous trajectory is easy to isolate by detecting the complete trajectories offline [11]. Liu et al. proposed an abnormal behavior detection method that is independent of map information and road networks by detecting inconsistencies between the velocity of the vehicle and the speed information of the GPS [6].

Online Detection. Based on iBAT [11], Chen et al. proposed the iBOAT detection method [2]. They considered a trajectory with lower support from historical trajectories as anomalous. It has a higher detection accuracy compared to iBAT and can be performed online. Zhou et al. proposed a detection method named OnATrade [12], consisting of two steps: route recommendation and online detection.

3.2 Detection Based on Temporal Features

The second class makes use of temporal features to detect trajectory. For instance, Li et al. proposed a method for detecting temporal outliers with an emphasis on historical similarity trends between data points [5]. Zhu et al. proposed a time-dependent popular route-based algorithm [14] and designed a time-dependent transfer graph from which the top-k most popular routes are obtained as references in different time periods. Based on [14], Zhu et al. presented an upgraded version of TPRO, named TPRRO [13], which is a real-time outlier detection method. They developed a time-dependent transfer index and a hot time-dependent transfer graph cache which speed up the online detection progress.

As discussed, most existing detection methods only separately consider the spatial or temporal features of trajectories, producing high false positives. Furthermore, the existing methods require a large number of historical trajectories to work properly, and do not have the ability to deal with cases where trajectories are sparse in some areas. In addition, there is scant research on online detection especially in relation to taxis. Therefore, further research into online taxi trajectory detection is urgently needed, which motivates our work.

4 Detection Framework

This section provides the trajectory detection framework which is shown in Fig. 4. The whole detection process is divided into two stages: offline pre-processing and online detection. The role of each component in this framework is described as follows:

Fig. 4.

Trajectory detection framework.

• Taxi Traces: Taxi traces refer to the collection of GPS records uploaded periodically to the server by all taxis.

• Grouping: Since the records of all taxis are mixed together in the traces, it is necessary to group them according to the taxi IDs and sort the GPS records by the timestamp in each group. After sorting the GPS points of each taxi, the parts of trajectory when the taxi is occupied are extracted.

• Denoising: In order to reduce the noise in the set of extracted trajectories, two adjacent points over 5 km away will be separated into two trajectories and the point which causes the speed between it and the last point to be larger than 120 km/h will be ignored. Furthermore, the map-matching technology [7] is applied to project the trajectory points into the road network.

• Invert Indexing: The number of trajectories extracted from the taxi traces is very large. To improve the performance for searching the trajectories that pass a certain grid-cell, the inverted index which records the trajectories passing the grid-cell and the index in which the grid appears is constructed.

• Trajectory Database: This stores all the point trajectories extracted from the traces and the corresponding grid-cell trajectories mapped from the point ones. Each trajectory has a globally unique ID, and its driving distance and driving time have been calculated.

• Index Database: This stores the previously mentioned inverted index.

• Model Cache: This stores the models that have been learned in the detection phase. In this way, when the same model is needed next time, it can be directly retrieved instead of being recalculated repeatedly. In addition, three-day expired time will be set to ensure the freshness of the model. Beyond this time, the model is retrained when the model is requested.

• Anomalous Detection (STL): For a testing trajectory, the historical trajectories that have the same source and destination point can be easily retrieved. Using the historical trajectories, our proposed anomalous detection method STL is applied to detect whether the testing trajectory is anomalous or not. The next section details the design of STL.

Fig. 5.

Displacement, driving distance and driving time scatter plot. (Color figure online)

5 Design of STL

5.1 Basic Idea

Concerning transportation, driving distance and driving time are two important metrics to measure driving efficacy. We use the combination of these two metrics to detect trajectory anomaly which is more accurate and more efficient than the existing methods that separately utilize spatial or temporal features. When detecting a trajectory, if it incurs a reasonable cost in terms of driving distance or driving time to travel from the source to the destination, it should be considered as normal, no matter which routes it takes. Following this direction, we explore the detection of trajectory anomaly using two models that reveal the critical spatial-temporal laws: the D-S model characterizes the relationship between displacement (D) and driving distance (S) and the D-T model depicts the relationship between displacement and driving time (T). The basic idea behind STL is that the set of historical trajectories implying both D-S and D-T laws can be used to efficiently and precisely detect trajectory anomaly. By analyzing large number of historical trajectories, it is found that there are distinctive differences in both laws between anomalous trajectories and normal ones, as shown in Fig. 5. In Fig. 5a, the cyan lines represent the normal trajectories and the red line is an anomalous one. In Fig. 5b and c, the green points and the red points are extracted from the normal and anomalous trajectories respectively. As we can see, the D-S and D-T relationships are quite different after 10 km, so this part of the trajectory should be considered as anomalous.

Therefore, it is practical to use the D-S and D-T relationships of normal trajectories to train models that are, in turn, utilized to detect anomalous trajectories. Given a testing trajectory, for each of its point $p_i$, the displacement $d_i$, driving distance $s_i$ and driving time $t_i$ are first calculated, and then the models learned from the trajectories are utilized to predict the normal ranges for the driving distance and driving time of $p_i$. If both the real driving distance and driving time are beyond the predicted ranges, $p_i$ is considered as anomalous, otherwise normal.

Therefore, designing STL concerns the following questions: (1) How to choose some trajectories from the taxi traces for training the two models? (2) How to learn the D-S and D-T models from the chosen trajectories? (3) How to perform trajectory detection based on the learned models? The following subsections answer these questions.

5.2 Selecting the Training Set

Since the historical trajectories stored in the database are unlabeled, a selection condition should be defined to retrieve some appropriate trajectories from the database to train the D-S and D-T models when detecting a testing trajectory. Therefore, an adaptive approach is firstly used to determine the appropriate number of historical trajectories in order to efficiently learn D-S and D-T models, and then a greedy strategy is applied to select the trajectories. Specifically, we define the number of trajectories as a function related to displacement (d) between the source and destination point and the time of the source point (t), i.e.,

$$\begin{aligned} m(d,t)=m_{base}\cdot 2^{1/(1+e^{-\gamma (d-d_{base})})+wt(t)} \end{aligned}$$

(1)

where the $m_{base}$ is the base number of trajectories, $d_{base}$ is the base displacement, and wt(t) is the indicator of working hours (return 1 when at working hours, otherwise return 0). The intuition behind function (1) is that long-distance drives or drives occurring at working hours need more historical trajectories to keep the detection results stable.

To select the training set that has m(d, t) trajectories determined above, the trajectories that passed from the grid-cell of source point to the grid-cell of destination point are firstly extracted from the trajectory database. Since D-S and D-T models are time-sensitive, the historical trajectories whose timestamps of the source points are within a one-hour period either before or after the timestamp of the testing trajectory’s source point and which have the same wt(t) attribute are chosen. If the number of currently selected trajectories is less than m(d, t), the trajectories passing the source and destination nearby will be used as a supplement; otherwise, the m(d, t) trajectories closest to time t will be selected. Ultimately, to prevent anomalous trajectories from being selected, those trajectories whose driving distance or driving time are less than the median of all trajectories are selected as the training dataset.

5.3 Learning Models

As shown in Fig. 5, the relationships of D-S and D-T are not hard to fit by the linear model. The two models of STL are defined as follows:

$$\begin{aligned} s_i=f\left( \mathbf {d}_i;\mathbf {w}_s\right) +\epsilon _s,\epsilon _s\sim \mathcal {N}\left( 0,\sigma _s^2\right) \\ t_i=f\left( \mathbf {d}_i;\mathbf {w}_t\right) +\epsilon _t,\epsilon _t\sim \mathcal {N}\left( 0,\sigma _t^2\right) \end{aligned}$$

where $\mathbf {d}_i=\left[ 1,d_i,d_i^2,\ldots \right] ^\mathrm {T}$, $s_i$ and $t_i$ represent the displacement vector, driving distance and driving time, respectively, of the $i^{th}$ point in the training dataset, and $f\left( \mathbf {d}_i;\mathbf {w}\right) =w_0+w_1d_i+w_2d_i^2+w_3d_i^3+\ldots$, $\mathbf {w}=\left[ w_0,w_1,\ldots \right] ^\mathrm {T}$. $\epsilon _s$ and $\epsilon _t$ are random variables obeying the normal distribution. Therefore, when using the displacement $\mathbf {d}_{test}$ of a test point to predict the driving distance and the driving time of this test point based on the learned models, we get two random variables subject to $\mathcal {N}\left( f\left( \mathbf {d}_{test};\mathbf {w}_s\right) ,\sigma _s^2\right)$ and $\mathcal {N}\left( f\left( \mathbf {d}_{test};\mathbf {w}_t\right) ,\sigma _t^2\right)$ which are useful to judge whether this point is anomalous or not. In the above models, $\mathbf {w}_s$, $\mathbf {w}_t$, $\sigma _s$ and $\sigma _t$ are the unknown parameters that need to be determined. We use the maximum likelihood estimation [8] to fit the models.

Applying this idea to STL, for each $\mathbf {d}_i$ in the training dataset, the probability of $s_i$ and $t_i$ in the corresponding training dataset should be maximized, namely the following likelihood functions (2) and (3) should be maximized.

(2)

(3)

where N is the total amount of points in the training set.

In order to maximize the likelihood functions (2) and (3), the partial derivatives of $\mathbf {w}$ and $\sigma$ are respectively calculated for the log-likelihood function $\log {L}$ as follows:

$$\begin{aligned} \left\{ \begin{array}{l} \displaystyle \frac{\partial \log L_s}{\partial \mathbf {w}_s}=\frac{1}{\sigma _s^2}(\mathbf {D}^\mathrm {T}\mathbf {s}-\mathbf {D}^\mathrm {T}\mathbf {D}\mathbf {w}_s)=0\\ \displaystyle \frac{\partial \log L_s}{\partial \mathbf {\sigma }_s}=-\frac{N}{\sigma _d}+\frac{1}{\sigma _d^3}\sum _{i=1}^N(s_i-\mathbf {d}^\mathrm {T}\mathbf {w}_s)^2=0 \end{array}\right. \end{aligned}$$

$$\begin{aligned} \left\{ \begin{array}{l} \displaystyle \frac{\partial \log L_t}{\partial \mathbf {w}_t}=\frac{1}{\sigma _t^2}(\mathbf {D}^\mathrm {T}\mathbf {t}-\mathbf {D}^\mathrm {T}\mathbf {D}\mathbf {w}_t)=0\\ \displaystyle \frac{\partial \log L_t}{\partial \mathbf {\sigma }_t}=-\frac{N}{\sigma _t}+\frac{1}{\sigma _t^3}\sum _{i=1}^N(t_i-\mathbf {d}^\mathrm {T}\mathbf {w}_t)^2=0 \end{array}\right. \end{aligned}$$

By solving these equations, the results obtained are:

$$\begin{aligned} \left\{ \begin{array}{l} \displaystyle \mathbf {w}_s=(\mathbf {D}^\mathrm {T}\mathbf {D})^{-1}\mathbf {D}^\mathrm {T}\mathbf {s}\\ \displaystyle \mathbf {\sigma }_s^2=\frac{1}{N}(\mathbf {s}^\mathrm {T}\mathbf {s}-\mathbf {s}^\mathrm {T}\mathbf {D}\mathbf {w}_s) \end{array}\right. \end{aligned}$$

(4)

$$\begin{aligned} \left\{ \begin{array}{l} \displaystyle \mathbf {w}_t=(\mathbf {D}^\mathrm {T}\mathbf {D})^{-1}\mathbf {D}^\mathrm {T}\mathbf {t}\\ \displaystyle \mathbf {\sigma }^2_t=\frac{1}{N}(\mathbf {t}^\mathrm {T}\mathbf {t}-\mathbf {t}^\mathrm {T}\mathbf {D}\mathbf {w}_t) \end{array}\right. \end{aligned}$$

(5)

where $\mathbf {D}=\left[ \mathbf {d}_1,\mathbf {d}_2,\ldots ,\mathbf {d}_N\right] ^\mathrm {T}$, $\mathbf {s}=\left[ s_1,s_2,\ldots ,s_N\right] ^\mathrm {T}$ and $\mathbf {t}=\left[ t_1,t_2,\ldots ,t_N\right] ^\mathrm {T}$.

When applying STL to detect the trajectories, it is apparent that STL has two main characteristics: time-aware and location-aware. Time-aware means the D-T model is changing at different times. Taking the source and destination shown in Fig. 5a for instance, the D-T model at different times is shown in Fig. 6a. It is intuitive that D-T has a smaller slope in the early hours of the morning (1:00–3:00) and a larger one during rush hour (17:00–19:00). With the same displacement, the driving time at rush hour is about 1.5 to 2 times more than that during the early hours of the morning, which proves that training different models based on time is reasonable. For location-aware, two source-destination pairs are picked from the urban and suburban area as shown in Fig. 6b. Figure 6c illustrates that the D-T model may have obvious differences at different locations, despite being at the same time.

Fig. 6.

Time-aware and location-aware.

5.4 Performing Anomaly Detection

For any test point $p_{test}$ in a testing trajectory, the $\mathbf {d}_{test}$, $s_{test}$ and $t_{test}$ are firstly calculated. Secondly, $\mathbf {d}_{test}$ is substituted into the D-S and D-T models that have been trained and two random variables are obtained: one for driving distance s subjected to $\mathcal {N}\left( f\left( \mathbf {d}_{test};\mathbf {w}_s\right) ,\sigma _s^2\right)$ and another for driving time t subjected to $\mathcal {N}\left( f\left( \mathbf {d}_{test};\mathbf {w}_t\right) ,\sigma _t^2\right)$. For each distribution $\mathcal {N}(\mu ,\sigma ^2 )$ with probability density function f(x), an anomaly probability function is defined as function (6):

$$\begin{aligned} anomaly(x)= {\left\{ \begin{array}{ll} 0 &{} \text { , } x<\mu \\ 1-f(x)/f(\mu )&{} \text { , } x\ge \mu \end{array}\right. } \end{aligned}$$

(6)

Therefore, two anomaly probabilities $anomaly(s_{test})$ and $anomaly(t_{test})$ are obtained. To combine these anomaly probabilities, the anomaly practicability of point $p_{test}$ is defined as function (7):

$$\begin{aligned} anomaly(p_{test})=\min (anomaly(s_{test}),anomaly(t_{test})) \end{aligned}$$

(7)

where $\min (\cdot ,\cdot )$ is a function to return the smaller of two values. The principle under the combining strategy is that a taxi that drives a longer distance and spends more time is more likely to have detoured unnecessarily which corresponds to both higher $anomaly(s_{test})$ and $anomaly(t_{test})$.

Anomaly probability $anomaly(p_{test})$ represents the anomaly degree of one point in the trajectory. To evaluate the anomaly of the whole trajectory T, anomaly score based on the anomaly probability is defined as function (8):

$$\begin{aligned} score(T)=\sum _{i=1}^{N-1}dist(p_i,p_{i+1})*anomaly(p_i) \end{aligned}$$

(8)

where N is the number of points in trajectory T. For a point, larger anomaly probability with longer segment means higher anomaly in this trajectory.

6 Empirical Evaluation

6.1 Trace Data

The trace data used in the experiments were collected for a month in three cities of China, namely Shanghai (SH), Shenzhen (SZ) and Chengdu (CD). The detail of these data sets is summarized in Table 1, where the sampling rate means the interval between two adjacent GPS records. Both trace data and implementation of experiments are available at Github³.

To objectively and reasonably select the trajectory sets used for evaluation, the top 10 popular sources and destinations are selected from each data set and the source-destination pairs are identified. Each source-destination pair corresponds to a trajectory set in which all the trajectories pass the source and the destination. To make the performance more stable, those trajectory sets where the source and the destination are too close or the number of trajectories is less than 100 are ignored. The detail of the trajectory sets is listed in Table 2. In each trajectory set, the trajectory is labeled as anomalous or normal according to the taxi fare in this travel.

Table 1. Detail of trace data

Table 2. Detail of trajectory set

6.2 Evaluation Metrics

The TP rate (TPR) measures the proportion of anomalous trajectories that are correctly labeled and is defined as $TPR=TP/\left( TP+FN\right)$. The FP rate (FPR) measures the proportion of false alarms and is defined as $FPR=FP/\left( FP+TN\right)$.

6.3 Compared Methods

In the experiments, STL is compared with three detection methods, namely iBAT, iBOAT and OnATrade. iBAT [11] is an offline detection method based on the cell trajectory mapped from the GPS trajectory. To detect a testing trajectory, iBAT randomly picks a cell from the trajectory to split the trajectory set into two parts, the cell and exclude the cell respectively. This process is repeated until the testing trajectory is isolated or there are no more cells in the testing trajectory. iBOAT [2] is an online detection method which maintains an adaptive window containing the latest testing cells and compare the sub-trajectory composed of the cells in the window with historical trajectories. As long as the support ratio of the sub-trajectory is higher than a threshold $\theta$, the new cell will continue to be added to the window, otherwise, the adaptive window is reduced to include only the cell most recently added and this point is identified as anomalous. OnATrade [12] is an online detection method based on the digital map. OnATrade consists of two steps: route recommendation and online detection. If the maximum similarity between the testing trajectory and all the recommended trajectories is less than a threshold $\theta$, the testing point is considered as anomalous.

6.4 Experiment Setup

To hard-classify the anomaly of point in experiment, a threshold of anomaly probability calculated by function (7) is set up to 0.75. In addition, $m_{base}$, $d_{base}$ and $\gamma$ in function (1) are set to 200, 20 km and 0.5 respectively. Similarly, the thresholds and parameters of iBAT, iBOAT and OnATrade are optimally set according to their proposed papers.

Fig. 7.

Effectiveness comparison.

6.5 Experiment Results

Effectiveness Evaluation. In each trajectory set, leave-one-out cross validation is applied for the evaluation. Specifically, one trajectory is selected to test the detection methods and the rest in the set are used as historical trajectories. The results of the experiments are shown in Fig. 7, where Fig. 7a and b represent the average TPR and FPR on different traces. Compared with the other methods, the overall average of TPR of iBAT, iBOAT, OnATrade and STL are 85.4%, 89.9%, 85.3% and 92.5% respectively; and the overall average of FPR of these methods are 9.9%, 10.2%, 10.1% and 5.7% respectively. Compared to the other three methods, STL shows a sightly improvement over TPR and a substantial improvement over FPR by up to 43%. To evaluate the effectiveness on different scales of trajectory sets, the trajectory sets are divided into three parts: small (${<}300$), medium (300–1000) and large (${>}1000$) according to the number of trajectories in each set. As shown in Fig. 7c and d, when the scale of the trajectory set is small, STL still has good performance on FPR with 42.9%, 48.9% and 49.7% improvement over the other three methods, which demonstrates that STL does not need a large number of historical trajectories to perform the detection.

Performance Evaluation. We analyze the time cost for these detection methods. The average detection time per trajectory on different trace datasets is shown in Fig. 8. STL has the smallest time complexity while OnATrade has bad performance on a long-distance trajectory because the time complexity of computing similarity is $O\left( n^2\right)$ (n is the number of points in the trajectory). Since the GPS sampling rate on the data sets of Shenzhen and Chengdu is less than the one of Shanghai, the time costs on the two datasets are lower than the one on Shanghai on average. In addition, the space complexity of STL is $O\left( 1\right)$ because it only stores basic information, such as the source point, the last point and the driving distance of the last point. This is another advantage of STL over the other three methods.

Fig. 8.

Time cost comparison.

Online Detection Analysis. This part analyzes why the FPR of iBOAT and OnATrade is higher than that of STL. To illustrate the difference between iBOAT, OnATrade and STL, one trajectory set consisting of 1490 trajectories from the Shanghai trace dataset is selected as an example as shown in Fig. 9a. The thicker the lines, the more times the trajectories are passed. The median of the driving distance and driving time of all trajectories are 13.56 km and 19.38 min, respectively. Since the number of trajectories covered by the rectangle shown by the blue dashed line is small, the trajectories passing this part are more likely to be classified as anomalous by iBOAT and OnATrade. We pick up a trajectory T passing this covered area, and its driving distance and driving time are 13.61 Km and 14.32 min, respectively. Since the driving time is less than the median and the driving distance is close to the median, T should be detected as normal.

Specifically, the visualization of the detection results for OnATrade and the similarity trend of T are shown in Fig. 9b and e. In Fig. 9b, the green points are labeled as normal and the red points are detected as anomalous. In Fig. 9e, the blue line and the orange dashed line represent the similarity of T with the recommended trajectories and the threshold $\theta _{sim}$, respectively. Since there is no trajectory in the recommended trajectories passing the covered area, it can be assumed that this part will be detected as abnormal. The detection result confirms this conjecture. The similarity drops from the ${18}^{\mathrm {th}}$ point and is below the threshold at the ${23}^{\mathrm {rd}}$ point. Therefore, after that, the points of T will be detected as anomalous.

For iBOAT, the visualization of the detection results is shown in Fig. 9c and the trend of the support ratio of T is shown in Fig. 9f. In Fig. 9f, the blue line and the orange dashed line represent the support ratio of each point in T and the threshold $\theta _{iBOAT}$, respectively. The support ratio drops at the ${18}^{\mathrm {th}}$ point and rises at the ${42}^{\mathrm {nd}}$ point, so this part of T is detected as anomalous by iBOAT, which corresponds to the area covered by the blue dashed line rectangle in Fig. 9a.

For STL, the visualization of the detection results for STL is shown in Fig. 9d. In Fig. 9g, the blue line, orange dotted line and green dashed line represent the anomaly probability of driving time, driving distance and the threshold mentioned in Sect. 6.4, respectively. Since the two anomaly probabilities are always below the threshold, the anomaly probability of points are apparently within the normal range. Therefore, T is correctly detected as normal.

Fig. 9.

Online detection comparison. (Color figure online)

In addition, the anomaly scores of T are 0.59, 5422.90 and 37.08 for OnATrade, iBOAT and STL respectively, where the range of anomaly score for OnATrade is 0 to 1 and the range for iBOAT and STL is 0 to infinity. The anomaly scores of T are ranked 80 (5.4%), 50 (3.4%) and 926 (62.1%) in 1490 trajectories, which also reflects the different behavior between the three methods.

7 Conclusion

In this paper, we proposed a novel method called STL for the online detection of taxi trajectory anomaly. Rather than using spatial or temporal features separately, STL combines spatial features and temporal features to solve the problem of high false positives caused by most existing counting-based methods and to demand sufficient historical trajectories to work properly. STL catches the essence of transportation in terms of two critical models: D-S and D-T, which can be used to detect anomalous trajectories efficiently and precisely. Through extensive experiments on real traces, we verify that STL can perform real-time detection and identify the anomalous part of trajectories. Furthermore, STL has excellent performance on both TPR and FPR with small time cost and memory consumption.