## 5 Method Design
### Trajectory Similarity Search
#### 5.3.3 Filtering Strategy
Moreover, PMMTss can deal with the trajectory intersection problem, i.e., trajectory similarity search with a threshold of 0. However, the three filtering strategies of PPJion+ cannot work if the threshold is set to 0. Therefore, PPJion+ cannot perform a similarity search when the threshold value is 0, i.e., it has no ability to address the problem of trajectory intersection. #### 6.3.2 Evaluation of Indexing and Filtering Effectiveness

In this subsection, we design a group of experiments to illustrate the effectiveness of the multi-layer spatiotemporal index. In detail, it can sharply decrease the number of candidate trajectories and speed up trajectory similarity search. Table 3 summarizes the data volume and the corresponding execution times for PPJoin+ and PMMTss. In detail, the first column means different combinations of trajectory length and threshold. The third column represents the input size, which is the number of trajectories. The fourth column means the number of involved trajectories: it takes the number of original trajectories as the involved trajectories for PPJoin+, and takes the number of trajectories extracted by index as involved trajectories for PMMTss. The fifth column stands for the number of trajectories in the result set. The sixth column shows the ratio of the output size and the input size. The seventh column means the corresponding execution time for a given combination of trajectory length and threshold. Note that the execution time for PMMTss consists of two parts: one is the time used to extract candidate points from the index, and the other is used to perform merging and filtering candidate segments. As shown in Table 3, both PPJion+ and PMMTss achieve more than 99% filtering ratio of the trajectory set, i.e., finding a subset of trajectories that are highly similar to the target trajectory from the input set in a million trajectories. The most significant difference between PPJion+ and PMMTss is the number of trajectories involved in the algorithm. We can make a conclusion that PMMTss has a very effective spatiotemporal index, which keeps all points in it and directly locates candidate points, sharply reducing the number of trajectories involved. To further explore time cost distribution at different stages for PMMTss, we conduct a group of experiments with different query conditions. For simplicity, we denote ET as the time cost used for extracting candidate points from the index, and denote ST as the time cost used for the search phase, which consists of merging and filtering candidate segments. Figure 7 shows the experimental results: the ratio of ET and total time is small when the long trajectory with a low threshold, and the ratio of ET and total time is large when the short trajectory with a high threshold. The value of ET increases from 6.5 ms to 20.1 ms when the length of the target trajectory increases from 4 to 64. It means the multi-layer index-based extract method is highly efficient and stable. ## 7 Conclusions

In this paper, we propose a solution for trajectory similarity search for metro scenarios. The core idea consists of a multi-layer index and a parallel multi-way merging search algorithm. Our method is significantly different from the existing trajectory similarity search algorithms. It keeps points rather than trajectories in the spatiotemporal index, and the candidate trajectory segments are merged and filtered out in the multiple search round. We evaluate this solution on a large dataset (Shenzhen Metro data for 3 consecutive months; 6.976 million trajectories with 260 million records). When lengths of input trajectories are 16, 32, and 64, respectively, the corresponding search times are 0.004 s, 0.016 s, and 0.036 s, respectively. Compared to the baseline PPJion+, the query times are reduced