SDOoop: Capturing Periodical Patterns and Out-of-phase Anomalies in Streaming Data Analysis
Alexander Hartl Félix Iglesias Vázquez Tanja Zseby







SDOoop: Capturing Periodical Patterns and Out-of-phase Anomalies in Streaming Data Analysis
    Alexander Hartl 0000-0003-4376-9605
Institute of Telecommunications 

TU Wien

1040 Wien, Austria

me@alexhartl.eu
Félix Iglesias Vázquez 0000-0001-6081-969X
Institute of Telecommunications 

TU Wien

1040 Wien, Austria

felix.iglesias@tuwien.ac.at
Tanja Zseby 0000-0002-5391-467X
Institute of Telecommunications 

TU Wien

1040 Wien, Austria

tanja.zseby@tuwien.ac.at

    September 9, 2024
=====================================================================================================================================================================================================================================================================================================================================================================================




§ ABSTRACT 
Streaming data analysis is increasingly required in applications, e.g., IoT, cybersecurity, robotics, mechatronics or cyber-physical systems. 
Despite its relevance, it is still an emerging field with open challenges. 
SDO is a recent anomaly detection method designed to 
meet requirements of speed, interpretability and intuitive parameterization. In this work, we present SDOoop, which extends the capabilities of SDO's streaming version to 
retain temporal information of data structures. SDOoop spots contextual anomalies undetectable by traditional algorithms, while enabling the inspection of data geometries, clusters and temporal patterns. 
We used SDOoop to model real network communications in critical infrastructures and extract patterns that disclose their dynamics. 
Moreover, we evaluated SDOoop with data from intrusion detection and natural science domains and obtained performances equivalent or superior to state-of-the-art approaches. 
Our results show the high potential of new model-based methods to analyze and explain streaming data.
Since SDOoop operates with constant per-sample space and time complexity, it is ideal for big data, being able to instantly process large volumes of information. 
SDOoop conforms to next-generation machine learning, which, in addition to accuracy and speed, is expected to provide highly interpretable and informative models.  



Contextual Anomalies, Streaming Data Analysis, Anomaly Detection, Communication Networks, Critical Infrastructures






§ INTRODUCTION

In data stream processing, data points v_j ∈ℝ ^D consistently arrive at monotonically increasing times t_j ∈ℝ for j=1,2,… 
Due to this steady acquisition,
analysis algorithms face the challenge of discovering knowledge in unbounded data that substantially accumulates in a short time.
In such a context, real-life applications dismiss batch-mode operation while demanding fast online processing able to update models and parameters to concept drift.
Here, “updating models and parameters” does not only mean adapting to new patterns and classes, but also forgetting those that have become obsolete.

In anomaly/outlier detection (OD), 
we commonly set a sliding window (or an observation horizon) w that establishes the memory length for which space geometries are remembered. 
Hence, the anomaly is defined: (a) either based on the neighborhood of a data point within w (e.g., Exact- and Approx-STORM <cit.>), or (b) by comparing to a model that evolves with w (e.g., Robust Random Cut Forests <cit.>). 
In both cases, note that the comparison reference is purely static (or geometric) relative to the point of comparison at the instant of comparison. That is, the data within w (or the model used instead) is a snapshot.  
While this is not a problem for many types of anomalies, most traditional methods are blind to identify contextual anomalies. A contextual (aka. conditional or out-of-phase) anomaly “occurs if a point deviates in its local context” <cit.>, i.e., if it happens outside its usual time. Consider a method whose w spans a one-week period. If a cluster occurs exclusively during weekends, but a data point of this cluster accidentally appears on a Wednesday, this method will not identify it as an anomaly, but as a normal inlier instead. 



