# Review of Anomaly Detection Algorithms for Data Streams
## 6 Algorithm Complexity and Scalability Analysis
### Semi-Online-Learning-Based Data Stream Anomaly Detection Algorithms
* MCOD algorithm: * Time complexity: O((1/a)*log(n/a)), where a is the proportion of data points in the micro-cluster, and n is the total number of data points. * Space complexity: O(d*log(n/a)), where d is the dimension of non-empty cells in the given window. * Scalability: The MCOD algorithm has relatively low time and space complexity, making it moderately scalable. * pMCOD algorithm: * Algorithm complexity: The pMCOD algorithm can process data streams in parallel, and its specific time and space complexity depend on the implementation and characteristics of the dataset. Therefore, the time and space complexity are not mentioned in the corresponding articles. However, it has been proven to be an efficient algorithm with lower complexity than the MCOD algorithm. * Scalability: The pMCOD algorithm improves scalability by introducing parallelization. It divides the dataset into multiple subsets and processes them simultaneously, thereby improving scalability. The pMCOD algorithm is superior to the MCOD algorithm in terms of time complexity, space complexity, and scalability, and it can effectively handle large datasets. * DILOF algorithm: * Time complexity: O(1), the DILOF algorithm uses density-based sampling and a new strategy called \"skip scheme\" to greatly reduce the time complexity. * Space complexity: Approximately O(n*d), where n is the data volume and d is the data dimension. * Scalability: The DILOF algorithm has good scalability. The detection stage of the DILOF algorithm uses an incremental approach and the skip scheme, which avoids excessive time complexity when updating neighborhood information upon inserting new data points, thereby maintaining high efficiency in processing large amounts of data. * CODS algorithm: * Algorithm complexity: The CODS algorithm can process data streams in parallel, and its specific time and space complexity depend on the implementation and characteristics of the dataset. Therefore, the time and space complexity are not mentioned in the corresponding articles. * Scalability: The CODS algorithm has an advantage in scalability. By utilizing the parallel computing capability of GPUs, the algorithm can handle multiple concurrent data streams and perform anomaly detection in a shorter time. Furthermore, with the improvement of GPU computing power, the performance of the algorithm can be further enhanced. * iForestASD algorithm:
* Time complexity: O(N*m**h), where N is the number of data points in the window, m is the number of trees, and h is the average height of the trees. The time complexity of the iForestASD algorithm depends on the number of data points in the window and the number of trees. * Space complexity: O(N*m**d), where d is the data dimension. The space complexity of the iForestASD algorithm is related to the size of the data in the window, the number of trees, and the feature dimension of newly arrived data points. * Scalability: The iForestASD algorithm has good scalability. The algorithm uses a sliding window approach to handle streaming data, allowing real-time updates of the isolation forest model and calculation of anomaly scores, thus being able to adapt to continuously incoming new data. * LSHforest algorithm:
* Algorithm complexity: The time and space complexity of the LSHforest algorithm are not mentioned in the corresponding articles. However, overall, the algorithm has low complexity and is related to the data volume and data dimension in the window. * Scalability: The LSHforest algorithm has good scalability. The algorithm has low complexity and is not sensitive to parameters, making it suitable for scalable anomaly detection. In conclusion, on the basis of the information in Table 10, the complexity and scalability of data stream anomaly detection algorithms using semi-online learning can be summarized as follows:  
Regarding algorithms that combine offline training with batch updates, their overall scalability is lower compared to algorithms that combine offline training with incremental updates.