Spatio-Temporal Trajectory Similarity Measures: A Comprehensive Survey and Quantitative Study

With the proliferation of GPS-equipped devices and mobile computing services, massive spatio-temporal trajectory data of moving objects such as people, vessels, and vehicles are being captured [87, 39]. For example, people share visited places (e.g., POIs) on social networks by their smartphones to generate “check-in” trajectories; according to the AIS project [47], millions of vessels connected with the AIS services continuously report locations to ensure the sailing safety; and the world’s largest ridesharing company Uber collects up to 17 million vehicle trips daily [63].

Trajectory data with its analytics benefit a broad range of real-life applications across different fields such as urban computing [38], transportation [88], behavior study [37], and public security [34], to name but a few. A fundamental functionality of most trajectory analysis is to evaluate the relationship/distance between two trajectories, i.e., trajectory similarity measurement. With an accurate and efficient trajectory similarity measure, downstream trajectory analytics involving retrieval [58, 50], clustering [32, 18], classification [22, 31], and mobility pattern mining [44, 28, 60] tasks can be well-supported to serve upper applications. For instance, Xie et al. [71] propose two distance measures to support similarity queries and joins in a large-scale trajectory dataset. Wang et al. [67] design a road network oriented distance measure for vehicle trajectory similarity computation, based on which, $k$-means clustering is studied [69] to detect hot/popular traveling paths in a city. In both cases, the trajectory similarity measure plays a fundamental role, and a different measure selection may result in totally different query results and clustering quality. Take the trajectory clustering as an example, clustering aims to group similar trajectories into clusters, where similarity computation is a fundamental task of clustering as shown in Figure 1(a); while different similarity measures may affect the clustering quality. As shown in Figure 1, although the numbers of clusters are the same (i.e., $\#$clusters=4), the clustering results are quite different when applying different measures (i.e., DTW and EDR). Hence, the selection of similarity measure is important. In addition, more trajectory similarity based analysis tasks can refer to [66, 39].

Unlike isolated spatial points or one-dimensional time series where the distance definition is straightforward, it is non-trivial to define the distance between continuous two-dimensional trajectories. It also needs to consider following four trajectory characteristics: (i) Different data sources, i.e., free space vs. road network space. In the latter case, a proper trajectory measure should take the road topology into account, as people and vehicles cannot travel like vessels without spatial constraints [54]. (ii) Various sampling rates and lengths. Unlike time series that generally feature constant and high sampling rates [36], spatio-temporal trajectory data is usually generated via varying samplings, resulting in variable lengths. (iii) The effect of noise. The noise points commonly exist, especially due to strength attenuation and interference in urban cities [83]. (iv) Complex shapes. Compared to private-car trajectories that are usually inaccessible caused by privacy principles, taxi trajectories are widely studied in the community [15, 61, 68]. However, taxi trajectories exhibit much more diverse, complex, and flexible geometric, because of various pick-pop demands. To deal with the above spatio-temporal characteristics, tremendous amounts of research efforts are devoted to designing dozens of spatio-temporal trajectory similarity measures.

Being faced with a huge amount of trajectory measures, researchers are often too exhausted to select a proper one. On the one hand, there are too many trajectory measures, which were proposed under different scenarios, e.g., learning based or non-learning based, free-space oriented or road network oriented, as well as standalone or distributed processing. In each scenario, various measures exist. Consequently, users need to spend tons of time and efforts to explore the specific details of each measure and the relations/differences among them. On the other hand, the evaluation on various trajectory measures is still not well organized. For instance, some measures only focus on efficiency, while others may put more attention on effectiveness and robustness. To address the problems mentioned above, a comprehensive survey, benchmark, and evaluation will be a great help for researchers involved in this important topic. Specifically, considering three-dimensional aspects, we classify the existing representative spatio-temporal trajectory measures proposed from 1995 to 2022 year in a hierarchical way, i.e., Non-learning vs. Learning (first hierarchy), Free Space vs. Road Network (second hierarchy), and Standalone vs. Distributed (third hierarchy). Table I summarizes trajectory similarity measures.

Although previous systematic surveys have made some efforts, they mostly focus on non-learning, free-space, or standalone based measures and thus significantly narrow the studied scope of trajectory similarity community. For example, Gudmundsson and Toohey et al. [62] only review four basic trajectory distance measures including Euclidean distance (ED), DTW [79], LCSS [64], and Fréchet [2]. Based on it, Sousa et al. [15] append partial vehicle trajectory similarity measures, e.g., LORS [67], LCRS [80], and NetEDR [30]. Note that, experimental evaluation of these measures are not studied in the surveys. Su et al. [57] conduct the state-of-the-art survey and experimental evaluation for 10 trajectory similarity measures under the non-learning, free-space, and standalone contexts. In contrast, we conduct a much more systematic review and evaluation of all the most common and representative spatio-temporal trajectory measures in a three-dimensional hierarchical way as depicted in Table I. We conduct a three-dimensional survey due to three following motivations:

(i) As deep learning has made great success in AI community, many studies [36, 76, 84, 26, 19] start leveraging the powerful approximation capabilities of neural networks to attempt to replace the traditional handcrafted trajectory measures with learning-based models. Besides, increasing efforts have been devoted to embracing learning-based techniques as an integral part of trajectory data management and analytics, such as deep clustering [20], deep mobility pattern mining [9], and deep path recommendation [81], to name just a few. As such, we believe that we have reached an imperative point to systematically study the contribution and explore the relations, differences, and pros/cons among the emerging learning-based and classic non-learning based trajectory measures.

(ii) In the early stage, most of the trajectory measures [57] are proposed for objects that move freely in the Euclidean space, e.g., bird or vessel trajectories. Recently, the proliferation of vehicle navigation systems and location based services (LBSs) enable the massive collection of vehicle and people trajectories in road networks. In that case, the free-space oriented trajectory measures cannot reflect the true distance between moving objects in a moving-constrained road network. In view of this, many network-aware trajectory measures [80, 67, 54, 30] are designed. To the best of our knowledge, there is no previous work that has given a systematic review and experimental evaluation of those network-based trajectory distance measures.

(iii) Since the storage capacity and processing ability of a single machine can no longer support a large scale of trajectory data, another popular line of trajectory similarity study is designing efficient and scalable frameworks upon distributed processing platforms (e.g., Spark) for large-scale trajectory similarity analytics. Towards this, several system-level frameworks are also developed. Hence, we are inspired to present a sufficient review and performance evaluation of distributed-based similarity computation studies.

Motivated by the observations above, we conduct a most unprecedented survey on all the most representative spatio-temporal trajectory similarity measures proposed in the literature. Specifically, we review 25 similarity measures from the following hierarchical perspectives, namely: (i) Model architecture, i.e., non-learning based vs. learning-based; (ii) Space context, i.e., free space oriented vs. road network oriented; and (iii) Computational mechanism, i.e., standalone machine vs. distributed platform. To the best of our knowledge, none of the previous studies have reached such a wide scope of trajectory measure evaluation. It is also significant to conduct objective and sufficient evaluation to study each measure by using the same tasks, datasets, and experimental settings. In light of this, we provide a standard benchmark¹¹1publicly available at https://github.com/ZJU-DAILY/TSM in a real setting by introducing five different scenarios, i.e., length shift, shape shift, noise shift, sampling shift, and cardinality shift, on four real datasets. Then, we extensively explore and compare the effectiveness, robustness, efficiency, and scalability for all measures via quantitative and qualitative analysis. With our benchmark, (i) users can quickly grasp the technical details about trajectory similarity measures; and (ii) users can easily choose or design suitable measures and utilize them as the baselines. Overall, this paper makes the contributions below.

• •

  We conduct a concise but concrete review to evaluate and compare spatio-temporal trajectory similarity measures qualitatively and quantitatively in three dimensions, i.e., learning-based or not, road network oriented or not, and distributed-based or not, providing a reference for measure selection among traditional similarity measures, deep learning models, and distributed processing technologies.

• •

  We provide a standard evaluation benchmark with five types of trajectory transformations under five typical trajectory analytics scenarios. Based on this, we conduct a comprehensive evaluation of effectiveness, robustness, efficiency, and scalability performance of 25 representative measures.

• •

  We have several key observations according to experimental results, based on which, we offer insights about trajectory measure selection in specific application scenarios. According to several issues that remained to be solved, we also present detailed potential future directions.

Section 2 gives the preliminaries. Sections 3 and 4 present the non-learning-based and learning-based trajectory similarity measures respectively, where free-space vs. network oriented and standalone vs. distributed measures are further detailed. Section 5 provides the benchmark. The evaluation results with insights are reported in Section 6. Section 7 puts forward interesting future directions. Finally, Section 8 concludes the paper.

In this section, we present the definitions related to trajectory similarity measure.

Here, $n$ denotes the length of a trajectory. We use $T_{i}$ to denote a trajectory whose id is $i$, and use ${T_{i}^{j}}$ to denote the $j$-th point in $T_{i}$. The points observed by GPS equipments could contain various information. For simplicity, we assume each sampling point is two-dimension or three-dimension (i.e., $(\textit{latitude, longitude})$ or $(\textit{latitude, longitude, timestamp})$). Although trajectory data is similar to time series data, time series data typically lacks of spatial information. In particular, for vehicle trajectories, they are physically constrained to the road network. Thus, directly applying similarity measures for time series in free space is not always suitable. The trajectories with road network constraints are taken into consideration. The road network is defined as follows.

Here, $v_{i}=(lat_{i},lon_{i})\in V$ is a road intersection, where $i$ is the id of $v_{i}$, while $(lat_{i},lon_{i})$ denotes the latitude and longitude of $v_{i}$. Meanwhile, an edge $e_{i,j}\in E$ represents a directed road segment from $v_{i}$ to $v_{j}$. Existing map matching methods [7, 82] are proposed to transform a trajectory of GPS points into a road network constrained trajectory. A trajectory in a road network can be represented as $T=\left\langle v_{1},v_{2},...,v_{c}\right\rangle(c\leq n)$ or $T=\left\langle e_{1},e_{2},...,e_{c-1}\right\rangle(c\leq n)$, where $c$ is the number of road vertices in $T$.

As shown in Table I, a similarity measure can be classified according to i) whether it is metric or not as defined in Definition 4 (“$\checkmark$” denotes it is a metric, “$\times$” denotes it is not a metric, “$/$” denotes learning methods do not use a manual function to compute similarity), ii) whether it can support trajectories with different lengths, iii) whether it is parameter-free, and iv) whether it is noise sensitive. Since trajectory similarity query is a prerequisite task in upper-level applications [71, 24], we perform Top-$k$ trajectory similarity query to evaluate the capabilities of all similarity measures in Section 6, which is defined below.