Here, we present SDOoop 
(SDO out-of-phase), an algorithm for OD in streaming data whose models 
store temporal information.  
While retaining constant per-sample space and time complexity and keeping intact the functionalities to detect other types of anomalies,
SDOoop is also able to identify contextual anomalies and capture periodical patterns that explain the time behavior of the data bulk.
SDOoop builds models 
by sampling a fixed number of data points at representative locations in feature space, called observers.
To escape dependence of the data volume, it uses an exponentially weighted moving average (EWMA) to estimate model information from the arriving data mass. At the same time, observers  hold temporal information as coefficients of Fourier transforms (FT). 
Thus, for a specific time of interest t, observers “twinkle” to show only the most representative model for time t.
The simple example in Fig. <ref> can give an intuition of the distinctive capabilities of SDOoop when compared with alternatives. In the figure, the internal model (incrementally updated) is formed by the red and orange points, which represent observers. 
Observers are placed in areas of considerable density to see the data mass around. Note that, while the orange observer stands for a cluster that occurs at a continuous pace, the red observer represents a cluster that exhibits a temporal behavior. Consequently, the red observer twinkles accordingly, the drawn gray curve showing the inverse FT of its captured FT coefficients.  
If a contextual anomaly happens, closest observers will not be awake, hence it will be detected as an anomaly by far observers.   








Our work advances the research on observers-based unsupervised learning, which originated SDO <cit.>, SDOstream <cit.> and SDOclust <cit.>.  
The remainder of this paper is structured as follows:
In Section <ref>, we introduce observers-based OD.
Section <ref> describes SDOoop and explains its parameters. 
SDOoop is evaluated in Section <ref>. 
In Section <ref> we explore related research efforts and contrast them to the problem solved here.
Finally, we summarize the main ideas and contributions in Section <ref>. 
To enable reproducibility, we make all our source code available in our repository 
<https://github.com/CN-TU/tpsdos-experiments>.




§ OBSERVERS-BASED OUTLIER DETECTION
 
The Sparse Data Observers (SDO) method <cit.> for OD on static datasets is the foundation of our current proposal. 
In a nutshell, SDO works as follows:
(a) Randomly sample points from the dataset, which will be called “observers”.
(b) Each data point in the dataset is only observed by the x nearest observers, resulting in each observer performing a different number of observations. 
(c) Remove idle observers, i.e., with the smallest number of observations. Remaining observers are termed active. 
(d) For each data point, compute an outlier score as median distance to the x nearest active observers.
Hence, observers capture the main shapes of the data in a low-density model and outlier scores are calculated as distances to points in this model. Removing idle observers minimizes the chances of outliers being part of the model.  
The observer-approach also holds for SDOstream <cit.>, which adapts the algorithm for a streaming setting by continuously sampling new observers and using EWMA for computing observations.

In this paper, we predominantly adhere to the notation of <cit.>. Hence, we denote the observers set as Ω and, accepting a slight abuse of notation, we denote by ω∈Ω both an abstract observer and its feature vector. Furthermore, P_ω denotes ω's observations, where P_ω∈ℕ_0 for SDO and P_ω∈ℝ_0^+ for SDOstream. Hence, P_ω  counts the number of data points for which ω belongs to the x nearest observers with an algorithm parameter x ∈ℕ. Observers with insufficient P_ω are thus disregarded for outlier scoring.
In contrast to SDO and SDOstream, SDOoop replaces the number of observations P_ω with a temporal function, allowing active observers to become temporarily idle (i.e., asleep) and reappear dynamically in accordance with the temporal pattern of the underlying clusters. Therefore, it is possible to construct an active observers set representative for the data stream at the current time and, hence,
to detect data points that do not meet the established temporal pattern, i.e., contextual anomalies.








§ SDOOOP
 




We describe the construction of our proposal. 
Main symbols and notation are shown in Table <ref>. 
We denote by [ N_bins ] with N_bins∈ℕ the set {0,…,N_bins-1} and by d: ℝ ^D×ℝ^D→ℝ^+ a distance function (e.g., Euclidean). 
Our method enables the model to absorb temporal patterns in processed data streams. To describe this, we consider data streams satisfying the following definition.


	
	For a given data stream, let γ( v, t) ∈ℝ_0^+ denote the expected rate of arriving data points at location v ∈ℝ^D and time t ∈ℝ. Therefore, γ( v, t)Δ v Δ t stands for the expected number of data points seen in a volume Δ v and time interval Δ t. We say that the stream exhibits T_0-periodic patterns with T_0 ∈ℝ^+ if γ( v,t) is T_0-periodic, i.e., γ( v,t)=γ( v,t+T_0) for all v ∈ℝ^D, t ∈ℝ.


