A key operation for the (increasingly large) data series collection analysis is similarity search. According to recent studies, SAX-based indexes ofer state-of-the-art performance for similarity search tasks. However, their performance lags under high-frequency, weakly correlated, excessively noisy, or other dataset-specific properties. In this work, we propose to facilitate data series similarity search with deep learning techniques, involving both data series approximation and data series indexing. Our preliminary study focuses on developing Deep Embedding Approximation (DEA), a novel family of data series summarization techniques based on deep neural networks. Moreover, we describe SEAnet, a novel architecture specially designed for learning DEA, that introduces the Sum of Squares preservation property into the deep network design. Finally, we propose a new sampling strategy, SEASam, that allows SEAnet to efectively train on massive datasets. Comprehensive experiments verify the advantages of DEA learned using SEAnet. These preliminary results can lead to further progress in this area, by developing more customized architectures and training strategies, better integrating DEA with index structures, learning novel data series indexes, and facilitating faster model training.
lem that SAX fails in hard datasets with specific propWith the rapid developments and deployments of modern erties [8]. Since SAX is the symbolization of Piecewise sensors, massive data series1 datasets are now being gen- Aggregate Approximation (PAA) [6], failure of PAA to erated, collected and analyzed in almost every scientific correctly represent some data series directly translates domain [1]. Data series similarity search aims to find the to failure of the PAA-based SAX. For example, the high closest series in a dataset to a given query series according frequency of Deep1B series means that each PAA segto a distance measure, such as Euclidean distance, which ment has to average many highly-varying points, leading is one of the most widely used [2]. Similarity search can to similar PAA values across diferent segments, and to be divided into exact search and approximate search [3]. indistinguishable SAX words across diferent series. InApproximate similarity search may not always produce troducing more SAX words could alleviate the problem, the exact answers, but in most cases, it produces answers but would lead to an undesirably long summarization that are very close to the exact ones [4]. Thus, it is very that could not be efectively indexed. popular in practice, and widely used on massive series To address the aforementioned problems, we propose collections to enable interactive data exploration and to build a data series index based on Deep Embedding other latency-bounded applications [5]. In this work, we Approximations (DEA), i.e., data series summarizations focus on approximate similarity search under Euclidean derived from embeddings learned using deep neural netdistance. works. Embedding techniques, or representation learn
Indexes are widely employed to speed up data se- ing [9], is to learn vectors possessing necessary latent ries similarity search [3, 4]. Most indexes are based information for classification, clustering, and other downon summarized representations of the data series [2] of stream applications. Embedding techniques have been lower dimensionality. Symbolic Aggregate approXima- proven to be capable of capturing frequency [10] and tion (SAX) [6] is a popular and efective discretized sum- other latent properties. However, data series embedmarization. SAX-based indexes [7] are the state-of-the- ding has not been adapted to and evaluated for similarity art (SOTA) data series similarity search methods [3, 4]. search (and could also be applied to other tasks, e.g., anomaly detection [11, 12, 13]).
Pnreoyc,eAeudisntrgaslioaf.the VLDB 2022 PhD Workshop, September 5, 2022. Syd- Specifically, we propose to replace traditional summa† supervised by Themis Palpanas. rizations (e.g., PAA) with DEA, and then be symbolized $ qitong.wang@etu.u-paris.fr (Q. Wang) and indexed by an iSAX index. DEA targets to preserve © 2022 Copyright for this paper by its authors. Use permitted under Creative Commons License original pairwise distances in the lower-dimensional DEA CPWrEooUrckReshdoinpgs IhStpN:/c1e6u1r3-w-0s.o7r3g ACttEribUutRion W4.0oInrtekrnsahtioonpal (PCCroBYce4.0e).dings (CEUR-WS.org) space. Thus, it is naturally capable of being symbolized 1A data series, or data sequence, is an ordered sequence of points. into SAX, on which an iSAX index can be built. Tdihmeemnsoiostn cthomat mimopnotsyepsethoefsdeqatuaensceerioersdiesritni mgeis steimriee;s,thwohugerhe, tthhies Our preliminary results show that compared to PAA dimension could also be the mass, angle, or position [1]. and SAX (which is based on PAA), DEA better preserves pairwise distances, leading to a more efective index DCaotlaleScetiroiens for data series similarity search. This can be used as DEAaPrbolmueispirnigntfutorthfaecridliitraetcetifounrsthienrclpurdoegrdeesvselionpitnhgis maroerae. SEAsam sample (3.3) iSAbXasIneddex AnswQeureQryuery customized architectures and training strategies based Train SEAnet (3.1) Construct index Approximate fgoarncaitoliinbtasgteiDrnvEgaAtfiaolsentaesrrnfDrionEmgAwpliertaehrlinimnindinegxaorsrytrtrrueacsntuuslfrteesr,drbienesgitgt[en1rs4,i]anontend- EmSbyemdbsoelriizees DtoEADEA DEAS-AbXassed Answer massive datasets. Calculate DEA-based SAX Indexing and Query Answering
Note that existing studies on learned indexes [15] cannot be straightforwardly employed for facilitating data Figure 1: Workflow of DEA-based similarity search. series similarity search with deep learning techniques.
This is true, because most existing methods assume that the data are sortable in a natural order, which can then be data series. denotes a collection of data series, i.e., captured by learned distribution functions [15]. However, = {1, ..., }. We call the size of the data series such global orders for data series similarity search do not collection. A summarization = {1, ..., } of a seexist (since the order depends on the queries) [16]. Fur- ries is a lower, -dimensional representation, which thermore, existing methods suitable for similarity search preserves some desired properties of . For similarity are built upon grid indexes [17, 18], which do not scale to search, the target property is pairwise distance space the high dimensionalities (i.e., in the order of 100s-1000s) structure of , i.e., ∀, ∈ , ′(, ) ≈ (, ), of data series. Hence, how to extend existing studies where , are summarizations of , , (· , · ), and to resolve the aforementioned open problems remains a ′(· , · ) are distance measures in series and summarizachallenging research direction. tion spaces, respectively. The distance measure
In this work, we propose the following research direc- we use is Euclidean distance [2]. ′ in the summarizations: tion space needs not be the same as , e.g., for PAA, 1. [Architecture] Design novel architectures that ′(· , · ) = √/√ × (· , · ). ′ for DEA is the same are specifically built to support high-quality DEA and as PAA if it’s scaled for SoS preservation. Otherwise, similarity search. Our preliminary solution, SEAnet (cf. ′(· , · ) = (· , · ). Given a query series of length , Section 3.1), introduces and formalizes the principle of a series collection of size and length , a distance Sum of Squares (SoS) preservation. measure , similarity search targets to identify the se2. [Training Dataset] Propose novel sampling strate- ries ∈ whose distance to is the smallest, i.e., gies for massive data series collections, enabling efective ∀ ∈ , ̸= , (, ) ≤ (, ). Instead of training for deep models. One such example is SEAsam ifnding the exact closest series , approximate simi(cf. Section 3.2), which demonstrates that intelligent sam- larity search targets to find a series ′ ∈ such that pling strategies can help improve the performance of the (′, ) ≈ (, ). (, )/(′, ) ∈ (0, 1] is deep network models. called ′’s tightness.
3. [Learned Indexes] Integrate index structure build- The most prominent data series indexing techniques ing into DEA learning to fully exploit the edges of DEA. can be categorized into optimized scans [19], and treePushing further in this direction, it would be interesting based indexes [20]. Recent studies [3, 4] have demonto learn a specifically designed index structure together strated that the SAX-based indexes [7] achieve SOTA perwith DEA learning. formance under several conditions. In this work, we use 4. [Model Training] Address the problem of the long MESSI as our iSAX index [21] , because its main-memory training times needed by the deep neural models (which operation and parallel design lead to SOTA performance. can be significantly slower than traditional approaches), by introducing transfer learning and domain adaptation techniques in this context. 3. DEA-based Similarity Search
A data series, = {1, ..., }, is a sequence of points, where each point = (, ), 1 ≤ ≤ is associated to a real value and a position . The position corresponds to the order of this value in the sequence. We call the length, or dimensionality of the Figure 1 illustrates the proposed DEA-based data series similarity search framework, including the SEAnet architecture. Given a series collection, SEAsam first draws representative samples to train SEAnet. After SEAnet converges, it embeds all series into DEAs, which are further discretized into SAXs. Thus, DEA-based SAXs are structured into an iSAX index, where approximate similarity search can be eficiently conducted.
C o Ln v a ry e 1 L rryaeoNm irLae3n 2 Decoder Stacked Dilated ResBlocks
Ln aT i n e
a 2h r 2
L L lxaPooM LykaeeRU rryae1oNm ′ Stacked Dilated ResBlocks
C o Ln v a ry e 1 an Laen T i h r 1 (a) SEAnet Architecture 1.9,… ,1.72
Leaky ReLU LayerNorm2
Leaky ReLU
I d e n itt y Up/ Downsample
L i n k LayerNorm1 -th Layer Dilated ResBlock (b) Dilated ResBlock in SEAnet … …
SEAnet is a novel autoencoder proposed to learn high- based on the largest SoS is equivalent to selecting the quality DEA (cf. Section 3.1). Moreover, it introduces the largest eigenvalues in linear dimensionality reductions principle of SoS preservation for lower dimensionality on z-normalized datasets, with the purpose of preserving representation learning (cf. Section 3.1.1). SEAsam makes information about the dataset through linear transformause of the inverse iSAX sortable summarization [22] (cf. tions [24]. Thus, SoS may be regarded as an indicator Section 3.2). of transformation quality. By keeping SoS invariant, the quality of DEAs is upheld from this perspective, and the 3.1. SEAnet Architecture networks then focus on learning the nonlinear transformations.
The SEAnet architecture is illustrated in Figure 2a. The We now elaborate on the architecture design and ifrst part of the SEAnet encoder, from ConvLayer1 to model training under SoS preservation. Given the (zMaxPool, comprises stacked dilated full-preactivation normalized) input dataset, SoS preservation requires two ResBlocks in Figure 2b for nonlinear transformations. steps: (1) z-normalizing the output of encoder (DEAs) The second part of the SEAnet encoder, from Linear1 and decoder (the reconstructed series); and (2) scaling to LayerNorm2, comprises two linear layers for dimen- the series by 1/√ and DEA by 1/√ in and . sionality reduction. Unlike most existing encoders with Based on theoretical analysis [25], we observe that linear final layers [ 23], the SEAnet encoder is finalized scaling series and DEA will not only keep the two disby LayerNorm2, which is specifically designed using the tances to the same level, but will also largely stabilize the SoS preservation principle. distance distributions. Thus, by z-normalizing DEA, and
SEAnet is trained in a pairwise manner by mini- scaling series and DEA in and , SEAnet succeeds batched Stochastic Gradient Descent (SGD). Its loss func- in providing high-quality DEAs by preserving SoS. tion is a linear combination of two components: (1) The Compression Error (i.e., the average diferences be- 3.2. Sampling with SEAsam tween the original distance of data series pairs (, ) and their DEA distance) evaluates whether original dis- The representativeness of the training set upper bounds tances are well preserved in the DEA space. (2) The for the quality of the deep models. Not only we need our Reconstruction Error (i.e., the average distance be- sample to efectively cover the entire space of a given tween the original series and the reconstructed series) dataset, but also we need to eficiently select this sample evaluates how well the original series can be recon- without having to perform expensive computations on structed using SEAnet. the full dataset.
To this end, we propose SEAsam (SEA Sampling), a 3.1.1. Sum of Squares Preservation novel data series sampling strategy based on the sortable data series representation, InvSAX [22]. Recall that SAX We propose a SoS preservation framework for efective ifrst transforms the data series into real values , and DEA learning. SoS preservation has been observed be- then quantizes these real values, representing them using fore [24], but to the best of our knowledge, has never been discrete symbols [20]. The core observation is that evformally introduced to representation learning. Given ery subsequent bit in a SAX word contains a decreasing an × matrix , where each row ,* corresponds amount of information about the location of its correto a series and each column * , corresponds to a po- sponding data point, and simply increases the degree of sition, SoS = ∑︀, 2, . Note that defining new axes precision. Interleaving SAX’s bits such that all significant Y axis: 1st BSF Tightness X axis: Number of Series Examined 0.90 bits across each SAX word precede all less significant bits ifrstly introduced SoS preservation principle, for efecpresents a value array with descending significance, i.e., tively learning DEA. A new sampling strategy, SEAsam, is InvSAX. SEAsam orders the series collection by their introduced in order to facilitate SEAnet’s training on masInvSAX representations, and draws samples at equal- sive collections. We demonstrate that the DEA learned by intervals (e.g., every 1,000 series) from this sorted order. SEAnet more closely approximates the original data seThus, SEAsam samples are expected to preserve the dis- ries distances, better preserves the true nearest neighbors tribution of the series collection by evenly covering its in the summarized space, better reconstructs the original InvSAX space. Moreover, the time complexity of SEAsam series, and leads to better similarity search results than is (), and the space complexity of SEAsam is (), the SOTA PAA-based iSAX (when examining either a rendering SEAsam an eficient strategy. small, or a large number of candidates). These preliminary results are very promising, they set the ground for further advancements in this area, and have the potential 4. Preliminary Results to also improve the performance of kNN classification, anomaly detection, and other similarity search-based apWe present our experimental evaluation of SEAnet, DEA- plications. based data series similarity search, and SEAsam using 7 Promising directions in our future studies include the diverse synthetic and real datasets. Totally, 5,040 deep following: models were trained to provide a thorough profile of DEA 1. Develop more customized architectures and trainarchitectures. In summary, the results demonstrate that ing strategies. An interesting candidate would be to the SEAnet DEA is robust across various dataset proper- quantify with diferentiability the nearest neighborhood ties and outperforms its competitors by better preserving preservation in the DEA space [28], which shows posioriginal pairwise distances and nearest neighborhood tive correlations with the qualities of query answers in structure, leading to better approximate similarity search our preliminary results. results than traditional (PAA-based) and alternative deep 2. Investigate the lower bounding properties for DEA learning (DEA-based using FDJNet [23], TimeNet [26], that will enable exact similarity search [29]. and InceptionTime [27]) approaches. 3. Integrate DEA learning with index structure build
We evaluate the benefit of using DEA for similarity ing. Such an end-to-end framework will have more
posearch, by reporting the 1st Best-So-Far (BSF) tightness, tential to reduce information loss during the DEA and
i.e., the 1st Nearest-Neighbor (NN) distance divided by indexing steps. Candidate index structures could be
exthe 1st BSF distance given a specific query, as a function tended from trees[30] to clusters [
Work supported by ANR-18-IDEX-000, Chinese Schol- [15] T. Kraska, A. Beutel, E. H. Chi, J. Dean, N. Polyzotis, arship Council, HIPEAC 4, GENCI–IDRIS (Grant 2020- The case for learned index structures, in: SIGMOD, 101471), and NVIDIA Corporation for the Titan Xp GPU 2018. donation used in this research. [16] M. Li, Y. Zhang, Y. Sun, W. Wang, I. W. Tsang, X. Lin, I/O eficient approximate nearest neighbour search References based on learned functions, in: ICDE, 2020. [17] V. Nathan, J. Ding, M. Alizadeh, T. Kraska, Learning [1] T. Palpanas, V. Beckmann, Report on the first and multi-dimensional indexes, in: SIGMOD, 2020. second interdisciplinary time series analysis work- [18] J. Ding, V. Nathan, M. Alizadeh, T. Kraska, Tsunami: shop (itisa), SIGMOD Record (2019). A learned multi-dimensional index for correlated [2] X. Wang, A. Mueen, H. Ding, G. Trajcevski, data and skewed workloads, PVLDB (2020).
P. Scheuermann, E. J. Keogh, Experimental compar- [19] H. Ferhatosmanoglu, E. Tuncel, D. Agrawal, A. E. ison of representation methods and distance mea- Abbadi, Vector approximation based indexing for sures for time series data, DMKD (2013). non-uniform high dimensional data sets, in: CIKM, [3] K. Echihabi, K. Zoumpatianos, T. Palpanas, H. Ben- 2000.
brahim, The lernaean hydra of data series similarity [20] J. Shieh, E. Keogh, isax: indexing and mining tersearch: An experimental evaluation of the state of abyte sized time series, in: KDD, 2008. the art, PVLDB (2018). [21] B. Peng, P. Fatourou, T. Palpanas, MESSI: In[4] K. Echihabi, K. Zoumpatianos, T. Palpanas, H. Ben- Memory Data Series Indexing, ICDE, 2020. brahim, Return of the lernaean hydra: experimen- [22] H. Kondylakis, N. Dayan, K. Zoumpatianos, T. Paltal evaluation of data series approximate similarity panas, Coconut: A scalable bottom-up approach search, PVLDB (2019). for building data series indexes, PVLDB (2018). [5] A. Gogolou, T. Tsandilas, K. Echihabi, A. Bezeri- [23] J.-Y. Franceschi, A. Dieuleveut, M. Jaggi, Unsuperanos, T. Palpanas, Data series progressive similar- vised scalable representation learning for multivariity search with probabilistic quality guarantees, in: ate time series, in: NeurIPS, 2019.
SIGMOD, 2020. [24] S. Wold, K. Esbensen, P. Geladi, Principal compo[6] J. Lin, E. Keogh, S. Lonardi, B. Chiu, A symbolic nent analysis, Chemometrics and intelligent laborepresentation of time series, with implications for ratory systems (1987).
streaming algorithms, in: SIGMOD, 2003. [25] Q. Wang, T. Palpanas, Deep learning embeddings [7] T. Palpanas, Evolution of a data series index, in: for data series similarity search, in: KDD, 2021.
ISIP, 2019. [26] P. Malhotra, V. TV, L. Vig, P. Agarwal, G. M. Shrof, [8] O. Levchenko, B. Kolev, D. E. Yagoubi, R. Akbarinia, Timenet: Pre-trained deep recurrent neural netF. Masseglia, T. Palpanas, D. Shasha, P. Valduriez, work for time series classification, in: ESANN, Bestneighbor: Eficient evaluation of knn queries 2017.
on large time series databases, KAIS (2020). [27] H. I. Fawaz, B. Lucas, G. Forestier, C. Pelletier, [9] Y. Bengio, A. C. Courville, P. Vincent, Represen- D. F. Schmidt, J. Weber, G. I. Webb, L. Idoumghar, tation learning: A review and new perspectives, P. Muller, F. Petitjean, Inceptiontime: Finding PAMI (2013). alexnet for time series classification, DMKD (2020). [10] J. Wang, Z. Wang, J. Li, J. Wu, Multilevel wavelet de- [28] L. Van der Maaten, G. Hinton, Visualizing data composition network for interpretable time series using t-sne., JMLR 9 (2008).
analysis, in: KDD, 2018. [29] P. Indyk, R. Motwani, P. Raghavan, S. S. Vempala, [11] P. Boniol, T. Palpanas, Series2Graph: Graph-based Locality-preserving hashing in multidimensional Subsequence Anomaly Detection for Time Series, spaces, in: SOTC, 1997.
PVLDB 13 (2020). [30] K. Echihabi, P. Fatourou, K. Zoumpatianos, T. Pal[12] P. Boniol, M. Meftah, E. Remy, T. Palpanas, dCAM: panas, H. Benbrahim, Hercules Against Data Series
Dimension-wise Activation Map for Explaining Similarity Search, PVLDB (2022).
been made available at http://www.mi.parisdescartes.fr/ ~themisp/seanet.