In this section, we introduce 22 non-learning based measures (as shown in the upper part of Table I), and further detail each measure in terms of space context (i.e., free space and road network).

As mentioned in Section 3, non-learning measures generally have a time complexity of O(mn), which is high. To address this, learning-based methods are developed to reconstruct the input data of high-dimension into a new representation of low-dimension [41, 78, 36].

t2vec [36] designs a trajectory deep learning framework to achieve robustness to low sample rates and noises. It maps a trajectory into a $d$-dimensional embedding vector. Note that, t2vec is not a similarity measure, but a representation method to transform trajectories into vectors.

Inspired by t2vec, many studies employ different deep learning frameworks in free space and road network, to learn approximate distance functions for non-learning measures. Generally, as shown in Figure 9, they first select similar and dissimilar trajectories (i.e., positive and negative trajectories) of anchor trajectories (origin trajectories) to obtain grid-based trajectories [76] or similarity triplets [84, 26, 19]. Then, features (in terms of spatial, temporal, structural and so on) are extracted, while trajectory embedding vectors are generated using deep representation learning. Finally, the learning (dashed rectangle in Figure 9) can stop until the trajectory similarities and dissimilarities evaluated on the embedding vectors are close to the ground-truth. Here, results calculated using non-learning measures are taken as ground-truth. Note that, the time complexity of similarity learning among vectors is linear. In view of this, we review 4 representative learning-based measures.

