## 1 Introduction  
A modern metro system plays a crucial role in public transportation systems due to its efficiency, punctuality, and comfort. As the urban population and the metro network grows, the number of records collected by the automatic fare collection (AFC) system in the metro is growing rapidly. In the case of the Shenzhen Metro system, as of January 2019, there are eight lines with a total of 166 stations, and the number of active smart cards has exceeded 10 million. Every day, three million passengers choose the metro as their traffic way on average. In detail, each record contains information such as smart card ID, timestamp, station name, and the flag of entry or exit. The entire metro system collects 24 million records per day on average, the corresponding number of records produced in each month is 690 million, and the corresponding number of records produced in six months is 4.2 billion. These historical ticket records not only contain the trajectory of individual passenger, but also contain the movement patterns of millions of passengers [1, 2]. How to manage and mine this valuable dataset is a popular research topic. The ability to store and analyze this trajectory dataset is the foundation for the downstream applications [3, 4]. For example, in an epidemic investigation, it is necessary to quickly determine which passengers have a spatiotemporal intersection with a passenger who is tested positive for COVID-19. However, it is a challenging task to conduct a similarity search on a dataset with millions of passenger trajectories. Currently, the most existing trajectory similarity research is focusing on GPS trajectories produced by moving objects, such as vehicles and mobile devices. The corresponding indexes and filtering strategies are designed according to the spatiotemporal features of GPS trajectories. However, these trajectories produced by smart cards in metro transportation systems present totally different spatiotemporal features from GPS trajectories. Thus, it is hard to apply these GPS-oriented solutions to trajectory similarity searches in metro transportation systems. To fill this gap, in this paper, we design and implement a trajectory similarity search solution for millions of metro passengers. The core idea of this solution has two points, the first is a point-based multi-layer spatiotemporal index and the second is a parallel multi-way merging-based search algorithm. Compared with the traditional method, our solution does not generate complete trajectories in advance, all points in a trajectory are scattered and stored in the spatiotemporal index. In detail, it first partitions all points into different groups by station name in the first layer, then it further divides the timeline into different intervals in the second layer and each point in a group is assigned to a particular interval. As to the search algorithm, it is executed in multiple rounds. In the first round, a group of tasks takes a query trajectory as input, and get candidate points from the index, generating candidate trajectory segments. In other rounds, candidate trajectory segments are merged by the same trajectory identity and the filtering strategy is conducted. Finally, a group of trajectories is returned, each of which satisfies that the similarity between it and the query trajectory is large than a predefined threshold. To evaluate the proposed method, we design and conduct a group of extensive experiments. We first implement PPJoin+ [5], the state-of-art string similarity search algorithm, as the baseline for evaluation. Then, we conduct a systematic comparison between PMMTss and PPJion+. Finally, we evaluate the effectiveness of the indexing and the filtering strategy of PMMTss. In summary, our key contributions are as follows. First, we design and implement an effective similarity search method called PMMTss for metro passenger trajectories. PMMIss has two key points, a multi-layer spatiotemporal index, and a parallel multi-way merging-based trajectory search algorithm.