# Review of Anomaly Detection Algorithms for Data Streams
## 6 Algorithm Complexity and Scalability Analysis
### Offline Learning Based Data Stream Anomaly Detection Algorithm
Time complexity: O(n2*d), where n is the number of data points, 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 LOF 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. 4. OCSVM algorithm: 1. Time complexity: O(n2*d) or O(n3*d), where n is the number of data points, and d is the dimensionality of the data. 2. Space complexity: O(n*d). It needs to store the kernel matrix. 3. Scalability: The traditional OCSVM algorithm has poor scalability in data-streaming scenarios. Since OCSVM is trained on finite samples, each time a new sample arrives, the entire model needs to be retrained, including solving the quadratic programming problem. This leads to increased time and computational resource overheads with growing data, limiting the scalability of OCSVM. 5. iForest algorithm: 1. Time complexity: O(n*m*log(n)), where n is the number of data points, and m is the number of trees. The average time complexity for constructing a single isolation tree is O(n*log(n)). 2. Space complexity: O(n*m), as it needs to store the input data and the collection of isolation trees. 3. Scalability: The iForest algorithm has a time complexity linearly dependent on the number of data points, making it suitable for handling large-scale data. Additionally, the algorithm can be parallelized efficiently on multi-core processors, further enhancing its scalability. 6. RS-Hash algorithm: 1. Time complexity: O(1). The RS-Hash algorithm is a hash-based fast anomaly detection algorithm. For each incoming data point, it only requires hash computations and comparison operations, resulting in constant time complexity. 2. Space complexity: O(m), as it needs to store the hash table and related data structures, where m is the size of the hash table. 3. Scalability: The traditional RS-Hash algorithm exhibits good scalability in data streaming scenarios. It only requires simple hash computations and comparison operations for each incoming data point, making it suitable for high-throughput data stream scenarios. * DeepAnT algorithm:
* Time complexity: Depends on the architecture and number of parameters of the deep neural network. Training deep neural networks usually requires significant computational resources and time, resulting in high time complexity. * Space complexity: The algorithm needs to store the parameters of the trained deep neural network, and the space complexity is usually high. * Scalability: The DeepAnT algorithm has relatively poor scalability in data streaming scenarios. The training and inference processes of deep neural networks are typically time-consuming, and as the data stream increases, the computational and storage overheads significantly increase. * SISVAE algorithm:
* Time complexity: The time complexity of the SISVAE algorithm depends on the structure and training process of the Variational Autoencoder (VAE). Typically, VAE training requires significant computational resources and time, resulting in a high time complexity. * Space complexity: The algorithm needs to store the parameters of the trained VAE, and its space complexity depends on the network structure and the number of parameters, which is usually high. * Scalability: The SISVAE algorithm exhibits relatively poor scalability in data-streaming scenarios. The training and inference processes of the VAE are typically time consuming, and as the data stream increases, the computational and storage overheads significantly increase. * GANomaly algorithm:
* Time complexity: Training Generative Adversarial Networks (GAN) usually requires substantial computational resources and time, resulting in a high time complexity. * Space complexity: The algorithm needs to store the parameters of the trained generators and discriminators, and the space complexity is usually high.