\section{Background}\label{sec:background}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{Time Series Similarity}

%Seja $T = \{T_1, T_2...,T_n\}$ uma base de dados com $n$ séries temporais e $T_q$ uma série temporal de consulta. 
%Dada uma função de distância $d(T_i,T_q)$ que indica a dissimilaridade entre as séries $T_i$ e $T_q$, a busca por similaridade em séries temporais pode ser dividida em duas classes~\cite{DasEtAl1998}, as quais são descritas a seguir:

Let $T = \{T_1, T_2...,T_n\}$ be a database with $n$ time series and $T_q$ be a time series center of a query.
Given a distance function $d(T_i,T_q)$ that denotes the dissimilarity between the time series $T_i$ and $T_q$, similarity queries in time series databases can be divided into two types \cite{DasEtAl1998}:

\begin{enumerate}

%\item \textbf{Casamento completo}, no qual comparam-se séries temporais de mesmo tamanho, calculando as distâncias $d(T_i,T_q)$ entre $T_q$ e todas as séries $T_i \in T$ e recuperando as séries mais próximas. 
%\item \textbf{Casamento de subsequência}, no qual comparam-se séries temporais de tamanhos diferentes, ou seja, $T_q$ possui tamanho menor ou igual ao tamanho das séries $T_1, T_2...,T_n$. 
%O casamento de subsequências pode ser transformado em um casamento completo se for utilizado uma janela deslizante do tamanho da série de consulta $T_q$ na série $T_i \in T$, conforme ilustrado na Figura~\ref{fig:subseq}.

