\section{The Proposed Telesto Method}\label{sec:telesto}

% Nesta seção é proposto o método \underline{Telest}o (acrônimo para \underline{T}ime S\underline{e}ries Genera\underline{l}iz\underline{e}d \underline{S}uffix \underline{T}ree), uma nova abordagem de indexação destinada a consultas por similaridade em bases de dados de séries temporais.  
% Para construir e realizar consultas por abrangência, Telesto é dividido nas etapas de pré-processamento, construção e consulta.
% A Figura~\ref{fig:telesto_build} apresenta a etapa de pré-processamento e a etapa de construção do método Telesto. 

In this section, we describe \underline{Telest}o  (acronym for \underline{T}ime S\underline{e}ries Genera\underline{l}iz\underline{e}d \underline{S}uffix \underline{T}ree), a novel indexing approach aimed at time series databases similarity queries, which is based on discretized time series and generalized suffix trees. 
To build and perform range and NN queries, Telesto is divided into three stages: pre-processing, construction and querying.


% Na \textbf{etapa de pré-processamento} ocorre a \textit{discretização das séries temporais}, da seguinte forma. 
% Seja $T = \{T_1, T_2, \dots ,T_n\}$ uma base de dados com $n$ séries temporais. 
% Inicialmente, cada série $T_i \in T$ é recuperada do disco (Figura~\ref{fig:telesto_build}(a)) e mapeada por meio da técnica SAX em uma \textit{string} $S_i$ (Figura~\ref{fig:telesto_build}(b)). 
% Com isso, ao final dessa etapa tem-se um conjunto de séries temporais discretizadas $S = \{S_1, S_2, \dots, S_n\}$.
% Em seguida, na \textbf{etapa de construção} ocorre a \textit{indexação} das séries temporais discretizadas por meio de uma \textit{árvore de sufixo generalizada} (Figura~\ref{fig:telesto_build}c). A construção da árvore de sufixo generalizada é realizada por meio do algoritmo de construção trivial apresentado na Seção~\ref{sec:gst}.

Figure \ref{fig:telesto_build} shows the pre-processing and the construction stages of the Telesto method.
In the \textbf{pre-processing stage},  the time series are discretized as follows.
Let $T=\{T_1, T_2, \dots,$ $ T_n\}$ be a database with $n$ time series.
Initially, each series $T_i \in T$ is retrieved from disk (Figure ~\ref{fig:telesto_build}(a)) and mapped into a string $S_i$ using SAX (Figure \ref{fig:telesto_build}(b)).
%The end of this stage has a set of discretized time series $S = \{S_1, S_2, \dots, S_n \} $.
The result of this stage is a set of discretized time series $S = \{S_1, S_2, \dots, S_n \} $.
Then, the \textbf{construction stage} executes the discretized time series indexing using a generalized suffix tree (Figure \ref{fig:telesto_build}(c)).
The generalized suffix tree is constructed according to the trivial construction algorithm described in Section \ref{sec:gst}.

\begin{figure}[h]
\centering
\includegraphics[width=15.0cm]{figuras/telesto_pre_build}
\caption{Telesto: pre-processing and construction stage.}
\label{fig:telesto_build}
\end{figure}

% A \textbf{etapa de consulta} é a responsável por realizar consultas por abrangência entre séries temporais discretizadas por meio de casamentos de subsequências.
% Seja $T_q = t_1, t_2, \dots, t_m$ uma série temporal de consulta e $r_q$ o raio de consulta. 
% No primeiro passo, a série $T_q$ é mapeada por meio da técnica SAX em uma \textit{string} $S_q = s_1 s_2 \dots s_m$ (Figura~\ref{fig:telesto_range}(a)). 
% Em seguida, por meio de uma consulta por abrangência na árvore de sufixo generalizada (Figura~\ref{fig:telesto_range}(b)), o método Telesto recupera todas as séries temporais $T_i \in T$ que estejam a uma distância $d(T_q, T_i) < r_q$ (Figura~\ref{fig:telesto_range}(c)), gerando um conjunto de séries temporais de resposta que são possíveis candidatas.

The \textbf{querying stage}, depicted in Figure~\ref{fig:telesto_range}, is responsible for performing range and NN queries between discretized time series through substrings matching.
Let $T_q = t_1, t_2, \dots, t_m$ be a time series query.
In the first step, the time series $T_q$ is mapped using SAX into a string $S_q = s_1 s_2 \dots s_m$ (Figure \ref{fig:telesto_range} (a)).
Then, Telesto performs the similarity query over the generalized suffix tree (Figure \ref{fig:telesto_range}(b)).
To execute a range query, Telesto retrieves all series $t_i \in T$ that are at a distance $d(T_q, T_i) < r_q$ (Figure \ref{fig:telesto_range}(c)), where $r_q$ is the query radius.
In the NN query, Telesto retrieves the series closest to $T_q$. 
% Since MINDIST distance is a lower bound of Euclidian distance (Section~\ref{sec:sax}), the end of this stage generates a set of time series that are candidates.
%Figure \ref{fig:telesto_range} summarizes the concepts used in the querying stage.

\begin{figure}[h]
\centering
\includegraphics[width=15.0cm]{figuras/telesto_range}
\caption{Telesto: querying stage.}
\label{fig:telesto_range}
\end{figure}

