A review on outlier/anomaly detection in time series data <s> Discord detection Dissimilarity-based <s> The problem of similarity search in large time series databases has attracted much attention recently. It is a non-trivial problem because of the inherent high dimensionality of the data. The most promising solutions involve first performing dimensionality reduction on the data, and then indexing the reduced data with a spatial access method. Three major dimensionality reduction techniques have been proposed: Singular Value Decomposition (SVD), the Discrete Fourier transform (DFT), and more recently the Discrete Wavelet Transform (DWT). In this work we introduce a new dimensionality reduction technique which we call Piecewise Aggregate Approximation (PAA). We theoretically and empirically compare it to the other techniques and demonstrate its superiority. In addition to being competitive with or faster than the other methods, our approach has numerous other advantages. It is simple to understand and to implement, it allows more flexible distance measures, including weighted Euclidean queries, and the index can be built in linear time. <s> BIB001 </s> A review on outlier/anomaly detection in time series data <s> Discord detection Dissimilarity-based <s> In this paper, we focus on mining surprising periodic patterns in a sequence of events. In many applications, e.g., computational biology, an infrequent pattern is still considered very significant if its actual occurrence frequency exceeds the prior expectation by a large margin. The traditional metric, such as support, is not necessarily the ideal model to measure this kind of surprising patterns because it treats all patterns equally in the sense that every occurrence carries the same weight towards the assessment of the significance of a pattern regardless of the probability of occurrence. A more suitable measurement, information, is introduced to naturally value the degree of surprise of each occurrence of a pattern as a continuous and monotonically decreasing function of its probability of occurrence. This would allow patterns with vastly different occurrence probabilities to be handled seamlessly. As the accumulated degree of surprise of all repetitions of a pattern, the concept of information gain is proposed to measure the overall degree of surprise of the pattern within a data sequence. The bounded information gain property is identified to tackle the predicament caused by the violation of the downward closure property by the information gain measure and in turn provides an efficient solution to this problem. Empirical tests demonstrate the efficiency and the usefulness of the proposed model. <s> BIB002 </s> A review on outlier/anomaly detection in time series data <s> Discord detection Dissimilarity-based <s> The problem of finding a specified pattern in a time series database (i.e. query by content) has received much attention and is now a relatively mature field. In contrast, the important problem of enumerating all surprising or interesting patterns has received far less attention. This problem requires a meaningful definition of "surprise", and an efficient search technique. All previous attempts at finding surprising patterns in time series use a very limited notion of surprise, and/or do not scale to massive datasets. To overcome these limitations we introduce a novel technique that defines a pattern surprising if the frequency of its occurrence differs substantially from that expected by chance, given some previously seen data. <s> BIB003 </s> A review on outlier/anomaly detection in time series data <s> Discord detection Dissimilarity-based <s> In this paper, we focus on mining surprising periodic patterns in a sequence of events. In many applications, e.g., computational biology, an infrequent pattern is still considered very significant if its actual occurrence frequency exceeds the prior expectation by a large margin. The traditional metric, such as support, is not necessarily the ideal model to measure this kind of surprising patterns because it treats all patterns equally in the sense that every occurrence carries the same weight towards the assessment of the significance of a pattern regardless of the probability of occurrence. A more suitable measurement, information, is introduced to naturally value the degree of surprise of each occurrence of a pattern as a continuous and monotonically decreasing function of its probability of occurrence. This would allow patterns with vastly different occurrence probabilities to be handled seamlessly. As the accumulated degree of surprise of all repetitions of a pattern, the concept of information gain is proposed to measure the overall degree of surprise of the pattern within a data sequence. The bounded information gain property is identified to tackle the predicament caused by the violation of the downward closure property by the information gain measure and in turn provides an efficient solution to this problem. Furthermore, the user has a choice between specifying a minimum information gain threshold and choosing the number of surprising patterns wanted. Empirical tests demonstrate the efficiency and the usefulness of the proposed model. <s> BIB004 </s> A review on outlier/anomaly detection in time series data <s> Discord detection Dissimilarity-based <s> Recent advancements in sensor technology have made it possible to collect enormous amounts of data in real time. However, because of the sheer volume of data most of it will never be inspected by an algorithm, much less a human being. One way to mitigate this problem is to perform some type of anomaly (novelty /interestingness/surprisingness) detection and flag unusual patterns for further inspection by humans or more CPU intensive algorithms. Most current solutions are “custom made” for particular domains, such as ECG monitoring, valve pressure monitoring, etc. This customization requires extensive effort by domain expert. Furthermore, hand-crafted systems tend to be very brittle to concept drift. In this demonstration, we will show an online anomaly detection system that does not need to be customized for individual domains, yet performs with exceptionally high precision/recall. The system is based on the recently introduced idea of time series bitmaps. To demonstrate the universality of our system, we will allow testing on independently annotated datasets from domains as diverse as ECGs, Space Shuttle telemetry monitoring, video surveillance, and respiratory data. In addition, we invite attendees to test our system with any dataset available on the web. <s> BIB005 </s> A review on outlier/anomaly detection in time series data <s> Discord detection Dissimilarity-based <s> The problem of finding anomaly has received much attention recently. However, most of the anomaly detection algorithms depend on an explicit definition of anomaly, which may be impossible to elicit from a domain expert. Using discords as anomaly detectors is useful since less parameter setting is required. Keogh et al proposed an efficient method for solving this problem. However, their algorithm requires users to choose the word size for the compression of subsequences. In this paper, we propose an algorithm which can dynamically determine the word size for compression. Our method is based on some properties of the Haar wavelet transformation. Our experiments show that this method is highly effective. <s> BIB006 </s> A review on outlier/anomaly detection in time series data <s> Discord detection Dissimilarity-based <s> The discovery of objects with exceptional behavior is an important challenge from a knowledge discovery standpoint and has attracted much attention recently. In this paper, we present a stochastic graph-based algorithm, called OutRank, for detecting outlying objects. In our method, a matrix is constructed using the similarity between objects and used as the adjacency matrix of the graph representation. The heart of this approach is the Markov model that is built upon this graph, which assigns an outlier score to each object. Using this framework, we show that our algorithm is more powerful than the existing outlier detection schemes and can effectively address the inherent problems of such schemes. Empirical studies conducted on both real and synthetic data sets show that significant improvements in detection rate and a lower false alarm rate are achieved using our proposed framework. <s> BIB007 </s> A review on outlier/anomaly detection in time series data <s> Discord detection Dissimilarity-based <s> Finding discords in time series database is an important problem in a great variety of applications, such as space shuttle telemetry, mechanical industry, biomedicine, and financial data analysis. However, most previous methods for this problem suffer from too many parameter settings which are difficult for users. The best known approach to our knowledge that has comparatively fewer parameters still requires users to choose a word size for the compression of subsequences. In this paper, we propose a Haar wavelet and augmented trie based algorithm to mine the top-K discords from a time series database, which can dynamically determine the word size for compression. Due to the characteristics of Haar wavelet transform, our algorithm has greater pruning power than previous approaches. Through experiments with some annotated datasets, the effectiveness and efficiency of our algorithm are both attested. <s> BIB008 </s> A review on outlier/anomaly detection in time series data <s> Discord detection Dissimilarity-based <s> Time discord detection is an important problem in a great variety of applications. In this paper, we consider the problem of discord detection for time series stream, where time discords are detected from local segments of flowing time series stream. The existing detections, which aim to detect the global discords from time series database, fail to detect such local discords. Two online detection algorithms are presented for our problem. The first algorithm extends the existing algorithm HOT SAX to detect such time discords. However, this algorithm is not efficient enough since it needs to search the entire time subsequences of local segment. Then, in the second algorithm, we limit the search space to further enhance the detection efficiency. The proposed algorithms are experimentally evaluated using real and synthesized datasets. <s> BIB009 </s> A review on outlier/anomaly detection in time series data <s> Discord detection Dissimilarity-based <s> Despite a dramatic growth of power consumption in households, less attention has been paid to monitoring, analyzing and predicting energy usage. In this paper, we propose a framework to mine raw energy data by transforming time series energy data into a symbol sequence, and then extend a suffix tree data structure as an efficient representation to analyze global structural patterns. Then, we use a clustering algorithm to detect energy pattern outliers which are far from their cluster centroids. To validate our approach, we use real power data collected from a smart apartment testbed during two months. <s> BIB010 </s> A review on outlier/anomaly detection in time series data <s> Discord detection Dissimilarity-based <s> Periodic pattern mining or periodicity detection has a number of applications, such as prediction, forecasting, detection of unusual activities, etc. The problem is not trivial because the data to be analyzed are mostly noisy and different periodicity types (namely symbol, sequence, and segment) are to be investigated. Accordingly, we argue that there is a need for a comprehensive approach capable of analyzing the whole time series or in a subsection of it to effectively handle different types of noise (to a certain degree) and at the same time is able to detect different types of periodic patterns; combining these under one umbrella is by itself a challenge. In this paper, we present an algorithm which can detect symbol, sequence (partial), and segment (full cycle) periodicity in time series. The algorithm uses suffix tree as the underlying data structure; this allows us to design the algorithm such that its worstcase complexity is O(k.n2), where k is the maximum length of periodic pattern and n is the length of the analyzed portion (whole or subsection) of the time series. The algorithm is noise resilient; it has been successfully demonstrated to work with replacement, insertion, deletion, or a mixture of these types of noise. We have tested the proposed algorithm on both synthetic and real data from different domains, including protein sequences. The conducted comparative study demonstrate the applicability and effectiveness of the proposed algorithm; it is generally more time-efficient and noise-resilient than existing algorithms. <s> BIB011 </s> A review on outlier/anomaly detection in time series data <s> Discord detection Dissimilarity-based <s> Society is becoming increasingly aware of the impact that our lifestyle choices make on energy usage and the environment. As a result, research attention is being directed toward green technology, environmentally-friendly building designs, and smart grids. This paper looks at the user side of sustainability. In particular, it looks at energy consumption in everyday home environments to examine the relationship between behavioral patterns and energy consumption. It first demonstrates how data mining techniques may be used to find patterns and anomalies in smart home-based energy data. Next, it describes a method to correlate home-based activities with electricity usage. Finally, it describes how this information could inform users about their personal energy consumption and to support activities in a more energy-efficient manner. These approaches are validated by using real energy data collected in a set of smart home testbeds. <s> BIB012 </s> A review on outlier/anomaly detection in time series data <s> Discord detection Dissimilarity-based <s> Detecting incident anomalies within temporal data - time series becomes useful in a variety of applications. In this paper, anomalies in time series are divided into two categories, namely amplitude anomalies and shape anomalies. A unified framework supporting the detection of both types of anomalies is introduced. A fuzzy clustering is employed to reveal the available structure within time series and a reconstruction criterion is used to assign an anomaly score to each subsequence. In the case of detecting anomalies in amplitude, the original representation of time series is used, while for detecting anomalies in shape an autocorrelation representation of time series to capture shape information is employed. Experimental studies concerning two real-world data sets are reported. <s> BIB013 </s> A review on outlier/anomaly detection in time series data <s> Discord detection Dissimilarity-based <s> Data stream mining is an active research area that has recently emerged to discover knowledge from large amounts of continuously generated data. In this context, several data stream clustering algorithms have been proposed to perform unsupervised learning. Nevertheless, data stream clustering imposes several challenges to be addressed, such as dealing with nonstationary, unbounded data that arrive in an online fashion. The intrinsic nature of stream data requires the development of algorithms capable of performing fast and incremental processing of data objects, suitably addressing time and memory limitations. In this article, we present a survey of data stream clustering algorithms, providing a thorough discussion of the main design components of state-of-the-art algorithms. In addition, this work addresses the temporal aspects involved in data stream clustering, and presents an overview of the usually employed experimental methodologies. A number of references are provided that describe applications of data stream clustering in different domains, such as network intrusion detection, sensor networks, and stock market analysis. Information regarding software packages and data repositories are also available for helping researchers and practitioners. Finally, some important issues and open questions that can be subject of future research are discussed. <s> BIB014 </s> A review on outlier/anomaly detection in time series data <s> Discord detection Dissimilarity-based <s> Anomaly detection in time series has been studied extensively by the scientific community utilizing a wide range of applications. One specific technique that obtains very good results is “HOT SAX”, because it only requires a parameter the length of the subsequence, and it does not need a training model for detecting anomalies. However, its disadvantage is that it requires the use of a normalized Euclidean distance, which in turn requires setting a parameter e to avoid detecting meaningless patterns (noise in the signal). Setting an appropriate e requires an analysis of the domain of the values from the time series, which implies normalizing all subsequences before performing the detection. We propose an approach for anomaly detection based on bounding boxes, which does not require normalizing the subsequences, thus it does not need to set e. Thereby, the proposed technique can be used directly for online detection, without any a priori knowledge and using the non-normalized Euclidean distance. Moreover, we show that our algorithm computes less CPU runtime in finding the anomaly than HOT SAX in normalized scenarios. <s> BIB015 </s> A review on outlier/anomaly detection in time series data <s> Discord detection Dissimilarity-based <s> Periodic pattern detection in time-ordered sequences is an important data mining task, which discovers in the time series all patterns that exhibit temporal regularities. Periodic pattern mining has a large number of applications in real life; it helps understanding the regular trend of the data along time, and enables the forecast and prediction of future events. An interesting related and vital problem that has not received enough attention is to discover outlier periodic patterns in a time series. Outlier patterns are defined as those which are different from the rest of the patterns; outliers are not noise. While noise does not belong to the data and it is mostly eliminated by preprocessing, outliers are actual instances in the data but have exceptional characteristics compared with the majority of the other instances. Outliers are unusual patterns that rarely occur, and, thus, have lesser support (frequency of appearance) in the data. Outlier patterns may hint toward discrepancy in the data such as fraudulent transactions, network intrusion, change in customer behavior, recession in the economy, epidemic and disease biomarkers, severe weather conditions like tornados, etc. We argue that detecting the periodicity of outlier patterns might be more important in many sequences than the periodicity of regular, more frequent patterns. In this paper, we present a robust and time efficient suffix tree-based algorithm capable of detecting the periodicity of outlier patterns in a time series by giving more significance to less frequent yet periodic patterns. Several experiments have been conducted using both real and synthetic data; all aspects of the proposed approach are compared with the existing algorithm InfoMiner; the reported results demonstrate the effectiveness and applicability of the proposed approach. <s> BIB016 </s> A review on outlier/anomaly detection in time series data <s> Discord detection Dissimilarity-based <s> We investigate algorithms for efficiently detecting anomalies in real-valued one-dimensional time series. Past work has shown that a simple brute force algorithm that uses as an anomaly score the Euclidean distance between nearest neighbors of subsequences from a testing time series and a training time series is one of the most effective anomaly detectors. We investigate a very efficient implementation of this method and show that it is still too slow for most real world applications. Next, we present a new method based on summarizing the training time series with a small set of exemplars. The exemplars we use are feature vectors that capture both the high frequency and low frequency information in sets of similar subsequences of the time series. We show that this exemplar-based method is both much faster than the efficient brute force method as well as a prediction-based method and also handles a wider range of anomalies. We compare our algorithm across a large variety of publicly available time series and encourage others to do the same. Our exemplar-based algorithm is able to process time series in minutes that would take other methods days to process. <s> BIB017 </s> A review on outlier/anomaly detection in time series data <s> Discord detection Dissimilarity-based <s> Because of user movements and activities, heartbeats recorded from wearable devices typically feature a large degree of variability in their morphology. Learning problems, which in ECG monitoring often involve learning a user-specific model to describe the heartbeat morphology, become more challenging. <s> BIB018 </s> A review on outlier/anomaly detection in time series data <s> Discord detection Dissimilarity-based <s> Abstract In the area of time series representation, the Piecewise Aggregate Approximation (PAA) method has established itself quite visibly resulting in a number of useful results. However, the PAA technique usually leads to some losses of information. In order to overcome this issue, we propose a representation approach called Piecewise Aggregate Pattern Representations (PAPR). In the PAPR method, the range of values assumed in the temporal segment is divided into several regions with equal probability. In the sequel, some statistics of the regions, such as the number, the mean and the variance of points falling within each region, are determined. A matrix (pattern) containing all these statistical characteristics is constructed to represent the corresponding segment of the time series. We incorporate the PAPR method into anomaly detection by computing the similarity of patterns and using a Random Walk (RW) model, as a classifier, to determine the similarity values. Finally, the connectivity and anomaly ranks of patterns are obtained with the use of the RW model. The overall anomaly detection approach is referred to as PAPR-RW. Experimental studies are reported for synthetic data sets and two publicly available data sets: electrocardiograms (ECGs) data and the video surveillance data. Compared with the PAA-based method, the PAPR-RW approach exhibits a higher level of robustness and detects anomalies more accurately. <s> BIB019 </s> A review on outlier/anomaly detection in time series data <s> Discord detection Dissimilarity-based <s> In this paper, we propose an improved variant of HOT SAX algorithm, called HS-Squeezer, for efficient discord detection in static time series. HS-Squeezer employs clustering rather than augmented trie to arrange two ordering heuristics in HOT SAX. Furthermore, we introduce HS-Squeezer-Stream, the application of HS-Squeezer in the framework for detecting local discords in streaming time series. The experimental results reveal that HS-Squeezer can detect the same quality discords as those detected by HOT SAX but with much shorter run time. Furthermore, HS-Squeezer-Stream demonstrates a fast response in handling time series streams with quality local discords detected. <s> BIB020 </s> A review on outlier/anomaly detection in time series data <s> Discord detection Dissimilarity-based <s> The problem of anomaly detection in time series has received a lot of attention in the past two decades. However, existing techniques cannot locate where the anomalies are within anomalous time series, or they require users to provide the length of potential anomalies. To address these limitations, we propose a self-learning online anomaly detection algorithm that automatically identifies anomalous time series, as well as the exact locations where the anomalies occur in the detected time series. In addition, for multivariate time series, it is difficult to detect anomalies due to the following challenges. First, anomalies may occur in only a subset of dimensions (variables). Second, the locations and lengths of anomalous subsequences may be different in different dimensions. Third, some anomalies may look normal in each individual dimension but different with combinations of dimensions. To mitigate these problems, we introduce a multivariate anomaly detection algorithm which detects anomalies and identifies the dimensions and locations of the anomalous subsequences. We evaluate our approaches on several real-world datasets, including two CPU manufacturing data from Intel. We demonstrate that our approach can successfully detect the correct anomalies without requiring any prior knowledge about the data. <s> BIB021 </s> A review on outlier/anomaly detection in time series data <s> Discord detection Dissimilarity-based <s> Abstract Many successful algorithms for analyzing ECG signals leverage data-driven models that are learned for each specific user. Unfortunately, a few algorithmic challenges are still to be addressed before employing these models in wearable devices, thus enabling online and long-term monitoring. In particular, since the heartbeats morphology changes with the heart rate, models learned in resting conditions need to be adapted to analyze ECG signals recorded during everyday activities. We propose an online ECG monitoring solution where normal heartbeats of each specific user are modeled by dictionaries yielding sparse representations, and heartbeats that do not conform to this model are detected as anomalous. We track heart rate variations by adapting the user-specific dictionary with a set of user-independent, linear, transformations. Our experiments demonstrate that these transformations can be successfully learned from a public dataset of ECG signals and that, thanks to an optimized anomaly-detection algorithm, our solution enables online and long-term ECG monitoring. <s> BIB022 </s> A review on outlier/anomaly detection in time series data <s> Discord detection Dissimilarity-based <s> Traditional distance and density-based anomaly detection techniques are unable to detect periodic and seasonality related point anomalies which occur commonly in streaming data, leaving a big gap in time series anomaly detection in the current era of the IoT. To address this problem, we present a novel deep learning-based anomaly detection approach (DeepAnT) for time series data, which is equally applicable to the non-streaming cases. DeepAnT is capable of detecting a wide range of anomalies, i.e., point anomalies, contextual anomalies, and discords in time series data. In contrast to the anomaly detection methods where anomalies are learned, DeepAnT uses unlabeled data to capture and learn the data distribution that is used to forecast the normal behavior of a time series. DeepAnT consists of two modules: time series predictor and anomaly detector. The time series predictor module uses deep convolutional neural network (CNN) to predict the next time stamp on the defined horizon. This module takes a window of time series (used as a context) and attempts to predict the next time stamp. The predicted value is then passed to the anomaly detector module, which is responsible for tagging the corresponding time stamp as normal or abnormal. DeepAnT can be trained even without removing the anomalies from the given data set. Generally, in deep learning-based approaches, a lot of data are required to train a model. Whereas in DeepAnT, a model can be trained on relatively small data set while achieving good generalization capabilities due to the effective parameter sharing of the CNN. As the anomaly detection in DeepAnT is unsupervised, it does not rely on anomaly labels at the time of model generation. Therefore, this approach can be directly applied to real-life scenarios where it is practically impossible to label a big stream of data coming from heterogeneous sensors comprising of both normal as well as anomalous points. We have performed a detailed evaluation of 15 algorithms on 10 anomaly detection benchmarks, which contain a total of 433 real and synthetic time series. Experiments show that DeepAnT outperforms the state-of-the-art anomaly detection methods in most of the cases, while performing on par with others. <s> BIB023
Frequency-based Prediction model-based Information theory Fig. 15 . Types of methods for detecting subsequence outliers in univariate time series. The first and most straightforward idea consists of detecting the most unusual subsequence in a time series (denominated time series discord) , by comparing each subsequence with the others; that is, D is a discord of time series X if where A is the set of all subsequences of X extracted by a sliding window, D ′ is a subsequence in A that does not overlap with D (non-overlapping subsequences), S ′ in A does not overlap with S (non-overlapping subsequences), and d is the Euclidean distance between two subsequences of equal length. Typically, discord discovery techniques require the user to specify the length of the discord. Two examples are given in Fig. 16 , in which the most unusual subsequences (O1 and O2) are shown. The simplest way of finding discords is using brute-force, which requires a quadratic pairwise comparison. Even so, the process can be sped-up by reordering the search using heuristics and pruning off some fruitless calculations with the HOT-SAX algorithm , which is based on the SAX discrete representation. Many variants of the HOT-SAX algorithm aim to reduce its time complexity by enhancing both the heuristic reordering and the pruning for discord detection, which may be based on the Haar wavelet transformation and augmented trie BIB008 BIB006 ], on bit representation clustering  ], on bounding boxes BIB015 , on clustering categorical data BIB020 , and on the iSAX representation [Buu and Anh 2011]. Additionally, BIB009 not only is the HOT-SAX algorithm applied in a streaming context using a sliding window but an incremental algorithm has also been suggested to simplify this computation. The method proposed by BIB020 is also based on this incremental algorithm. Those discord discovery techniques require the user to prespecify the length of the discord, which in many cases may not be known. Consequently,  present two approaches to detect variable-length discords applying grammar-induction procedures in the time series discretized with SAX. Since symbols that are rarely used in grammar rules are non-repetitive and thus most likely to be unusual, subsequence outliers correspond to rare grammar rules, which naturally vary in length. Given that the lengths of the subsequences vary, the Euclidean distance between them is calculated by shrinking the longest subsequence with the Piecewise Aggregate Approximation (PAA) BIB001 ] to obtain subsequences of the same length. The abovementioned discord detection techniques are limited to finding the most unusual subsequence within a time series. However, since they do not have a reference of normality or a threshold, they cannot specify whether it is indeed an outlier or not. Therefore, this decision must be made by the user. Conversely, the other categories in Fig. 15 consider a criterium of normality and contain specific rules to decide whether or not the identified subsequences are outliers. For example, dissimilarity-based methods are based on the direct comparison of subsequences or their representations, using a reference of normality. In this category, the reference of normality, as well as the representations used to describe the subsequences, vary widely, in contrast to the dissimilarity-based techniques analyzed in Section 3.2.2. Then, for a predefined threshold τ , subsequence outliers are those that are dissimilar to normal subsequences; that is, where S is the subsequence being analyzed or its representation,Ŝ is the expected value of S obtained based on the reference of normality, and s measures the dissimilarity between two subsequences. Typically, S is of fixed-length, non-periodic, and extracted via a sliding window. Some dissimilarity-based approaches are described below ordered based on the considered reference of normality (see Fig. 17 ), which will be used to obtain the expected valueŜ. Same time series. The most straightforward approach is to consider the same time series object of the analysis as the reference of normality (Fig. 17a ). Clustering techniques commonly use this reference of normality to create clusters by Manuscript submitted to ACM grouping subsequences that are similar to each other and by separating dissimilar subsequences into different clusters (see Fig. 18 ). Then,Ŝ in equation (7) can be defined by the centroid or center of the cluster to which S belongs. For example, BIB010 and BIB012 cluster discretized subsequences of the same length and flag subsequences that are far from the nearest centroid (Ŝ) as outliers. In this case, the distance used is the Euclidean norm of three specific distances between the discretized subsequences. Alternatively, BIB013 employ Fuzzy C-Means (FCM) clustering on the raw data, allowing each subsequence to belong to more than one cluster. In particular, the authors use the Euclidean distance in (7) . Note that these two clustering approaches are not applied to streaming time series in the original papers but could be extended using stream clustering algorithms BIB014 ]. As opposed to the clustering methods that detect fixed-length subsequence outliers, BIB021 propose dynamic clustering to identify variable-length outliers in a streaming context. The method works directly with raw data and assumes that the observations arrive in fixed-length batches (B i is the i th batch). Given L initial batches, grammar-induction is used to find a rule for dividing the incoming batches of data into M non-overlapping variablelength subsequences; that is, B i = S i1 ∪ S i2 ∪ ... ∪ S i M (all batches are split in the same points). Clustering is then applied to the set of subsequences S 1j , S 2j , ..., S Lj for each j separately. A new incoming subsequence is flagged as an outlier using dynamic clustering and observing when it is either far from its closest cluster centroid or belongs to a sparsely populated cluster. There are other techniques besides clustering that also use the same time series as the reference of normality. For instance, BIB019 use the same time series to represent each subsequence with a value that indicates how dissimilar it is with the rest (connectivity value). To this end, a Markov chain random walk model is applied in a graph where each node is a subsequence and each edge the pairwise similarity value between the nodes BIB007 . In particular, the pairwise similarity values are computed based on the Piecewise Aggregate Pattern Representation (PAPR), which is a matrix representation that captures the statistical information covered in the subsequence. External time series. There are some methods that rely on an external time series as a reference of normality, assuming that it has been generated by the same underlying process but with no outliers. For example, BIB017 use an external time series to find a set of exemplars that summarizes all of its subsequences within it and which detects outliers as those that are far from their nearest exemplar (Ŝ). In this case, subsequences are represented by a feature vector of two components that captures both the shape and the stochastic variations of the subsequences in a time series, using smoothing and some statistics (e.g., the mean and the standard deviation). The authors use a weighted Euclidean distance in equation (7), taking into account the components of both a subsequence and its nearest exemplar. In this category, we have also included techniques that use past non-outlier subsequences as the reference of normality. Even if these subsequences belong to the same time series, this set is considered as an external set where outliers are not detected, unlike the previous category. For instance, BIB018 collect the most relevant subsequences within a series of past subsequences in a dictionary. Subsequence outliers are those that cannot be accurately approximated by a linear combination of some subsequences of the dictionary (Ŝ), resulting in a large error in (7) using the Euclidean distance BIB022  . Previous subsequence. Finally, there are some techniques that only use the previous adjacent non-overlapping window to the subsequence being analyzed as the reference of normality, which means that they have a much more local perspective than the others. BIB005 and use this reference of normality to obtainŜ. Specifically, the authors represent each subsequence by a bitmap; that is, a matrix in which each cell represents the frequency of a local region within a subsequence (the frequency of the subwords). A subsequence whose local regions differ from the regions of its previous adjacent subsequence (Ŝ) is flagged as an outlier, using the squared Euclidean distance between each pair of elements of the bitmaps. In this case, bitmaps are incrementally updated at each time step. Returning to the general classification of the subsequence outlier detection techniques, the third group of methods belongs to the prediction model-based category in Fig. 15 , which assume that normality is reflected by a time series composed of past subsequences. These methods intend to build a prediction model that captures the dynamics of the series using past data and thus make predictions of the future. Subsequences that are far from those predictions are flagged as outliers because, although they may resemble subsequences that have appeared previously, they do not follow the dynamics captured by the model: where S = x p , ..., x p+n−1 is the subsequence being analyzed,Ŝ is its predicted value, and τ is the selected threshold. Predictions can be made in two different manners: point-wise or subsequence-wise. Models that use point-wise prediction make predictions for as many points as the length of the subsequence iteratively. With this in mind, any method within Section 3.1 could be used for this purpose. However, since each predicted value is used to predict the subsequent point, the errors accumulate as predictions are made farther into the future. In contrast, the subsequence-wise prediction calculates predictions for whole subsequences at once (not iteratively). Within this category, BIB023 use Convolutional Neural Networks (CNN) to predict whole subsequences and detect outliers using a model built with past subsequences. The next subsequence outlier detection methods are the frequency-based, as shown in Fig. 15 , which also use one of the reference of normality mentioned in Fig. 17 . A subsequence S is an outlier if it does not appear as frequently as expected: where f (S) is the frequency of occurrence of S,f (S) its expected frequency, and τ a predefined threshold. Due to the difficulty of finding two exact real-valued subsequences in a time series when counting the frequencies, these methods all work with a discretized time series. A paradigmatic example can be found in BIB003 . Given an external univariate time series as reference, a subsequence extracted via a sliding window in a new univariate time series is an outlier relative to that reference if the frequency of its occurrence in the new series is very different to that expected. BIB016 also propose an algorithm based on the frequency of the subsequences but the aim is to detect periodic subsequence outliers together with their periodicity. In this case, the reference of normality is the same time series. The intuition behind this method is that a periodic subsequence outlier repeats less frequently in comparison to the more frequent subsequences of same length. The algorithm checks the periodicity based on the algorithm described in BIB011 . As shown in Fig. 15 , the last group of subsequence outlier detection methods correspond to information theory based techniques, which are closely related to the frequency-based methods. In particular, BIB002 BIB004 focus on detecting periodic subsequence outliers in discretized univariate time series using this theory. They assume that a subsequence that occurs frequently is less surprising and thus carries less information than a rare subsequence. Therefore, the aim is to find infrequent but still repetitive subsequences with rare symbols, using the same time series as the reference of normality; that is, BIB002 BIB004 mark S as an outlier if where I (S) ≥ 0 is the information carried by S and f (S) ≥ 1 is the number of occurrences of S. I (S) is computed taking into account the number of times the symbols within S are repeated through the series, so a discretized subsequence S that has symbols that do not commonly appear in the time series has a large I (S) . Conversely, if f (S) is large (S occurs frequently), then the information I (S) will be lower, closer to 0. A summary of the methods that detect subsequence outliers in univariate time series is presented in Table 5 . Most of these methods detect non-periodic outliers of fixed-length, assuming the length is known in advance. Many techniques use a discretized version of the time series to compare real-valued subsequences effectively or to speed up the search process of outliers, this one specifically in the discord discovery category. However, discretizing a time series may cause loss of information. In contrast to the many methods that discover point outliers, the analyzed methods for subsequences are not iterative. In addition, for all of the authors, the outlier represents an event of interest. A reference of normality is also commonly used when detecting subsequence outliers. Finally, it is worth mentioning that some methods may perform better in time series with periodic or repetitive patterns (e.g., clustering, the frequency-based, and the information theory based).