\item \textbf{Whole matching}, in which time series of the same size are compared (i.e. $T_q$'s size is equal to the time series in database $T_1, T_2...,T_n$), the distances $d(T_i,T_q)$ between the series $T_q$ and $T_i \in T$ are calculated, and the nearest series are retrieved.
%
\item \textbf{Subsequence matching}, in which time series with different sizes are compared, i.e. $T_q$'s size is equal or smaller than the time series in database $T_1, T_2...,T_n$.
Subsequence matching can be transformed into a whole matching by using a sliding window whose size is equal to the size of the query $T_q$ in $T_i \in T$, as shown in Figure~\ref{fig:subseq}.

\end{enumerate}

\begin{figure} [h]
\centering
\includegraphics[width=0.35\textwidth]{figuras/subseq.png}
\caption{Subsequence matching transformed into a whole matching.}
\label{fig:subseq}
\end{figure}

%Um tipo de consulta importante frequentemente utilizado em buscas por similaridade em bases de dados de séries temporais é a \textbf{consulta por abrangência}. 
%Ela é definida da seguinte maneira. 
%Dado $r_q$ um raio de consulta, a consulta por abrangência retorna todas as séries temporais $T_i \in T$ que satisfaçam à condição $d(T_i,T_q) \leq r_q$. 
%Este trabalho enfoca em consultas por abrangência por meio de casamentos de subsequência em bases de dados de séries temporais.

The main unary similarity queries most frequently used over time series databases are the range and the nearest neighbor queries.
The range query is defined as follows.
Given $r_q$ as a range distance, a range query retrieves the time series $T_i \in T$ such as $d(T_i,T_q) \leq r_q$. 
On the other hand, the nearest neighbor (NN) query retrieves the closest time series to $T_q$.
%One particular case of the nearest neighbor is when $k=1$, usually called NN query.
The NN query is important to study similarity measures, since the effectiveness of similarities measure is directly reflected on a NN classifier~\cite{DingTSWK08}.
In this work, we focus on the range and the NN queries using subsequence matching in time series databases.


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\subsection{Simbolic Aggregate Aproximation (SAX)}\label{sec:sax}

%A técnica SAX~\cite{Lin2003} permite que séries temporais de tamanho $l$ sejam representadas por \textit{strings} de tamanho arbitrário $w$ ($w<l$). 
%Dada uma série temporal, a técnica SAX consiste das seguintes etapas.
% SAX~\cite{Lin2003} allows time series of size $l$ to be represented as strings of arbitrary size $w$ ($w<l$).
%Primeiro, a série temporal é normalizada de modo que a média de seus valores seja nula e que o desvio padrão seja unitário \cite{Goldink1995}.
%Na sequência, a série temporal normalizada é convertida para a representação \textit{Piecewise Aggregate Approximation} (PAA), que reduz sua dimensionalidade \cite{Keogh2001}. 
%Por fim, a série temporal na representação PAA é discretizada em uma \textit{string} de alfabeto de tamanho $\sigma > 2$.
%O tamanho do alfabeto utilizado refere-se ao nível de discretização da técnica SAX.
The SAX representation allows time series of size $l$ to be represented by strings of arbitrary size $w$ ($w<l$)~\cite{Lin2003}.
For a given time series, SAX consists of the following steps.
Firstly, the time series is normalized using z-score, so that the data have standard normal distribution \cite{Goldink1995}.
Next, the normalized time series is converted to the Piecewise Aggregate Approximation (PAA) representation, decreasing the time series dimensionality \cite{Keogh2001}.
Lastly, the PAA representation is discretized into a string with an alphabet of size $\sigma > 2$.
The size of the alphabet refers to the SAX discretization level.

%Seja o vetor de números reais $T_a = t_{1}, ..., t_{l}$ uma série temporal normalizada de tamanho $l$.
%A representação PAA para a série temporal $T_a$ pode ser descrita pelo vetor $\bar{T_a} = \bar{t}_{1},...,\bar{t}_{w}$ de tamanho $w$, cujo $i$-ésimo elemento $\bar{t}_{i}$ de $\bar{T_a}$ é descrito pela Equação \ref{eq:paa}.

Let a vector on the real numbers' domain $T_a = t_{1}, ..., t_{l}$  be a normalized time series of size $l$.
% The time series is divided into $w$ equal-sized windows.
% The mean value of the data in a window is calculated, so that the PAA representation of $T_a$ can be described as the vector $\bar{T_a} = \bar{t}_{1},...,\bar{t}_{w}$ of size $w$. 
The PAA representation of $T_a$ can be described as the vector $\bar{T_a} = \bar{t}_{1},...,\bar{t}_{w}$ of size $w$. 
The $i^{th}$ element $\bar{t}_{i}$ of $\bar{T_a}$ can be calculated by Equation \ref{eq:paa}.

\begin{equation}
	\bar{t}_{i} = \frac{w}{l} \sum \limits_{j=\frac{l}{w} (i-1) +1}^{\frac{l}{w}i} t_{j} 
	\label{eq:paa}
\end{equation}

%A redução de dimensionalidade da série temporal $T_a$ de tamanho $l$ para tamanho $w$ por meio da técnica PAA pode ser observada na Figura \ref{fig:sax}.
%A série temporal é dividida em janelas de tamanho igual a $w$ e, para cada janela, calcula-se a média de seus valores.
%A série temporal passa então a ser representada pelo vetor de médias obtido pela Equação \ref{eq:paa}.

Figure~\ref{fig:sax} shows the PAA dimensionality reduction of the time series $T_a$ of size $l$ into a time series of size $w$, which is performed as follows.
The time series is divided into $w$ windows of equal sizes. 
Then, the mean value of the data in each window is calculated.
Finally, the time series is represented by a vector containing the mean values calculated using Equation~\ref{eq:paa}.

\begin{figure}[h!]
	\centering
	%\begin{minipage}{0.47\linewidth}
		\centering{}
		\includegraphics[width=0.4\linewidth]{figuras/sax.png}
		\caption{
			%Série temporal discretizada utilizando a técnica SAX ($l=120$, $w=8$ e $\sigma=3$), adaptada de \protect\cite{Lin2003}.
			A discretized time series using SAX ($l=120$, $w=8$ e $\sigma=3$), adapted from \protect\cite{Lin2003}.
		}
		\label{fig:sax}
	%\end{minipage}
	%\begin{minipage}{0.02\linewidth}
	%\textcolor{white}{a}
	%
	%\end{minipage}
	%\begin{minipage}{0.47\linewidth}
	%	\centering{}
	%	\includegraphics[width=\linewidth]{figuras/sax.png}
	%	\caption{
	%		***refazer***Uma série temporal discretizada utilizando o SAX utilizando $w=8$ e $a=3$. %Adaptada de \cite{Lin2003}.
	%	}
	%	\label{fig:mindist}
	%\end{minipage}
\end{figure}	

%Em seguida, a representação PAA $\bar{T_a}$ é convertida em uma sequência de símbolos discretos equiprováveis pertencentes a um alfabeto $\Sigma  = \{\alpha_{1}, ...,\alpha_{\sigma}\}$ com $\sigma$ caracteres.
%Séries temporais normalizadas apresentam uma distribuição Gaussiana, assim, definem-se os pontos crescentes $\beta_{1},...,\beta_{\sigma-1}$, de modo que a área abaixo de uma curva Gaussiana $N(0,1)$ no intervalo entre $\beta_{i}$ e $\beta_{i+1}$ seja igual a $1/\sigma$ ($\beta_{0}$ e $\beta_{\sigma}$ são definidos respectivamente por $-\infty$ e $\infty$).
%Por fim, a série temporal $\bar{T_a}$ é discretizada na \textit{string} $S_a = s_{1}s_{2}...s_{w}$, de modo que o $i$-ésimo termo $s_{i}$ é obtido por meio da Equação ~\ref{eq:alphabet}.

The PAA representation $\bar{T_a}$ is converted into a sequence of equiprobable symbols in an alphabet $\Sigma  = \{\alpha_{1}, ...,\alpha_{\sigma}\}$ of cardinality $\sigma$.
Normalized time series usually have Gaussian distribution, thus, we can define a list of sorted breakpoints $\beta_{1},...,\beta_{\sigma-1}$ such that the area under a $N(0,1)$ Gaussian curve from $\beta_{i}$ to $\beta_{i+1}$ is equal to $1/\sigma$ ($\beta_{0}$ and $\beta_{\sigma}$ are defined as $-\infty$ e $\infty$, respectively).
Then, the time series $\bar{T_a}$ is discretized into a string $S_a = s_{1}s_{2}...s_{w}$.
The $i^{th}$ element is defined using Equation~\ref{eq:alphabet}.

\begin{equation}
	s_{i} = \alpha_{j},~~~\text{if $~~~\beta_{j-1}<\bar{t}_{i}<\beta_{j}$}
	\label{eq:alphabet}
\end{equation}

%Para comparar duas séries temporais discretizadas $S_a$ e $S_q$ é necessário utilizar a função de distância \textit{MINDIST}, proposta em \cite{Lin2003} e descrita na Equação ~\ref{eq:minDist}. 
%Nessa equação, a função $dist(\alpha_{i},\alpha_{j})$ representa a distância entre dois símbolos e é calculada por meio da Equação ~\ref{eq:dist}.

Given two discretized time series $S_a$ and $S_q$, they can be compared using the MINDIST function~\cite{Lin2003}, which is  described in Equation~\ref{eq:minDist}.
The $dist(\alpha_{i},\alpha_{j})$ function represents the distance between two symbols and can be calculated using Equation~\ref{eq:dist}.

\begin{equation}
	MINDIST(S_a,S_q) = \sqrt{ \frac{l}{w} } \sqrt{ \sum \limits_{i=1}^w (dist(s_{i},s_{q_i}))^{2} }
	\label{eq:minDist}
\end{equation}

%\begin{equation}
%	D(Q,C) = \sqrt{ \sum \limits_{i=1}^n (q_{i}-t_{i})^{2} }
%	\label{eq:euclidian}
%\end{equation}

%
%\begin{equation}
%	DR(Q,C) = 
%	\label{eq:ppaDist}
%\end{equation}

\begin{equation}
	dist(\alpha_{i},\alpha_{j}) = 
		\begin{cases}
			0, &\text{if $|i-j|\le 1$}\\
			\beta_{max(i,j)-1}-\beta_{min(i,j)}, &\text{otherwise}
		\end{cases}
	\label{eq:dist}
\end{equation}

%Em \cite{Lin2007} é mostrado que a função \textit{MINDIST} se apresenta como um limitante inferior da distância Euclidiana.
%Logo, utilizar a função \textit{MINDIST} para realizar buscas por similaridade em séries temporais discretizadas por meio da técnica SAX não implica na ocorrência de falsos negativos.

Lin et al. (2007) \nocite{Lin2007} showed that the MINDIST function is a lower bound of the Euclidian distance.
Therefore, we can perform similarity queries in discretized time series using the MINDIST function warranting that no false dismissals occur.

%A série $Q$ deve ser comparada com subsequências de $T_{i}$.
%nesta categoria $m<n$, logo a busca deve ser realizada em subsequências de $T_{i}$. A série de consulta $Q$ deve ser comparada com as
