# Review of Anomaly Detection Algorithms for Data Streams
## 6 Algorithm Complexity and Scalability Analysis
### 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 online-learning-based data stream anomaly detection algorithms, as shown in Table 11.  
1. osPCA algorithm: 1. Time complexity: O(d\({}^{2}\)*k), where d is the dimensionality of the data stream, and k is the number of computed principal components. 2. Space complexity: O(d). The algorithm updates the principal directions by copying target instances and does not require storing the entire covariance matrix or dataset. 3. Scalability: The scalability of the osPCA algorithm is relatively poor. In large-scale data stream environments, the computational cost of updating the principal directions limits its scalability. 2. OSHULL algorithm: 1. Time complexity: O(n), where n is the number of normal data points. With new normal data arrivals, the OSHULL algorithm can avoid recomputing the convex hull through online adaptivity. 2. Space complexity: O(n/m), where m is the number of nodes. The OSHULL algorithm needs to store convex hull and data point information, so its space complexity is proportional to the size of the dataset. However, the algorithm uses a distributed approach by dividing the dataset into multiple parts, which reduces the storage requirements per node through average allocation. 3. Scalability: The OSHULL algorithm has good scalability. The algorithm can adaptively adjust the convex hull, making it capable of handling different types and distributions of data. Additionally, since the dataset can be processed in a distributed manner, the algorithm can be applied to large-scale distributed systems. 3. Matrix Sketch-Based Data Stream Anomaly Detection Algorithm: 1. Time complexity: The time complexity mainly depends on the size of the matrix sketch and the rate of the data stream. The update and query operations of the matrix sketch are usually constant time complexity (O(1)). Therefore, the time complexity of the algorithm is typically linear or close to linear, i.e., O(n), where n is the size or length of the data stream. 2. Space complexity: The matrix sketch is a highly space-efficient data structure that typically requires minimal memory to store the sketch's state. Therefore, the space complexity of the algorithm is usually constant, i.e., O(1) or O(k), where k is the size of the matrix sketch. 3. Scalability: This algorithm generally has good scalability. The operations of the matrix sketch can be parallelized, allowing for easy parallelization of the algorithm to handle large-scale data streams. The size of the matrix sketch can also be adjusted as needed to accommodate different scales of data streams. 4. VFDT algorithm: 1. Time complexity: O(dvc), where d is the number of attributes, v is the maximum number of values per attribute, and c is the number of classes. 2. Space complexity: O(ddv*c), where l is the number of leaves in the tree. 3. Scalability: The VFDT algorithm has good scalability. It employs incremental learning, allowing it to handle large-scale data streams without loading the entire dataset into memory. 5. CVFDT algorithm, HAT algorithm: 1. Time complexity: In CVFDT and HAT algorithms, for each new sample, the algorithm determines whether to expand the current tree by computing theHoeffding bound. Therefore, the time complexity of the algorithm is typically approximately constant, i.e., O(1). * Space complexity: In CVFDT and HAT algorithms, each node only stores relevant statistical information rather than the complete dataset. Therefore, the space complexity of the algorithm is typically approximately constant, i.e., O(1). However, the HAT algorithm incorporates an adaptive sliding window that avoids storing excess window data, resulting in lower space complexity compared to the CVFDT algorithm. * Scalability: Both CVFDT and HAT algorithms have excellent scalability, maintaining model consistency and accuracy when processing large amounts of data.