## 3 STRP-DBSCAN
### Spatial-Temporal Random Partition  
The most significant improvement of STRP-DBSCAN compared to RP-DBSCAN is the spatial-temporal random partition based on the spatial and temporal information contained in the trajectory data, respectively. In the spatial dimension, each data point is assigned to the cell and sub-cell to which it belongs according to its positional coordinates in each dimension. Meanwhile, in the time dimension, the time value of the data point in each cell is randomly selected as the partition key for that cell, and cells with the same partition key will be assigned to the same partition. The algorithm stores the information about the data points in the cells, as well as the sub-cells in a two-level cell dictionary, i.e., a general summary of the dataset, and sends it to each computing node by broadcasting, which enables different computing nodes to achieve local clustering despite not knowing the complete dataset. The implementation of the spatial-temporal random partitioning is shown in Algorithm 1.  
```
Input: dataset \(D\) containing \(N\) data points, radius parameter Eps, minimal points number within the radius MinPts, number of partitions \(k\), approximation parameter rho Output: cells [\(C_{1}\),\(C_{2}\),...], cell dictionary \(M\), partition data {\(P_{1}\),...\(P_{k}\)}
1 //Spatial-Temporal Randomization Partition
2 class Spatial_Time_Pseudo_Random_Partitioning(\(D\), Eps, rho, \(k\))
3 //Assign points to different cells
4 method MAP(NULL, point \(p\))
5 \(cid\) = the cell id of point \(p\);
6 EMT(\(cid\), \(p\));
7 //Partition according to time
8 method REDUCE(\(cid\), {\(p_{1}\), \(p_{2}\),...]}
9 C = {\(p_{1}\), \(p_{2}\),...];
10 grid = random(time in C);
11 EMT(\(pid\), C);
12 method REDUCE(\(pid\), {\(C_{1}\), \(C_{2}\),...]}
13 new\(P_{pid}\) = [\(C_{1}\), \(C_{2}\),...];
14 EMT(\(pid\), \(newP_{pid}\));
15 //Cell dictionary construction
16 class CELL_DICTIONARY_BUILDING({\(P_{1}\),...\(P_{k}\)}, Eps, rho)
17 method MAP(\(pid\), \(newP_{pid}\))
18 for each\(C_{i}\)(\(newP_{pid}\)do
19\(C_{i}\) = {\(s_{1}\), \(s_{2}\),...];
20 new\(M_{pid}\) = make a cell dictionary;
21 EMT(NULL, \(newM_{pid}\));
22 method REDUCE(NULL, \(newM_{1}\), \(newM_{2}\),..., \(newM_{k}\))
23\(M\) = \(newM_{1}\cup newM_{1}\cup\cdots\cup newM_{k}\);
24 EMT(NULL, \(M\));
```  
**Algorithm 1** Spatial-Temporal Random Partition  
Figure 7 shows an example of spatial-temporal partition. Due to the normalization, values for all dimensional attributes of the data are in the range [0, 1]. All data points are mapped into a 3D data space of cells, as shown in Figure 6(a). Cells of different colors are distributed to different computing nodes. Although the partition is performed in 3D data space, the 2D plan view consisting of the time axis and the latitude axis allows for a more intuitive and obvious demonstration of the data partitioning. Figure 6(b) shows the original data point distribution in the 2D plan of the time axis and the latitude axis, and Figure 6(c) shows the partition results of Figure 6(b). Cells that contain data points at the same height in the time axis but differ in the latitude axis are assigned to the same partition.