# Review of Anomaly Detection Algorithms for Data Streams
## 6 Algorithm Complexity and Scalability Analysis
### Online-Learning-Based Data Stream Anomaly Detection Algorithms
* EFDT algorithm, GAHT algorithm:
* Time complexity: Both algorithms have a similar time complexity of O(dvc+h), where d is the number of attributes, v is the maximum number of values per attribute, c is the number of classes, and h is the maximum depth of the tree. However, the GAHT algorithm incorporates pruning operations, resulting in lower time complexity compared to the EFDT algorithm. * Space complexity: Both algorithms have a similar space complexity of O(ldv+c), where l is the number of leaves in the tree. However, the GAHT algorithm incorporates pruning operations, resulting in lower space complexity compared to the EFDT algorithm. * Scalability: The EFDT algorithm and GAHT algorithm have excellent scalability. The algorithms have low complexity. Additionally, the EFDT algorithm and GAHT algorithm can be combined with other incremental learning algorithms to further improve their scalability and adaptability. * Online Deep Learning-Based Data Stream Anomaly Detection Algorithm:
* Algorithm complexity: Examples of online deep learning anomaly detection algorithms, such as the ADA algorithm, DAGGM algorithm, ARCUS algorithm, and S-DPS algorithm, generally have variable time and space complexity. Their complexity depends on the type of deep neural network model and the training process, which is typically high. * Scalability: Online deep learning-based anomaly detection algorithms have overall poor scalability. The training and updating processes of deep neural networks require significant computational resources and time, limiting the scalability of the algorithms. Handling large-scale data streams may require techniques such as distributed computing or model compression to improve scalability. In summary, considering Table 11, the complexity and scalability of data stream anomaly detection algorithms based on online learning can be summarized as follows:  
1. Online deep learning algorithms generally have lower scalability compared to online shallow learning algorithms. This is because deep learning algorithms often involve the training and storage of deep neural networks, which adversely affects the scalability of online deep learning algorithms. 2. Among online shallow learning algorithms: Those based on matrix sketch algorithms convert data calculations into matrix sketch calculations, providing unique advantages in terms of complexity and scalability. Thus, they have the best scalability. Those based on decision tree algorithms do not require normalization and have unique advantages in feature extraction, resulting in relatively good scalability. Those based on Similarity of Data Distribution algorithms have complexity related to statistical features of the data, requiring normalization and feature extraction steps, resulting in relatively poor scalability compared to the other three categories. Overall, considering Tables 8-11, the scalability of offline-learning-, semi-online-learning-, and online-learning-based data stream anomaly detection algorithms can be summarized as follows:  
1. Offline-learning-based data stream anomaly detection algorithms * Low scalability: Offline-learning-based algorithms typically require batch processing and model training over the entire dataset, which can pose computational and storage challenges for large-scale datasets or high-speed data streams. * Difficult to adapt to changes in real time: Since the algorithms are trained offline, they may not adapt to new patterns or changing concepts in the data stream in a timely manner, requiring retraining of the entire model. 2. Semi-online-learning-based data stream anomaly detection algorithms: * High scalability: Semi-online-learning-based algorithms typically adapt to changes in the data stream through batch updates or incremental updates. They can partially utilize previous models or samples, reducing the computational and storage requirements and thus improving scalability.