\section{Introduction}

% Uma série temporal é uma coleção de observações feitas sequencialmente ao longo do tempo, usualmente com domínio nos números reais. 
% Séries temporais são encontradas nas mais variadas áreas de aplicação, tais como finanças, \textit{marketing}, agricultura, meteorologia e coleta de dados industriais e científicos. 
% Devido ao recente avanço tecnológico e à crescente capacidade de armazenamento dos computadores, o volume de dados relacionados a séries temporais coletados, armazenados e disponíveis para análise tem aumentado constante e substancialmente. 
% Como resultado, surge o desafio de pesquisar de forma eficiente bases de dados de séries temporais. 

A time series is a collection of observations obtained sequentially over time, usually in the real domain.
Time series are found in several application areas, such as finance, marketing, agriculture, weather, industrial and scientific data gathering.
Due to the recent technological advances and the increasing storage capacity of computers, the volume of data related to time series collected, stored and available for analysis has increased constantly and substantially.
As a result, it has been increasingly important to perform search and retrieval operations efficiently over time series databases.

% A busca por similaridade em bases de dados de séries temporais é uma ferramenta importante para extrair conhecimento dessas bases.
% Ela é amplamente empregada como sub-rotina em aplicações baseadas em agrupamentos~\cite{Kalpakis2001}, classificação~\cite{Geurts2001} e mineração de regras de associação~\cite{Luo2004}.
% Por exemplo, por meio dessa busca é possível determinar, a partir de dados agrometeorológicos, regiões para as quais um determinado comportamento seja similar ao ocorrido em regiões produtoras de cana-de-açúcar em períodos próximos.

Similarity searching on time series databases is an important tool to extract knowledge from these databases. 
It is widely used as a subroutine in applications based on clustering \cite{Kalpakis2001}, classification \cite{Geurts2001} and mining association rules \cite{Luo2004}.
%For example, through this search it is possible to determine, using agro-meteorological data, regions for which a particular behavior is similar to that in the regions producing cane sugar in the coming periods.
Through similarity searches, it is possible to find locations with similar behavior. For instance, through the analysis of agrometeorological data, we can find sugar-cane producing regions and regions similar to them to learn what features should be employed and nurtured to strengthen  the performance of other regions~\cite{RomaniGZTT10}.


% O problema de busca por similaridade em séries temporais pode ser dividido em duas classes: casamento completo e casamento de subsequências~\cite{DasEtAl1998}. 
% Enquanto no casamento completo consideram-se séries temporais que possuem o mesmo tamanho, no casamento de subsequências as séries temporais comparadas podem ter tamanhos diferentes. 
% Neste trabalho, é enfocada a segunda classe de busca por similaridade em séries temporais, o casamento de subsequências, já que em aplicações reais as séries temporais usualmente possuem tamanhos diferentes.

The problem of performing similarity queries over time series can be divided into two classes: whole matching and subsequence matching~\cite{DasEtAl1998}.
While whole matching compares complete series with same sizes, subsequence matching compares series with different sizes.
In this article, we focus on the second class of similarity queries, the subsequence matching, since it is more general and time series usually have different sizes in real applications.

% Outra característica deste trabalho é que ele parte do conceito de que séries temporais em domínios contínuos podem ser discretizadas para diminuir a complexidade e a dispersão local dos dados. 
% Para isso, é feita a discretização de uma série temporal de um domínio contínuo para um domínio discreto de baixa cardinalidade. 
% A série passa a ser representada por uma cadeia de caracteres (\textit{string}). 
% Dessa forma, o problema original da busca por similaridade entre séries temporais pode ser traduzido em um problema de comparação de \textit{strings}. 
% Um método de acesso que permite resolver de forma eficiente problemas que envolvam esse tipo de comparação é a árvore de sufixo generalizada, a qual estende a árvore de sufixo para indexar mais do que uma \textit{string} simultaneamente~\cite{Gusfield1997}.


%The concept of time series in continuous domains which can be discretized to reduce complexity and local data dispersion is also applicable in this work.
Time series in the domain of real numbers can be discretized to decrease data complexity and local dispersion.
%For this, the time series of a continuous domain discretization is made to a discrete domain of low cardinality.
In order to do so, the real domain data is converted into a discrete and low cardinality domain.
Many techniques have been proposed in the literature, such as the \textit{Discrete Fourier Transform} (DFT)~\cite{Faloutsos1994}, the \textit{Discrete Wavelet Transform} (DWT)~\cite{Chan99}, the \textit{Singular Value Decomposition} (SVD)~\cite{Keogh01}, the \textit{Adaptive Piecewise Constant Approximation} (APCA)~\cite{Geurts2001}~\cite{Keogh01}, the \textit{Piecewise Aggregate Approximation} (PAA)~\cite{Keogh01} and the\textit{ Symbolic Aggregate Approximation} (SAX)~\cite{Lin2003}, which is the most  commonly used technique and, therefore, is used as a basis for our proposal.

