# Review of Anomaly Detection Algorithms for Data Streams
## 6 Algorithm Complexity and Scalability Analysis
### Semi-Online-Learning-Based Data Stream Anomaly Detection Algorithms  
This section provides a detailed introduction and comparison of the time complexity, space complexity, and scalability of semi-online-learning-based data stream anomaly detection algorithms, as shown in Table 10.  
1. MiLOF algorithm: 1. Time complexity: The first stage is to observe the data stream and divide it into several subsets, with a time complexity of O(d*n), where d is the dimension of the input vector and n is the number of data points. The second stage is to calculate the LOF value of each subset and store it in memory, with a time complexity of O(k*n*logn), where k is the maximum number of data points stored in memory. The third stage is to calculate the LOF value of new data points and update the LOF value of subsets, with a time complexity of O(d*k*logk). Therefore, the total time complexity of the MiLOF algorithm is O(dn + knlogn + dklogk). 2. Space complexity: O(k*d), the space complexity of the MiLOF algorithm is proportional to the number of data points and the dimension of data points stored in memory. 3. Scalability: The MiLOF algorithm has good time complexity and scalability. The algorithm can detect anomalies in real-time data streams and can adapt to datasets of different sizes through batch training. 2. NETS algorithm: 1. Time complexity: The time complexity of NETS is 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. 2. Space complexity: The space complexity of NETS is O(d/a), where d is the dimension of non-empty cells in the given window. This is because NETS needs to maintain d-dimensional cells and the neighbor counts of each data point. 3. Scalability: The NETS algorithm is highly scalable, even for high-dimensional data streams. In addition, the NETS algorithm can handle multiple data streams and can be extended to different application scenarios. 3. EC-SVM algorithm: 1. Time complexity: O(n\({}^{3}\)*d), where n is the number of training samples and d is the data dimension. The EC-SVM algorithm needs to calculate the kernel matrix and select support vectors and optimize model parameters. 2. Space complexity: O(n\({}^{2}\)*d), the algorithm needs to store the kernel matrix. 3. Scalability: For large-scale datasets and high-dimensional feature spaces, the computational cost of the EC-SVM algorithm is very high, and its scalability is poor. When the sample size and dimension are very large, the algorithm becomes very time consuming, and the memory requirement is also very high. 4. Storm algorithm: 1. Time complexity: O(N), where N is the amount of data in the sliding window and d is the data dimension. The algorithm processes the data stream usinga sliding window, and the window size determines the computational cost of the algorithm. * Space complexity: O(N), the data window needs to store the data in the sliding window, and the window size determines the storage cost. * Scalability: The Storm algorithm has good scalability in handling large-scale data streams and scenarios with high real-time requirements. The Storm algorithm uses a sliding window to process data streams, and the algorithm can adapt to continuously incoming new data and perform anomaly detection in real-time or near real-time environments. * Storm1, 2, 3 algorithms: * Time complexity: O(log n), where n is the size of the data stream. * Space complexity: The space complexity is at the level of O(n*d), where the space complexity of Storm1 is relatively the largest, followed by Storm2, and Storm3 has the smallest space complexity. * Scalability: The Storm1 algorithm needs to fully store all window objects, so it occupies a lot of memory space, and its scalability is limited. The Storm2 algorithm reduces accuracy but significantly reduces the space it occupies, improving the algorithm's scalability. The Storm3 algorithm continues the approach of Storm2 and greatly improves the algorithm's scalability, making it suitable for time- and space-constrained scenarios.