% Para comparar séries temporais discretizadas por meio da técnica SAX, isto é, para calcular as distâncias $d(T_i, T_j)$ entre essas séries, Telesto usa como base a função de distância \textit{MINDIST($S_i, S_j$)}. 
% Como resultado, a consulta por abrangência em árvores de sufixo generalizadas proposta pelo Telesto estende a busca por \textit{substrings} na árvore de sufixo generalizada da seguinte forma. Seja $S_q = s_1 s_2 \dots s_m$ uma série temporal de consulta discretizada. 
% A consulta por abrangência por $S_q$ busca todas as \textit{substrings} de tamanho $m$ na árvore de sufixo generalizada. Durante cada busca, para cada nó interno $X$ percorrido na árvore, tem-se a \textit{substring} $path(X) = S_i[1:k]$ correspondente. 
% Caso \textit{MINDIST}$(S_i[1:k], S_q[1:k]) > r_q$, a busca é interrompida, isto é, realiza-se uma poda na busca, e descarta-se $S_i[1:k]$. 
% Caso a busca encontre uma \textit{substring} com $m$ caracteres $S_i[1:m]$ e \textit{MINDIST}$(S_i[1:m], S_q[1:m]) \leq r_q$, $S_i[1:m]$ é inserida no conjunto resposta.
% A Figura~\ref{fig:gst_range} resume os conceitos utilizados na busca por abrangência em árvores de sufixo generalizada.

In order to compare time series in SAX representation, i.e. to calculate the distance $d(T_i, T_j)$ between these series, Telesto uses the \textit{MINDIST$(S_i , S_j$)} distance function described in Section~\ref{sec:sax}.
The range query operation proposed extends the substring search in generalized suffix tree as follows.
Let $S_q = s_1 s_2 \dots s_m$ be a discretized time series query.
The range query search for $S_q$ finds all substrings of size $m$ in the generalized suffix tree.
During each search, for each internal node $X$ traversed in the tree, there is a corresponding substring $path(X) = S_i[1: k]$.
In the case that MINDIST$(S_i [1: k], S_q [1: k]) > r_q$, the search is stopped, i.e. a pruning occurs and $S_i[1:k]$ is discarded.
In the case when the search finds a substring $S_i [1: m]$ with $m$ characters and MINDIST$(S_i[1: m], S_q[1: m]) \leq  r_q$, $S_i[1:m]$ is inserted into the answer set.
The NN query operation is based on the same basic range query operation, however the query radius $r_q$ is variable from infinity and reduces to the distance value of the string closest to $S_q$, as the search procedure traverses the generalized suffix tree.

% Por exemplo, seja a série de consulta $T_q$ discretizada na \textit{string} $S_q = a b c$, $S_q$ possui $3$ caracteres. A busca por abrangência por $S_q$ realiza 4 consultas por \textit{substring} na árvore de sufixo generalizada (caminhos destacados em cinza). As \textit{substrings} geradas nesse processo são $\{aba, abc, bca, cab\}$. 
% For instance, let $T_q$ be a query time serie discretized into the string $S_q = a b c$, $S_q$ has 3 characters. The range query search by $S_q$ performs 4 consultations for substrings in the generalized suffix tree (paths highlighted in gray). 
% The substrings generated in these process are $\{aba, abc, bca, cab\}$. All these substrings are compared with $S_q$ during the traversal of the suffix tree. 
% In the case MINDIST$(S_i [1: k], S_q [1: k]) > r_q$, the search would have stopped, pruned and $S_i[1:k]$ discarded. In this instance no search was pruned.
% 
% \begin{figure}[h]
% \centering
% \includegraphics[height=4.5cm]{figuras/gst_range}
% \caption{Telesto: Range Query Search}
% \label{fig:gst_range}
% \end{figure}


% In the case MINDIST$(S_i [1: k], S_q [1: k]) > r_q$, the search was stopped, pruned and $S_i[1:k]$ is discarded. In this instance no search was pruned.
% In the case the search finds a substring $S_i [1: m]$ with $m$ characters and MINDIST$(S_i[1: m], S_q[1: m]) \leq  r_q$, $S_i[1:m]$ is inserted into the answer set.
% \textcolor{red}{Colocar uma poda na figura, e supor que MINDIST foi maior que o raio na descrição do exemplo}


% 
% \begin{algorithm}[h]\label{alg:MM}
% \SetLine
% \caption{Algoritmo de busca por abrangência}
% \Entrada{Série Temporal de consulta $Q = q_1 q_2 \dots q_n$}
% \Saida{conjunto de resultados}
% \Inicio{
% $Q$ é mapeada em $S = s_1 s_2 \dots s_n$;\\
% 
%   \Para{todo caminho na árvore de tamanho $n$}
%   {
%     \Se{sequencia gerada g, dist(sequencia, sequencia de consulta) $\leq$ raio}
%       {
%         proxima consulta;(PODA)\\
%       }
%     \Se{final do caminho a dist(sequencia, sequencia de consulta) $\leq$ raio}
%       {
%         insere sequencia no resultado\\
%       }
%   }
% }
% \end{algorithm}

% Outra característica da etapa de consulta do Telesto é que ela atua como uma fase de filtragem, por ser baseada no uso da função \textit{MINDIST}, a qual garante a ausência de falsos negativos.
% Em contrapartida, podem ocorrer falsos positivos, o que gera a necessidade de uma fase posterior de refinamento.
% Portanto, Telesto gera um conjunto de séries temporais que são possíveis candidatas.
% Na sequência, cada candidata tem que ser testada calculando-se sua distância com relação à série temporal de consulta no domínio original (i.e. séries não discretizadas). 

Another important feature of Telesto's querying stage is that it acts as a filtering phase, since it uses the MINDIST distance, which guarantees the absence of false negatives (Section~\ref{sec:sax}).
On the other hand, false positives can occur, which creates the need for a later refinement stage.
Therefore, Telesto generates a set of possible candidates. %time series that are possible candidates.
%As a result, each candidate must be tested by calculating its distance with respect to the time series of consultation in the original domain (not discretized series).
Consequently, each candidate must be tested in the original domain.