%dei uma procurada, normality quer dizer o quanto os dados se aproximam de uma normal, então acho que está correto mesmo
The SAX technique is based on PAA and assumes normality of the resulting aggregated values.
SAX employs an approximate distance function that lower bounds the Euclidean distance~\cite{Lin2007}. 
When using SAX, initially the time series must be transformed into the PAA representation and then it is discretized into a sequence of discrete symbols (i.e. string).
Thus, the original problem of similarity comparison between time series can be transformed into a string comparison problem.
%An access method that allows to efficiently solve problems involving this type of comparison is the generalized suffix tree, which extends the suffix tree to index more than one string \cite{Gusfield1997}.
This type of comparison can be efficiently solved using the generalized suffix tree, which extends the suffix tree to simultaneously index more than one string \cite{Gusfield1997}.

% % Na literatura, os únicos trabalhos que empregam árvores de sufixo para analisar séries temporais são os descritos em~\cite{Lin2004}~e~\cite{Faraz2011}.
% % No entanto, esses trabalhos diferem da nossa proposta pois enfocam, respectivamente, em mineração visual de séries temporais e em previsão de comportamento de séries (\textit{forecasting}).
% % Adicionalmente, esses trabalhos não usam árvores de sufixo generalizadas, impossibilitando que diversas \textit{strings} sejam analisadas. 
% % Essas diferenças com relação ao propósito e às funcionalidades oferecidas motivam o desenvolvimento de um novo método de acesso que permita a indexação de séries temporais por meio de árvores de sufixo generalizadas.
% 
% In the literature, there are only two works that employ suffix trees for analyzing time series, described in \cite{Lin2004} and \cite{Faraz2011}.
% However, these studies differ from our proposal because they focus in time series visual mining and time series behavior forecasting, respectively.
% Moreover, they do not use generalized suffix trees, making it impossible to analyze more than one string.
% These differences regarding the purpose and functionality offered motivated the development of a new access method that allows the indexing of time series using generalized suffix trees.

% Neste artigo é proposto o método Telesto, uma nova abordagem de indexação destinada a consultas por similaridade em bases de dados de séries temporais. 
% Em detalhes, Telesto é baseado em séries temporais discretizadas e em árvores de sufixo generalizadas. 
% Nesse método, as séries temporais são inicialmente discretizadas em \textit{strings} utilizando a técnica \textit{Symbolic Aggregate Approximation} (SAX)~\cite{Lin2003}. 
% Em seguida, as \textit{strings} geradas são indexadas por meio de uma árvore de sufixo generalizada.
% Para realizar consultas por abrangência entre séries temporais discretizadas por meio de casamentos de subsequências, Telesto estende o algoritmo de busca por \textit{substrings} em árvores de sufixo para calcular a distância entre as séries. 

In this article, we propose Telesto, a novel indexing technique aimed at performing similarity queries over time series.
Telesto is based on discretized time series and generalized suffix trees. 
Initially, Telesto discretizes time series and represents them as strings using SAX. 
Then, these strings are indexed using a generalized suffix tree. 
%To provide range and nearest neighbor query operations among discretized time series, Telesto extends the suffix tree substring search algorithm by calculating distances between the discretized time series. 
Finally, Telesto extends the suffix tree substring search algorithm by calculating distances between the discretized time series. This extension enables the creation of range and nearest neighbor query operators that can be applied over discretized time series.

% Este artigo está estruturado da seguinte forma. 
% Na Seção~\ref{sec:background} são resumidos conceitos usados como base para o desenvolvimento do trabalho.
% Na Seção~\ref{sec:telesto} é proposto o método Telesto, e na Seção~\ref{sec:tests} são discutidos testes de desempenho. 
% O artigo é finalizado na Seção~\ref{sec:conclusion}, com as conclusões e as propostas de trabalhos futuros.

This article is organized as follows.
Section~\ref{sec:related_work} reviews related work that employ suffix trees for analyzing time series, while
Section~\ref{sec:background} summarizes the main concepts used as the basis for developing our work.
Section~\ref{sec:telesto} describes the proposed Telesto method, and
Section~\ref{sec:tests} discusses performance tests.
Section~\ref{sec:conclusion} concludes de article and also highlights future work. 