Definition <ref> is based on the expected rate of arriving data points. This means that, to reason about periodic behaviors, the random stream is modeled as generated by an underlying deterministic process.
In particular, a stationary stream exhibits T_0-periodic patterns for any T_0. 
Note that Definition <ref> does not include concept drift, which is tackled by SDOoop with a exponential sliding window.

To capture temporal patterns, we allow the observers' observations to be T_0-periodic. We represent and store the associated temporal functions in terms of their FT coefficients P_ω,n∈ℂ with ω∈Ω, n ∈ [N_bins].
To extract observers relevant for the current point in time from the model, we first define the q_id-percentile P_thr∈ℝ^+ of the observers' average observations P_ω,0, i.e.,

    P_thr = max{ρ∈ℝ^+  | |{ω∈Ω |   P_ω,0 < ρ}|≤ q_id|Ω|}.

Similar to previous work, P_thr allows us to require active observers to have a minimum number of observations in relation to the total time-averaged observation count.
Hence, we construct a view yielding the currently active observers 

    Ω_a = {ω∈Ω | {∑_n ∈ [N_bins] P_ω,n}≥ P_thr}

in terms of a lower-bound for the inverse FT, where {∑_n ∈ [N_bins] P_ω,n} evaluates the temporal shape of the observers' observations at the current time.

To narrow the scope to the most relevant information, we form sets from both Ω and Ω_a that only contain the x nearest points. Hence, for a point  v ∈ℝ^D we specify the set of nearest observers 𝒩( v)⊂Ω with |𝒩|  = min(x,|Ω|) and the set of nearest active observers 𝒩_a( v) ⊂Ω_a with |𝒩_a | = min(x,|Ω_a|), i.e.

    d( ω̃,  v )    ≤ d( ω,  v )  ∀ ω̃∈𝒩( v), ω∈Ω∖𝒩( v)   and
    
    d( ω̃,  v )    ≤ d( ω,  v )  ∀ ω̃∈𝒩_a( v), ω∈Ω_a ∖𝒩_a( v) .

Algorithm <ref> depicts the core process, discussed as follows.







 §.§ Algorithm Construction

Algorithm <ref> can be divided into three parts: establishing active observers Ω_a (line 1), scoring outlierness (line 2), and updating the model (lines 3-10). 
The core concept, which allows to capture periodical patterns, is based on Lemma <ref>.


	 
	For an observer ω∈Ω, let g(t)∈ℝ^+ denote the expected rate of arriving data points, for which ω is contained in 𝒩 at time t. If g(t) is a T_0-periodic function and T≫ T_0, observations P_ω,n approximate a Fourier transform E{P_ω,n}≈∫ _-T_0^0 g(τ-t) exp(-j2 π nτ/T_0) dτ up to a constant factor.


We prove the lemma in Appendix <ref>.
Lemma <ref> shows that temporal information about how frequently observers are used can be extracted from P_ω , n in terms of an inverse FT. 
To obtain the current set of active observers Ω_a, 
it suffices by selecting observers that have been used most often in the past.
Here, 
observer activity is mainly evaluated at time t-T_0, which is reasonable due to T_0-periodicity. However, due to inherent interpolation, also the very recent activity of observers is considered, which is particularly relevant for setting new observers.
In Theorem <ref>, we show that our method applies this approach for constructing Ω_a.


	
	At time t, for data streams with T_0-periodic patterns, the active observers set Ω_a, as used by Algorithm <ref>, contains observers with highest g(t).


	Equation <ref> constructs the set Ω_a by selecting observers from Ω, for which {∑_n∈[N_bins]P_ω,n} is highest. If P_ω,n yields the FT of g(t) according to Lemma <ref>, the theorem follows immediately, since {∑_n∈[N_bins]P_ω,n} performs the inverse FT at time t=0 relative to the current time.


