## 4 PER-SAC based Optimal Parameter Autotuning for DBSCAN
### PER-SAC Algorithm
\begin{aligned} \frac{\theta_{p}^{(l-1)}}{\pi_{p}}, \text{ if }p=\text{Eps;}\\ \max\{\left[\frac{\theta_{p}^{(l-1)}}{\pi_{p}}+\frac{1}{2}\right],1\},\text{ otherwise.}\end{aligned} \right. \tag{7}\]

Thus, the computational complexity is O (\(N\)) when there is no recursive structure, where \(N=\theta_{p}^{(0)}/\theta_{p}^{(L)}=(\pi_{p})^{L}\). Our optimal parameter autotuning framework with an \(L\)-layer recursive structure simply takes \(L\cdot(\pi_{p})\), reducing the complexity from O (\(N\)) to O (\(\log N\)). ## 5 Experiments

### Experiment Settings

1. Dataset

The experiments use ship trajectory data to validate the proposed algorithms. The adopted dataset is the real ship data of public AIS in the East China Sea [36]. Since the proposed STRP-DBSCAN algorithm first preprocesses the dataset, for the real AIS dataset, the abnormal data points with a sailing speed of less than 2 knots and greater than 60 knots are removed, and the minute is set as the smallest time measurement unit. After preprocessing, two kinds of labeled datasets and unlabeled datasets are obtained, respectively. It is worth stating that the spatial-temporal trajectory clustering algorithm proposed in this paper is also applicable to other types of trajectory data. 2. Evaluation metrics

The experiments will evaluate the algorithm in terms of both clustering efficiency and clustering accuracy. We evaluate the efficiency of the clustering algorithm in terms of the overall time it takes to obtain the final clustering results. At the same time, there are many common metrics that can be used to evaluate the goodness of the clustering results, i.e., clustering accuracy. For unlabeled data, we use the silhouette coefficient [37] and the Davies-Bouldin index [38] to evaluate clustering accuracy. For labeled data, we use the normalized mutual information (NMI) [39] and the adjusted Rand index (ARI) [40] for clustering accuracy measurement. Among them, except for the DBI index, the larger the value of the other three evaluation indexes, the better the clustering effect. For the execution efficiency of the algorithm, we used 10 runs of the algorithm and averaged the running time to evaluate the execution efficiency of the algorithm. 3. Experimental configuration

The STRP-DBSCAN is a distributed parallel clustering algorithm based on the Spark implementation. The experimental information is shown in Table 2.

Table 3 shows the experimental information about the optimal parameter autotuning framework. For all baseline algorithms used in the experiments, the open-source imple \begin{table}
\begin{tabular}{c c} \hline \hline
**Hardware/Software** & **Parameters** \\ \hline CPU & Intel® CoreTM i5-1040F CPU @ 2.90 GHz \\ \hline Hadoop & Hadoop3.2 \\ \hline JDK & JDK 1.80\_211 \\ \hline Scala & Intel AVX512 \\ \hline \# of cores & 12 \\ \hline Spark & Spark-3.1.3 \\ \hline Memory & 32 GB DDR4 \\ \hline Operation system & CentOS Linux release 7.9.2009 (Core) \\ \hline \hline \end{tabular}
\end{table} 
Table 2: Experimental configurations of STRP-DBSCAN. mentation libraries or those provided by the authors were used and the experiments were conducted in the following environments. ### Evaluation of STRP-DBSCAN

The proposed STRP-DBSCAN algorithm is first evaluated. In this part of the experiments, we use three unlabeled datasets of size 8.5K, 50K, and 217K after preprocessing and normalization, respectively. We compared STRP-DBSCAN with the DBSCAN algorithm [5] and one of state-of-the-art parallel DBSCAN algorithms, i.e., RP-DBSCAN [10]. These two algorithms do not optimize the spatial-temporal data by preprocessing. To be fair, we uniformly use the preprocessed and normalized datasets for the experiments. In order to exclude any influence on the results, all tested algorithms used the same clustering parameters, i.e., _Eps_ is set to 0.02 and _MinPIs_ is set to 100 for all datasets. For the three datasets of different data sizes, Table 4 records the computation time of the three clustering algorithms.