## 5 Method Design
### Trajectory Similarity Search
#### 5.3.3 Filtering Strategy  
In this section, we introduce how the scheduler conduct merging and filtering operation. The purpose of merging is to combine different segments with the same identity. The implementation of the merge thread is shown in Algorithm 2. ``` Input: task1, task2, taskQueue, isFilter, threshold. Output: taskQueue. 1 procedureMergeThread (task1, task2, isFilter, threshold)
2 resTr\(\leftarrow\varnothing\)
3 maxM\(\leftarrow\lfloor length(SPCL)\times(1-threshold)\rfloor\)
4 Tr\(Set1\leftarrow\)task1
5 Tr\(Set2\leftarrow\)task2
6 Set\(C\leftarrow\)TrSet1\(\cap\)TrSet2//cardId in TrSet1 and TrSet2
7 Set\(A\leftarrow\)TrSet1\(-\)SetC
8 Set\(B\leftarrow\)TrSet2\(-\)SetC
9 forcall\(A\in\)SetCdo
10\(total\leftarrow\)missCount\((TrSet1,cardId)+missCount(TrSet2,cardId)\)
11 if\(isFilter==\)true\(\&\)total\(>\)\(maxM\)then
12 Discard(TrSet2,cardId)
13 else
14\(uTr\leftarrow\)TrSet1\((cardId)\cup\)TrSet2\((cardId)\)
15 Tr\((cardId,uTr)\to\)resTr
16 endif
17 endfor
18 forcardId\(\in\)SetAdo
19\(total\leftarrow\)missCount\((TrSet1,cardId)+maxMissCountInSet2\)
20 if\(isFilter==\)true\(\&\)total\(>\)\(maxM\)then
21 Discard(TrSet1,cardId)
22 else
23 Tr\((cardId,TrSet1(cardId))\)\(\rightarrow\)resTr
24
25
26
27
28
29
30





PMMTss adopts two filtering strategies: the first filtering strategy is to extract candidate trajectory points from the index by the spatiotemporal information of the target points. The filtering algorithm is the second filtering strategy. The steps of the filtering algorithm are as follows: first, it calculates the number of points where a candidate trajectory does not overlap with the target trajectory. Second, it calculates the similarity score between the candidate segment and the target trajectory. We remove the candidate segment if the score is less than the lower bound. It means all derivatives of this candidate cannot satisfy the filtering threshold. In this way, trajectory segments that are impossible to become the members in final results are deleted in the intermediate rounds, reducing the number of candidate trajectories and computational costs for the next rounds. ## 6 Experiment

### Experimental Setup

The experimental setup includes two parts: the first is data pre-processing and index building, and the second is service deployment and performance evaluation. The first part is a Spark cluster with one coordinator and five workers. Each node is equipped with the same hardware and software configurations. Specifically, two CPUs with 32 cores (Intel (R) Xeon (R) Silver 4216 CPU), memory size 32 GB (DDR4), one disk with 4 TB storage space, and network bandwidth is 10 Gb. The version of Hadoop is 2.7.7 and the Spark version is 3.2, the OS is CentOS 7.6, and the JDK is 1.8. The search service is deployed and evaluated on a single node, which has the same configuration. ### Dataset

The dataset was collected from the Shenzhen Metro System for the three months from November 2018 to January 2019. The dataset involves 6.97 million smart cards with a total of 265 million records. Details of the fields in the dataset are shown in Table 2. A group of ordered records produced by a smart card formulates a passenger trajectory, and all trajectories formulate a trajectory set. The length of these passenger trajectories is 34 on average, and 95% of the trajectory lengths were less than 100. The trajectory set includes 6.97 million passenger trajectories. \begin{table}
\begin{tabular}{c c c} \hline \hline
**Field** & **Value** & **Description** \\ \hline card\_no & 6683 **** & Smart card ID \\ station & Grand Theater Station & Metro station name \\ deal\_type & entry & Type of ticketing \\ deal\_date & 31 October 2018 22:45:59 & Time of ticketing \\ \hline \hline \end{tabular}
\end{table} 
Table 2: Detail of passenger record field. We first randomly select 4000 trajectories as samples out of 6.97 million trajectories with a sampling rate of 0.05%. The lengths of these sample trajectories are from 4 to 64.