Theorem <ref> allows us to use Ω_a for assessing outlierness of arriving data points by leveraging nearest-observer distances. Hence, in line 1, 𝒩 and 𝒩_a are constructed. Based on <cit.>, we compute an outlier score with the median of distances to the x closest observers. 
The final part of Algorithm <ref> handles model updating, which involves replacing the less “active” observer. 
Updating of P_ω, n in line 4 follows an exponential shape set by time T. We show in Theorem <ref>  that replacing observers proceeds with the same pace, which is necessary as observers otherwise would not be able to build meaningful  P_ω, n values.

	
	For data streams exhibiting T_0-periodic patterns, Algorithm <ref> on average samples k data points during a time period T as new observers.


We prove the lemma in Appendix <ref>.
Note that the factor ∑_ω∈𝒩 P_ω,0 /x/∑_ω∈Ω P_ω,0 /k occurring in line 6 of Algorithm <ref> might be omitted without invalidating Theorem <ref>. 
However, we include it to promote representativity of the observers set. 
Hence, underrepresented observers in a  neighborhood cause the observation count in this neighborhood to increase, leading to a higher sampling probability, while overrepresented observers lead to a lower sampling probability. 
Moreover, this factor is stronger during the transient starting phase, ensuring that the model soon reaches its full size, but at the same time avoiding that it is fulfilled with the first points, which in many cases would build unrepresentative models. 


During time T the model is replaced one time on average according to Theorem <ref>. Since we use a fixed-size model, an observer has to be removed when adding a new one, picking the removal candidate based on its P_ω, n. 
To avoid new observers constantly replaced due to the stronger inertia of old observers, we use an age-normalized observation count P_ω,0/H_ω for selecting the observer to remove in line 7. By updating H_ω as depicted in line 3,  H_ω denotes the maximum P_ω,0 that an observer ω might have reached over time. Thus, P_ω,0/H_ω∈ [0,1], where 1 is only scored if ω has always been in 𝒩 since it was assimilated in the model.




 §.§ Interpreting the Learned Model


Direct analysis of patterns in streams from a manual perspective is inherently complicated. Experts quickly run into difficulties regarding how to observe the data, what reference points to take, for how long, how much data to use, how to do this incrementally, etc. 
SDOoop solves all these issues in a natural and elegant way.
At any point in time, the observers set Ω allows prompt access to highly representative data points that additionally retain temporal information. The temporal shape g_ω(t) of observed data points in a neighborhood of a given observer ω can be efficiently recovered in terms of an inverse FT,

    g_ω(t) = {∑_n ∈ [N_bins] P_ω,nexp(jtn2π /T_0) } .


SDOoop is designed to be embedded in the data processing pipeline of stand-alone systems. In other words, its primary purpose is feeding subsequent analysis phases, e.g., visualization or clustering techniques to extract further knowledge. Nevertheless, Ω is commonly small enough for manual inspection, 
meaning that we can explore the set of observers along different time spans and study their periodicities, but also isolate a given instant in time to focus only on its stream characteristics.  
By analyzing observers in Ω_a, the data analyst obtains an immediate depiction of the data model to easily interpret both the ground of the outlierness scoring and how data are (or are expected to be) as a whole. 




 §.§ Costs and Parameters


The computational cost lies primarily in the comparison of incoming data points with the learned model.
Assuming that distance computation is 𝒪(D) with the number of dimensions D, 
building Ω_a (equation <ref>) implies 
time complexity 𝒪(kN_bins)+𝒪(kD). 
Holding the model in memory requires storing the observers ω and storing their observations P_ω,n, similarly resulting 𝒪(kN_bins)+𝒪(kD) as space complexity.
Therefore, per-point space and time complexity linearly depend on model size k, which is a pre-fixed parameter.  
This makes SDOoop suitable for big data with highly demanding processing.




Temporal behavior is captured by 
T, T_0 and the number of frequency bins N_bins. 
T is the time constant of the exponential windowing mechanism.  
It governs memory length, therefore equivalent to the window length of sliding window algorithms.
T_0 denotes the period of the FT base frequency. Periodicities can be captured best if T_0 is an integer multiple of expected periodicities.
For instance, in many real-world applications, it might be reasonable a T_0-value of one week, so that weekly and diurnal patterns can be detected. 
Furthermore, to ensure that the EWMA approximates a Fourier integral, T_0 should be reasonably smaller than T.
N_bins determines the maximum frequency that can be captured by the model,
hence also fixing the temporal resolution of the learned temporal shapes. 




