# An Implementation of the HDBSCAN* Clustering Algorithm
## 3 Materials and Methods
### Main Development Phase
#### 3.4.4 Add Concurrency  
During the review of the Java reference implementation, several blocks of logic with high asymptotic complexity were identified. For example, the first step in the algorithm \begin{table}
\begin{tabular}{c c c} \hline
**Dataset Size** & **Number of Clusters** & **Exemplar Number** \\ \hline
100 & 5 & 12 \\
2000 & 4 & 35 \\
2000 & 8 & 39 \\
5000 & 4 & 54 \\
5000 & 8 & 60 \\
9000 & 100 & 167 \\
10,000 & 4 & 74 \\
50,000 & 3 & 161 \\
100,000 & 200 & 423 \\ \hline \end{tabular}
\end{table} 
Table 2: Examples of exemplar numbers calculated for different scenarios. to compute the core distances has a time complexity of \(O(n^{2})\). The second step in the algorithm is to compute the extended minimum spanning tree graph. This also takes \(O(n^{2})\). These findings are consistent with the descriptions the authors of [8] provide in their detailed complexity analysis of the HDBSCAN* algorithm. Rather than repeat all the details from this complexity analysis here, a more practical approach to understanding the performance of the algorithm is taken. The execution times of each major step of the algorithm are collected when training models using a variety of datasets. These are not meant to be rigorous experiments. Only a general idea of where the algorithm spends most of its time is needed at this point. In fact, the first step in the algorithm which computes the core distances consistently takes the longest out of all the steps. It is the next step that computes the extended minimum spanning tree graph that takes the second longest. Therefore, it makes sense to focus on parallelizing these two steps of the algorithm, starting with the core distance calculations. In Java 8, there are several APIs which can be used for implementing concurrency. An initial attempt is made to use a ForkJoinPool which is designed for work that can be broken into smaller pieces recursively. This implementation does not perform well and ended up taking longer in all cases than the sequential version of the code. Next, the core distance calculations were implemented using the ExecutorService API. For datasets larger than 5000 records, executing this logic in parallel with multiple threads is always faster than the sequential implementation. For small datasets, the overhead of starting and shutting down the ExecutorService appears to degrade performance. For this reason, when the HdbscanTrainer is instantiated with the variable numThreads equal to one, this condition will be detected, and the original sequential core distance calculation will be executed. This provides a mechanism to achieve optimal performance results for smaller datasets. The use of Java's Parallel Streams API is not explored here since some cumbersome steps would have been required to transform the existing data structures into streams-compatible datatypes. Exact measurements comparing various core distance calculation execution times are not observed or presented here. This analysis is too fine grained. It is more important to focus on measuring the time it takes to execute the complete algorithm, since that is how the code will be used in practice. Such measurements will be presented and discussed in the following section. The next step of this task is to parallelize the block of logic that computes the extended minimum spanning tree graph. Similar to the core distance calculation, there is a loop nested within a loop which causes the time complexity to be \(O(n^{2})\). Carefully reviewing this logic, again with the intention of executing it in parallel, reveals that each execution of the outer loop cannot be safely performed in separate threads. Each subsequent execution of the outer loop depends on a result from the previous executions of the loop. This indicates each iteration of the outer loop needs to be made sequentially. Instead, an implementation which again uses the ExecutorService API is developed which submits only the code within the inner loop to a thread pool executor.