# Review of Anomaly Detection Algorithms for Data Streams
## 6 Algorithm Complexity and Scalability Analysis
### Offline Learning Based Data Stream Anomaly Detection Algorithm  
This section details and compares the time complexity, space complexity, and scalability of the offline learning-based data stream anomaly detection algorithms, as shown in Table 9.  
1. K-means algorithm: 1. Time complexity: O(n*k*l*d), where n is the number of data points, k is the number of clusters, I is the number of iterations, and d is the dimensionality of the data. 2. Space complexity: O(n*d), as it requires storing the feature vectors of all data points. 3. Scalability: The scalability of the k-means algorithm in data streaming scenarios is relatively poor. It requires traversing all data points and updating cluster \begin{table}
\begin{tabular}{c c c c c c} \hline \hline
**Algorithm Type** & **Algorithm Type (Subtype)** & **Algorithm Name and Reference** & **Time Complexity** & **Space Complexity** & **Scalability** \\ \hline \multirow{5}{*}{Offline training} & Based on similarity of data distribution & MiLOF [29] & O(N+d) & O(N+d) & Overall poor \\ \cline{2-5}  & Based on distribution & NETS [30] & O(log n+d) & O(n*d) & \\ \cline{2-5}  & Based on & & & & \\ \cline{2-5}  & classification & EC-SVM [31] & O((l/a)*log\({}^{2}\)(n/a)) & O(d+log(n/a)) & Overall very poor \\ \hline \multirow{5}{*}{Offline training} & \multirow{5}{*}{Based on similarity of data distribution} & Storm [32] & - & - \\ \cline{2-5}  & & Storm1, 2, 3 [33] & O(l) & O(n*d) & \\ \cline{2-5}  & & MCOD [34; 35] & - & - & Overall better \\ \cline{2-5}  & & PMCOD [36] & O(N*d) & O(N*d) & \\ \cline{2-5}  & & DILOF [37] & O(log n+d) & O(n*d) & \\ \cline{2-5}  & & CODS [38] & O((l/a)*log\({}^{2}\)(n/a)) & O(d+log(n/a)) & \\ \cline{2-5}  & & EForestASD [39] & O(N*m*h) & O(N*m*d) & Overall very good \\ \cline{2-5}  & & partitioning & LSHifiorest [40] & - & - & Overall very good \\ \hline \hline \end{tabular}
\end{table} 
Table 10: Comparison of complexity and scalability of semi-online learning-based data stream anomaly detection algorithms. \begin{table}
\begin{tabular}{c c c c c c} \hline \hline
**Algorithm Type** & **Algorithm Type (Subtype)** & **Algorithm Name and Reference** & **Time Complexity** & **Space Complexity** & **Scalability** \\ \hline \multirow{5}{*}{Online learning} & Based on similarity of data distribution & osPCA [41] & O(d\({}^{2}\)*k) & O(d) & Overall poor \\ \cline{2-5}  & & OSHULL [42] & O(n) & O(n/m) & Overall poor \\ \cline{2-5}  & & The deterministic flow update algorithm [43] & & & \\ \cline{2-5}  & Based on matrix sketch & The stochastic stream update algorithm [43] & & & \\ \cline{2-5}  & & A framework of virtual war room and matrix sketch-based streaming anomaly detection [44] & & & \\ \cline{2-5}  & & VFDT [45] & O(d*w*c) & O(l*d*w*c) & \\ \cline{2-5}  & & CVFDT [46] & & & \\ \cline{2-5}  & Based on decision trees & HAT [47] & O(l) & O(l) & Overall better \\ \cline{2-5}  & & EFDT [48] & & & \\ \cline{2-5}  & & GAHT [49] & O(d*v*c*h) & O(l*d*v*c) & \\ \hline \multirow{5}{*}{Online deep learning} & ADA [50] & & & & \\ \cline{2-5}  & DAGMM [51] & & & & \\ \cline{1-1} \cline{2-5}  & & ARCUS [52] & - & - & Overall very poor \\ \cline{1-1} \cline{2-5}  & & S-DPS [53] & & & \\ \hline \hline \end{tabular}
\end{table} 
Table 11: Complexity and scalability comparison of online learning-based data stream anomaly detection algorithms. centers. For large data streams or high update frequencies, it can result in significant computational and storage overhead. 2. KNN algorithm: 1. Time complexity: O(n*m*d), where n is the number of data points, m is the number of training samples, and d is the dimensionality of the data. 2. Space complexity: O(n*d), as it needs to store the feature vectors of all data points. 3. Scalability: The KNN algorithm has relatively poor scalability in data streaming scenarios. It requires traversing all data points and calculating distances. As the data stream increases, the computational and storage overheads keep growing. 3. LOF algorithm: 1.