T, T_0 and N_bins are intuitive parameters and can be easily adjusted based on domain knowledge. 
q_id, k and x are discussed extensively in <cit.> and <cit.>.
Here suffice it to mention that further experimentation confirms q_id, k and x robustness, meaning that performances are stable for a wide range of values and that most applications work properly with default configurations.
The setting of k depends on the expected variability and degree of representation, but several hundred observers is sufficient in most cases. 
x inherits from nearest-neighbor algorithms, with similar tuning strategies <cit.>. 
In our experiments, values between k ∈ [100,1000], x ∈ [3,9] and q_id∈ [0.1,0.3] have shown excellent results. 




§ EXPERIMENTAL EVALUATION
 
In this section, we discuss the experimental evaluation of SDOoop.
Based on a proof of concept, we first demonstrate its capability to detect contextual outliers. We then proceed by benchmarking OD performances on public datasets. We finally show the discovery and modeling of temporal patterns in real-life cases.





 §.§ Contextual Anomalies: Proof of Concept

For this proof of concept, we use MDCGen <cit.> to generate a synthetic data stream of five clusters that vanish and reappear at different times and periods. We add both spatial and contextual outliers into the stream. 
Fig. <ref> shows an excerpt of the generated data stream with 0.5% of contextual outliers. Hence, while normal outliers are distributed across the entire feature space, outliers occurring out of phase fall in the same spatial location as clustered data, but their time of appearance does not meet the temporal shape of clustered data.






In Fig. <ref>, we plot the area under the ROC curve (AUC) for different ratios of contextual outliers to data points in one active cluster.
We compare SDOoop with two consolidated OD methods for streaming data: 
SW-kNN (the sliding-window implementation of kNN for OD <cit.>) and RRCT <cit.>. 
All algorithms have been properly tuned to capture at least one full period. The more outliers occur out of phase, the more the performance of traditional algorithms plummets, 
whereas our method retains the highest AUC at all times.
This clearly indicates that 
SDOoop is the only algorithm capable of detecting contextual outliers. 




 §.§ OD Performance with Evaluation Datasets

To compare our method with state-of-the-art stream OD algorithms, we selected popular OD datasets of sufficient length 
and with timestamped data points.

Datasets and metrics. 
The KDD Cup'99 dataset <cit.> aims at detecting network intrusions based on a number of network and host features and, similar to previous work <cit.>,
we considered User to Root (U2R) attacks as outliers over normal traffic, resulting in 976,414 data points with an outlier proportion of 0.4%.
Additionally, we selected the recent SWAN-SF <cit.> dataset, which collects data about solar flares, and used preprocessing scripts provided by Ahmadzadeh and Aydin <cit.>. For SWAN-SF, we assigned a normal label to the majority class and an outlier label to the remaining classes, resulting in 331,185 data points with an outlier portion of 17.2%. In both experiments, we randomly sampled 50% of the data stream for randomized hyperparameter search and the other half for evaluation. For an overview of the ranges of hyperparameters, we refer to the code repository of this paper. Metrics for evaluation are Adjusted Average Precision (AAP), 
Adjusted Precision at n (AP@n), 
and AUC <cit.>.

Algorithms and experimental setups. 
We used the dSalmon framework <cit.>, which provides efficient versions of several stream OD algorithms. 
Since ensembles commonly exhibit superior accuracy, we used an ensemble of nine for SDOoop, yet noticing almost no difference compared to a single SDOoop detector. 

OD performances. 
Experiment results in Table <ref> show how our method matches and even outperforms state-of-the-art algorithms for streaming OD. The strongest competitor is RS-Hash <cit.>. 
In the SWAN-SF case, SDOoop ranks among the best performers, while, in the KDD Cup'99 dataset, it clearly stands out, particularly in AAP and AP@n. 
The higher AP@n also indicates that our method finds several true outliers that pass unperceived for the competitors.






