## 4 Problem Definition  
The purpose of a metro trajectory similarity search is to find a group of passengers whose trajectories have a high degree of spatiotemporal overlap with the target trajectory. To help understand metro trajectory similarity search, the following definitions are provided. **Definition 1**. : _(Point): A point of a GPS trajectory is commonly represented by three fields, time, longitude and latitude, \(P=\{t,lon,lat\}\). However, in a metro trajectory, the longitude and latitude of a point can be replaced by a station name \(s\). In addition,\(\sigma\) is the flag, which represents the passenger entering (\(\sigma=O\)) or leaving (\(\sigma=D\)) the metro station. The point of metro trajectory is defined as follows:_  
\[P=(t,s,\sigma). \tag{1}\]  
**Definition 2**. : _(Trajectory): A trajectory of a metro passenger is made up of a card ID and a series of ordered points. Moreover, we can transform a point-based trajectory into a trip-based trajectory. In the context of the metro scenario, each trip has an original point and a destination point, a trip also can be called an OD (original destination). In this way, the trajectory can also be described as a sequence of OD pairs. The trajectory of the metro passenger is defined as follows:_  
\[\text{Tr}=\Big{\{}\text{card1d},\Big{\{}\text{P}_{1}^{\text{O}},\text{P}_{2}^{ \text{D}},\ldots,\text{P}_{n-1}^{\text{O}},\text{P}_{n}^{\text{D}}\Big{\}} \Big{\}}. \tag{2}\]  
**Definition 3**. : _(Similarity of Point): How to measure the similarity of two different points is the foundation to measure the similarity of two different trajectories. If two passengers appear at the same metro station within the same time period, we assume that the points in different passenger trajectories are similar. However, for the trajectory spatiotemporal intersection (TSI), \(\Delta t\) is a threshold with a relatively small value, typically around 10 min between the time intervals of two adjacent metro trains. For trajectory similarity search, the value of \(\Delta t\) is assigned a relatively larger value, typically 2 h. In summary, \(P_{i}\) and \(P_{j}\) are similar if they satisfy the following conditions:_  
\[\left\{ \begin{aligned} s_{i}=s_{j}\\ |t_{i}-t_{j}|<\Delta t\end{aligned} \right.. \tag{3}\]  
**Definition 4**. : _(Trajectory Similarity Measure Function): Given two trajectories \(\text{Tr}_{o}\) and \(\text{Tr}_{i}\), their similarity scores are shown in Equation (4). This measurement is derived from Jaccard [25] and LCSS [26]._  
\[Sim(\text{Tr}_{o},\text{Tr}_{i})=\frac{\sum_{k=1}^{|\text{Tr}_{o}|}d_{o\to i }^{k}}{|\text{Tr}_{o}|}. \tag{4}\]  
_The variable \(d_{o\to i}^{k}\) is a Boolean value that indicates whether the points of the trajectory are similar or not. The rules for the variable \(d_{o\to i}^{k}\) are shown below:_  
\[d_{o\to i}^{k}= \begin{cases}0,&\text{Others}\\ 1,&s_{o}^{k}=s_{i}^{k}\text{ and }\left|t_{o}^{k}-t_{i}^{k}\right|<\Delta t \end{cases} . \tag{5}\]  
**Definition 5**. : _(Metro Trajectory Set): Each passenger produces a trajectory and all passenger trajectories formulate a trajectory set. The trajectory set is denoted as the following equation:_  
\[\text{TrSet}=\{\text{Tr}_{1},\text{Tr}_{2},\ldots,\text{Tr}_{n}\} \tag{6}\]  
**Definition 6**. : _(Metro Trajectory Similarity Search): Given a target trajectory \(\text{Tr}_{o}\) and a trajectory set \(\text{TrSet}\), a similarity measure function, and a similarity threshold \(\epsilon\), the metro trajectory similarity search is to find trajectories from \(\text{TrSet}\) that satisfy the conditions of Equation (7)._  
\[\left\{ \begin{aligned} \text{Tr}_{i}\in\text{TrSet}\\ \text{Sim}(\text{Tr}_{o},\text{Tr}_{i})\geq\epsilon\end{aligned} \right. \tag{7}\]  
The problem this paper attempts to address is defined as follows. Given a query trajectory, a similarity measure function, and a threshold, our goal is to find a group of trajectories from the metro trajectory set, each of which satisfies that similarity between it and the query trajectory above the predefined threshold.