# Scale-BOSS-MR: Scalable Time Series Classification Using Multiple Symbolic Representations +
## 2 Literature Review  
As pointed out in the introductory part of this article, one of the main ideas of the proposed approach is to use a symbolic representation of time series. The following paragraphs elaborate on such representations and corresponding TSC methods. In [12], the authors present the SAX-VSM classification algorithm that uses the SAX representation and Term Frequency--Inverse Document Frequency (TF-IDF) weighting. A tf-idf vector is created for each class, after the training set has been transformed into SAX words. Then, the set of target time series is transformed into SAX words and the Term-Frequency (TF) vector is created for each time series in the target set. To classify a time series, the cosine similarity between the TF vectors of that series and of the classes' centers is computed. In [13], the authors introduce the Bag of SFA Symbols Ensemble classifier (BOSS) that uses Symbolic Fourier Approximation (SFA) [14] to classify a time series. To compute SFA words, a number of Fourier coefficients are computed, which are grouped based on common prefixes, building histograms per group, discretized, and mapped to an alphabet. The SFA approximation, and thus BOSS, uses a symbolic representation based on the frequency domain, providing information about the whole series. Properties of this representation lead to significant lower training times compared to using the SAX representation. The BOSS ensemble classifier is based on a 1-NN classification using multiple BOSS models at different time series' substructural sizes. However, BOSS requires the entire training set to be available while classifying target time series. In [5], the authors present the BOSS-VS classification algorithm where each data point in the training set is transformed into SFA words. Then, a centroid is created for each class and the cosine similarity is computed between centroids and target series, as in [12]. This significantly reduces computational complexity and the memory footprint of the classification algorithm, since now each target time series is only compared to the class centroids. While BOSS-VS improves in scalability, it manages to do so at the expense of accuracy. In [15], the authors present the K-BOSS-VS algorithm for time series classification, which is based on state-of-the-art symbolic time series classification algorithms, such as BOSS-VS and BOSS [5; 13]. The main intuition behind the K-BOSS-VS method is that, by exploiting SFA representations, instead of having a single centroid to represent each class label, we can have K representatives per class. K-BOSS-VS applies the K-means clustering algorithm to each class label of the training set to obtain the K representatives per class. In so doing, it is between using a single representation per class, as in [5], or computing similarities with the entire training set, as in [13]. K-BOSS-VS addresses the scalability problem while at the same time achieving an accuracy greater than BOSS-VS and close to BOSS. cBOSS [16] aims to speedup BOSS. Due to its grid-search method and the method of retaining ensemble members, BOSS is unpredictable in its time and memory resource usage. cBOSS utilizes an altered random selection of parameters of its ensemble members, allowing the user to control the build using a time contract. In doing so, it manages to significantly speed up BOSS while retaining accuracy. S-BOSS [17] is a variation of BOSS that takes into account the location of the symbolic words in a series. The intuition is that in some datasets, the locations of certain discriminatory subsequences are important. Some patterns may gain importance only when they occur in a particular location, or a frequently occurring word may be indicative of different classes depending on when/where it occurs. In [18], the authors propose WEASEL as a middle ground between BOSS-VS [5] and BOSS [13] for time series classification, balancing between accuracy and scalability.