Disclosing insights about the data. 
Obtained results seem consistent with data contexts. Considering how
outliers have been defined in the SWAN-SF dataset, we do not expect
that outliers break possible temporal periodicities in samples from solar
flares. 
On the other hand, the KDD Cup’99 dataset describes events in a
computer network, which are expected to exhibit strong
temporal patterns due to human activity. Patterns may be broken by attack traffic, 
leading to contextual outliers, behaviors that can be spotted by our method. 
Here, the superior detection of
SDOoop not only indicates that the data
show temporal patterns, but also that some U2R
attacks are indeed contextual outliers.





 §.§ Temporal Patterns in Machine-to-Machine Communication
 

Application context. 
We study network traffic captured in a critical infrastructure,
in particular, of an energy supply company that connects charging stations for electric vehicles. The network communication satisfies management, accounting and maintenance aspects[While we embrace reproducible research, issues related to confidentiality, security and privacy prevent us from making these data publicly available.].
Network communication for these purposes usually adopts the OCPP protocol. 
Due to the large portion of machine-to-machine communications, we expected to discover distinct periodic patterns.

Preprocessing and parameters. 
We preprocessed data with the feature vector described in <cit.>, resulting in 13 million flows during a 1 month period. We parameterized the algorithm using T=1 week, 2000 frequency bins and T_0=2000 minutes, obtaining a minimum period of 1 minute. 
We used 400 observers. 

Capturing periodical patterns/clusters. 
Fig. <ref> shows on the left side examples for the frequency spectrum (magnitude) learned by observers. Hence, different clusters show diverse temporal patterns. While observer 1 shows no or just weak periodicities, observer 2 shows a clear 5 minute periodicity and observers 3 and 4 show a 10 minute periodicity. From the learned FT, temporal shapes can be constructed in terms of an inverse FT as depicted in equation <ref>.
Fig. <ref> also shows the reconstructed temporal shape plotted over a 1 hour and 24 hour period. Hence, beneath the periodicities already found when inspecting the FT directly, the temporal shape for observers 3 and 4 additionally shows periodicities of a longer period of approximately 2.5 hours.



Interpreting clusters in the application. 
The manual examination of network flows represented by observers confirmed the soundness of discovered temporal patterns. For example, observer 3 corresponds to ICMP pings that happen regularly to ensure that network devices are alive. Observer 4 identifies DNS requests that charging stations perform to resolve the name of the OCPP server to its IP address and transmit meter readings. For observer 4, the periodicity emerges from DNS caching, so that every second request for transmitting meter readings can be performed without having to perform a DNS lookup.

Observer 1 corresponds to protocol heartbeat messages. The fact that it does not show a clear periodicity might be due to the requesting devices not being time-synchronized or by deviating device configurations. Alternatively, heartbeat messages might take place with a very high frequency, so that no periodicities can be observed at the analyzed time scale.

Identifying outliers in the application. 
Fig. <ref> shows outlier scores of points in time order. The manual inspection of flows with highest outlierness (in the center of Fig. <ref>) revealed that they are firmware update processes. Since updates took place only during two days in the monitored time span, then high outlier scores are consistent (yet they are not contextual anomalies).






Learning stability. 
Finally, we investigated whether our results meet the expected algorithm behavior with respect to the sampling of new observers. Fig. <ref> shows how many data points have been sampled as new observers during the first two weeks. With T=1 week and k=400 observers, 400/7≈ 57 observers should be sampled each day according to equation <ref>. This theoretical conjecture shows good agreement with the empirical results.
Fig. <ref> also shows that the model is not instantly filled with observers in the first hours, but it is instead built up during the first days. Since data seen within the first couple of hours might not be representative for the remaining data, this transient behavior boosts the swift discovery of a representative model while achieving a fast model buildup  with a high sampling rate at the beginning.





 §.§ Discovery of Temporal Patterns: Darkspace Data


Application context and parameterization. 
We additionally tested our method on the publicly available CAIDA “Patch Tuesday” darkspace dataset <cit.>. During preprocessing, we aggregated features  by source IP address using the AGM feature vector <cit.>, specifically proposed for analyzing darkspace data. We applied our algorithm with T_0=1 week and T=10 weeks and 100 observers and 100 frequency bins, resulting in a minimum period length of about 100 minutes.