NEUTRAJ. The first learning-based trajectory similarity measure is NEUTRAJ [76], which is based on neutral metric learning. Specifically, NEUTRAJ first maps trajectories into grid-trajectories. Then, it samples trajectories as seeds, and uses their pair-wise similarities and dissimilarities as guidance. Finally, NEUTRAJ uses Long Short-Term Memory (LSTM) model to generate the embedding vectors, and approximates various non-learning similarity computations (as depicted in Figure 9) with the complexity of O(m+n). Note that, embedding vectors generated by NEUTRAJ can preserve the spatial information of trajectories. In addition, in order to improve the performance of deep representation learning methods on long trajectories, TrajGAT [77] is proposed, which is based on graph attention networks (GATs), Transformer and a quad-tree index for effectively embedding trajectories.

Traj2SimVec. Although NEUTRAJ has greatly reduced the time complexity, it needs a pre-training process to compute the similarity among all seed trajectories, which incurs a quadric time complexity during training. Thus, Traj2SimVec [84] is proposed to improve the training efficiency by simplifying training trajectories into triplet training samples. And the training time complexity is reduced to O(logn), where $n$ denotes the average length of training trajectories. Similar to Traj2SimVec, T3S [75] and TMN [74] are proposed based on attention networks, where the former considers dissimilar trajectories while the latter focuses on the inter-information between trajectories.

GTS. Different from the above two methods that are designed in free space, a Graph Neural Network (GNN) based approach named GTS [26] is designed to measure the trajectory similarity in road network. In order to reflect the information on the road network, GTS learns the representation of point-of-interest (POI) in spatial network and the relationship between trajectories, between POIs, or between trajectories and POIs.

ST2Vec. ST2Vec [19] is also proposed for spatio-temporal trajectory similarity computation in road network. Considering the complex temporal information in trajectory data [57], ST2Vec with a time complexity of O(d) captures both spatial and temporal features, and fusions these features to obtain spatio-temporal embedding vectors based on GNN and LSTM. Also, ST2Vec applys training triplets samples to reduce the training cost, and sets spatial and temporal weights that can be adjusted for flexible analysis.