Capturing and identifying periodical patterns/clusters. 
Fig. <ref> shows the magnitude of the Fourier coefficients of the three strongest observers. Peaks in Fig. <ref> occur at the 7th and 14th frequency bins, which are diurnal and semi-diurnal periodicities. 
This coincides with previous studies of the darkspace <cit.> 
that, among others, identified Conficker.C worm attacks or BitTorrent misconfigurations for diurnal patterns, and horizontal scan, vertical scan and probing activities on the UDP protocol for semi-diurnal patterns.











§ RELATED WORK
 

The problem addressed in this paper is covered in diverse fields, yet differing in some core aspects. 
In this section, we provide an overview of related concepts and precedents to place SDOoop in the landscape of existing work.

Time Series Analysis and Contextual Anomalies. 
A time series is a temporal sequence of observations of specific measurement variables. Time series have been studied in multiple domains, e.g., 
finance and econometrics <cit.>
weather forecasting <cit.>, 
electric load forecasting <cit.>. 
Traditionally, time series have been analyzed with mathematical tools  
<cit.>, 
however, in multivariate time series complexity increases dramatically and experts usually resort to nonlinear machine learning, e.g., <cit.>
Multivariate time series and streaming data are frequently considered synonyms, showing small differences open to discussion <cit.>.


Contextual anomalies have been tackled mainly in the time series analysis domain <cit.>, but here experts also emphasize the low attention given to contextual anomalies in spite of its relevance for cybersecurity, healthcare sensory and fraud detection <cit.>. 
Latest research tends to expand the focus and, besides point anomalies, face anomalous sequences within the whole time series context, giving rise to 
fast model-based detectors <cit.>. However, when considered, contextual anomalies are confronted mainly from a univariate time series perspective. An exception is the recent work by Pasini et al. <cit.>, which copes with low-dimensional multivariate time series and proposes a global contextual variance score by weighting feature-wise contextual variances based on Mahalanobis distances. 
Note that such approach assumes feature independence though.


OD in Streaming Data
The trend in OD of recent years is to build models to process streaming data with constant memory complexity. In addition to distance-based methods like SDOstream <cit.>, OD in streams is grounded on tree-based methods <cit.>, half-space chains <cit.>,
histograms <cit.>, randomized hashing <cit.>, 
or simply based on nearest neighbors in a sliding window <cit.>. 
A thorough comparison of these methods can be consulted in <cit.>.

When compared to SDOoop, beyond the core approach for calculating point outlierness, the main difference is that
earlier algorithms establish a temporally evolving model (or a set of reference data points) that is deemed stationary at time scales smaller than a pre-fixed time parameter.
Hence, contextual outliers, i.e. data points that occur at an atypical time (out-of-phase), are wrongly classified as normal inliers. 
Another important property of OD methods is interpretability of returned outlier scores.
In fact, many modern techniques like forest-based methods require space transformations that inevitably sacrifice interpretability. 
In SDOoop, outlier scores can be directly interpreted as distance-to-observers, i.e., distance-to-normality. The model is small enough for manual inspection, allowing the analyst to draw conclusions about the data mass based on main model patterns. On the other hand, obtained models are also suitable for stand-alone systems or frameworks where knowledge must be integrated with decision-making modules or other types of knowledge. 

Table <ref> shows a summarized comparison of recent algorithms for evolving stream OD with regard to key properties. SW-kNN and SW-LOF denote sliding-window implementations of the popular kNN <cit.> and LOF <cit.> algorithms.


R[2]
	>angle=#1,lap=-(#2)
	l
	<




Periodic Pattern Mining. 
The detection of periodicities in 
sequences has also been investigated in the context of periodic pattern mining <cit.>.
Periodic pattern mining can be applied to spatiotemporal data <cit.> to detect periodicities in the movement of objects. 
In contrast, SDOoop is able to detect periodicities of arbitrary clusters  even if the corresponding data points are mixed up with data points from other clusters with different temporal patterns or no patterns at all.
To the best of our knowledge, this problem has not been explored before.





§ CONCLUSION
 
Big data frequently arrives in data streams and requires online processing and analysis. We proposed SDOoop, a method for knowledge discovery in data streams that is able to capture coexisting periodicities regardless of data geometries.
Our method performs a single pass through the data and builds a fixed-size model consisting of representative point locations along with their temporal behavior in Fourier space. 
We showed equal or superior performances compared to state-of-the-art algorithms when testing OD in established evaluation datasets. Moreover, we showed that our method can be an important tool for understanding and visualizing the spatiotemporal behavior of steadily arriving real-world data,
particularly in network security and critical infrastructures communications.


IEEEtran 
      




§ PROOF OF LEMMA <REF>
 
Let i_o ∈ℕ denote the index of a data point, for which ω is contained in 𝒩 and i_c is the index of the currently processed data point, i.e., i_o < i_c. Then, the contribution of i_o to P_ω,n according to line 4 of Algorithm <ref> has been multiplied by Π _i=i_o+1^i_c(exp(-T^-1+jn2 π /T_0))^t_i-t_i-1 = (exp(-T^-1+jn2 π /T_0))^t_i_c-t_i_o. Summing over all points that have arrived in ω's neighborhood, we can write 

    E{P_ω,n} = ∫ _-∞^t g(τ)  (exp(-T^-1+jn2 π /T_0))^t-τ dτ.

Splitting the integral into intervals of length T_0, we obtain

    E{P_ω,n} =  
     ∑_l=0^∞∫ _t-T_0^t g(τ-lT_0)  (exp(-T^-1+jn2 π /T_0))^t-τ-lT_0 dτ
        = ( ∑_l=0^∞exp(-T^-1lT_0) ) ∫ _t-T_0^t  g(τ)  (exp(-T^-1+jn2 π /T_0))^t-τ dτ

due to T_0-periodicity of g(t) and exp(jn2π)=1. Abbreviating the constant factor and substituting τ^'=τ-t, we obtain

    E{P_ω,n} = 
     c ∫ _-T_0^0 g(τ^'-t)  (exp(-T^-1+jn2 π /T_0))^-τ^' dτ^'
       T ≫ T_0≈ 
    c ∫ _-T_0^0 g(τ^'-t)  exp(-jn2 πτ^' /T_0)) dτ^' .




§ PROOF OF THEOREM <REF>
 
Taking line 6 in Algorithm <ref> as starting point, 
the probability of selecting a newly seen point as observer is
min(1,k^2/Tx∑_ω∈𝒩 P_ω,0/∑_ω∈Ω P_ω,0t_i-t_i_LAO/i-i_LAO). 
Since we target specifically data streams with high rates of arriving data points, we can safely assume this probability to be small.
Hence, {1 <k^2/Tx∑_ω∈𝒩 P_ω,0/∑_ω∈Ω P_ω,0t_i-t_i_LAO/i-i_LAO} is negligible and we can write for the average probability of sampling a new point as observer
P_s ≈ E {k^2/Tx∑_ω∈𝒩 P_ω,0/∑_ω∈Ω P_ω,0t_i-t_i_LAO/i-i_LAO}. Under the same assumption, we observe that the term t_i-t_i_LAO/i-i_LAO depends on the current time, but, since points belonging to different neighborhoods arrive in an interleaved manner, does not depend on a point's neighborhood. Since ∑_ω∈𝒩 P_ω,0/∑_ω∈Ω P_ω,0 does not depend on time, we can split the term to P_s ≈ E {k^2/Tx∑_ω∈𝒩 P_ω,0/∑_ω∈Ω P_ω,0} E{t_i-t_i_LAO/i-i_LAO} due to stochastic independence of both terms.
∑_ω∈𝒩 P_ω,0 /x expresses the average observation count in the current neighborhood. The algorithm implements several mechanisms to make the observer density agree with the time-averaged point density, rendering the time-averaged local average observation count E{∑_ω∈𝒩 P_ω,0 /x} equal to the total average observation count of all observers ∑_ω∈Ω P_ω,0 /k, hence P_s ≈k/TE{t_i-t_i_LAO/i-i_LAO}=k/TIAT, where the average inter-arrival time of two data points is termed IAT.
During a time period of T, T/IAT data points arrive, yielding an average number of sampled points of P_sT/IAT=k.   