Note that, due to the similarity among different learning-based methods, we mainly evaluate NEUTRAJ [76], Traj2SimVec [84], GTS [26], ST2Vec [19] in Section 6 for simplicity.

Motivation. Since the evaluation on such a big family of trajectory similarity measures has never been organized, we are inspired to propose the first standard evaluation framework to examine the function of each measure. On the one hand, the primary goal of a distance measure is being effective, robust, efficient, and scalable. These four desiderata are often in tension with each other. In view of this, the evaluation framework must enable to study the capability of each measure in terms of multi-aspects. On the other hand, trajectory data usually have various characteristics such as variable lengths, complex shapes (especially for vehicle trajectories), varying samplings, outlier noises, etc. Specifically, the variable lengths and complex shapes are intrinsic properties [87], while the varying samplings and outlier noises are usually caused by other factors [57] such as battery power and urban building effect. Overall, we build an evaluation framework to benchmark the trajectory measures under as many real-life settings as possible, objectively studying the capability of each measure in terms of four performance aspects. Table II summarizes all the evaluation dimensions and corresponding scenarios. According to Table II, we evaluate each trajectory similarity measure from four dimensions as follows.

(i) Effectiveness vs. length and shape. Length and shape are considered as intrinsic properties of trajectory data [35], which requires an effective measure. However, as the similarity of two trajectories does not have a ground truth [32], we cannot determine whether the value computed by trajectory measures is correct or not. It is also meaningless to cross-compare the distance values returned by different measures. To this end, we adopt a qualitative way to visualize the Top-$k$ similarity query results returned by different trajectory measures, for the same query trajectory. Thus, we give an intuitive analysis when the query trajectory is selected with different lengths or shapes to show the effectiveness of each measure.

Specifically, we use parameter $L$ to change the trajectory length. For example, $\textit{L=}20$ means to select the first $20\%$ points from the original trajectory as a deformed trajectory. Such length-oriented evaluation enables us to see how each distance measure performs when the length of the trajectory changes from short to long, which is useful in an online setting that involves trajectory evolution. In terms of varying shapes, we select four typical geometrics, i.e., straight line, polyline without overlaps, polyline with overlaps, and round line, to explore how each similarity measure performs when the query trajectories are of different shapes.

(ii) Robustness vs. sampling and noise. Quality issues commonly exist during data collection. For example, a taxi driver may alter the default device sampling rate to reduce the power consumption [86]. In this case, even for the same trajectory, this may result in sparse and dense segments. In addition, noise may occur in GPS points, which is usually caused by low satellite visibility or urban canyons that affect signal quality. Consequently, given a query trajectory, a robust trajectory similarity measure is expected to retrieve the same query results for datasets with different sampling rates and noise ratios.

We use parameter $S$ to denote the percentage of sampling points in each trajectory. For example, $\textit{S=}20$ means that we sample $20\%$ points from a trajectory as a deformed trajectory. Note that, sampling transformation is meaningful and useful for free space trajectories, while meaningless and useless for road network constrained trajectories after map matching. We use parameter $N$ to represent the ratio of noises in a whole trajectory. For instance, $\textit{N=}10$ denotes to sample $10\%$ points from a trajectory, and then add an outlier for each point. Here, we utilize Gaussian noise [5] to add an outlier $p^{\prime}$ for each filtered point $p$, i.e., $p^{\prime}=p+\Delta\cdot p\sim Gaussian(0,1)$, where $\Delta$ is the radius range of outliers.

(iii) Efficiency vs. Top-$k$ query. An efficient trajectory similarity measure is expected to efficiently compute the distance value between any pair of trajectories, which especially is important for online trajectory applications. Therefore, we directly use the Top-$k$ similarity query as the evaluation task.

(iv) Scalability vs. length and cardinality. Despite how the average trajectory length or the data cardinality (i.e., the number of moving objects) of the trajectory dataset changes, a scalable measure should show stable inter-trajectory distance computation performance. Specifically, we proceed to use $L(\%)$ to control the average length of trajectories in the dataset. In addition, we use another parameter $O_{r}$ to control the percentage of moving objects w.r.t. all the objects, i.e., the trajectory dataset to be queried/processed.

We conduct extensive experiments aimed at offering insights to the performance of trajectory similarity measures summarized in Table I. First, we present experimental settings. Next, based on the evaluation benchmark proposed in Section 5, we study trajectory measures in terms of four aspects: effectiveness, robustness, efficiency, and scalability. Finally, we conduct a study of metric similarity measures to show the effect of indexing and pruning on them.