\section{Performance Evaluation}\label{sec:tests}


% O método Telesto foi validado por meio de testes de desempenho usando bases de dados reais de séries temporais extraídas de imagens de satélites AVHRR/NOAA (\textit{Advanced Very High Resolution Radiometer/National Oceanic and Atmospheric Administration}).
% Essas séries correspondem às medidas mensais do índice vegetativo NDVI (\textit{Normalized Difference Vegetation Index}), o qual indica o vigor vegetativo do solo \cite{Rouse1973} contidos nos \textit{pixels} das imagens. 
% Durante a etapa de pré-processamento utilizou-se a técnica SAX com nível de discretização igual a 5, isto é, as séries temporais foram discretizadas em \textit{strings} de um alfabeto de tamanho 5.
% Cada \textit{string} possui o tamanho de 108 caracteres, sendo que cada caractere corresponde a um mês extraído da série temporal. 

The benefits of the Telesto method were investigated through performance tests executed using a real-world time series database.
These data were extracted from a series of satellite images captured by AVHRR/ NOAA satellite (Advanced Very High Resolution Radiometer/National Oceanic and Atmospheric Administration).
These series correspond to monthly measures of the Normalized Difference Vegetation Index (NDVI), which indicates the soil vegetative vigor represented in the pixels of the images~\cite{Rouse1973}.
In the pre-processing stage, we used the SAX representation with discretization level equals to 5, i.e. the time series were discretized in strings of an alphabet of size 5.
Each string has 108 characters and each character corresponds to a month in the extracted series.

% Nos testes de desempenho foram utilizadas bases de dados com 50, 100, 150, 200 e 250 mil séries temporais e 5 grupos de consultas.
% Cada grupo possui 5 consultas diferentes de tamanhos 12, 24, 36, 48 e 60 caracteres, sendo que essas consultas consistem de séries temporais de 1, 2, 3, 4 e 5 anos, respectivamente. 
% A taxa de erro $\epsilon = 0.005$ foi utilizada para calcular o raio de abrangência $r_q$ das consultas, tal que $\epsilon = r_q/|S_q|$ e $|S_q|$ é o tamanho da série de consulta.

In the performance tests, we used databases with 50, 100, 150, 200 and 250 thousand time series and 10 query groups.
Each group has queries of 5 different sizes (12, 24, 36, 48 and 60 characters), such that the queries consist of time series corresponding to 1, 2, 3, 4 and 5 years, respectively.
We performed both range and NN queries.
For range queries, we used the error $\epsilon = 0.005$ to calculate the query radius $r_q$, such that $\epsilon = r_q/|S_q|$ and $|S_q|$ is the query size.
%And for k-nn queries, we used $k = 1, 50, 100, 150, 200$ and $250$.


% Os testes foram realizados em um computador executando o sistema operacional Linux (32 bits) com um processador \textit{Intel Core i7} 2,67 Ghz, 12 GB de memória primária e 2 TB de memória secundária. 
% Para comparar a etapa de consulta proposta pelo método Telesto, foi implementado um método que realiza  busca sequencial na base de séries discretizadas.
% Ambos os métodos, Telesto e busca sequencial, foram implementados para memória primária usando a linguagem de programação C++, considerando apenas a fase de filtragem.
% Foram analisados os tempos gastos durante a etapa de construção do Telesto e durante o processamento das consultas por abrangência do Telesto e da busca sequencial. 
% Todos os testes foram executados 5 vezes, portanto, os valores apresentados e discutidos nessa seção correspondem à média dessas 5 execuções.

The experiments were conducted on a computer with an Intel Core i7 2.67 GHz processor, 12 GB of main memory, 2 SATA 1 TB hard disks and Linux Ubuntu system (32 bits).
To compare the range and NN queries operations, we implemented a method that performs sequential scan on the databases.
Both methods, Telesto and sequential scan, were implemented using the C++ programming language (main memory only), considering the filtering stage.
All tests were performed 5 times, so the values presented and discussed in this section correspond to the average of these 5 executions.

% A Figura~\ref{test:build} mostra o tempo gasto em segundos durante a etapa de construção do Telesto.
% Pode-se observar um crescimento linear do tempo gasto de acordo com o aumento do tamanho da base de dados  (linha pontilhada). 
% Portanto, conclui-se que a etapa de construção do Telesto é escalável, desde que o aumento no tamanho da base não degradou o seu desempenho.  
% Além disso, o tempo gasto para construir o índice da base de 250.000 séries temporais foi de aproximadamente 40 segundos, o que pode ser considerado pequeno, uma vez que, como apresentado nos próximos testes, uma única busca sequencial nessa base gasta em média 10 segundos.

Figure~\ref{test:build} shows the time spent (in seconds) by Telesto during the \textbf{construction stage} for distinct database sizes.
Telesto showed a linear growth in response to increasing data volumes (dotted line).
Therefore, we can conclude that the Telesto's construction stage is scalable, since the increase in volume did not impair its performance. 
Furthermore, the time spent to construct the index of the biggest database was approximately 70 seconds, which can be considered small, since, as shown in the next test, a single sequential scan for range query on that database spent on average 9 seconds.

\begin{figure}[h]
\centering
\includegraphics[height=4.5cm]{figuras/buildTime}
\caption{Telesto: time spent during the construction stage.}
\label{test:build}
\end{figure}

% Os tempos gastos no processamento de consultas por abrangência são mostrados nas Figuras~\ref{test:range}. %~e~\ref{test:rangeb}.
% Enquanto a Figura~\ref{test:rangea} investiga o impacto do aumento do tamanho da base de séries temporais, a Figura~\ref{test:rangeb} investiga o impacto do aumento do tamanho da consulta considerando a base de tamanho 250K.   
% Pode-se observar que, em ambos os casos, o desempenho do Telesto foi muito superior ao desempenho da busca sequencial. 
% Telesto proveu uma melhora de desempenho que variou de 108 a 118 vezes quando considerado o impacto do aumento do tamanho da base, e que variou de aproximadamente 99 a 167 vezes quando considerado o impacto do aumento do tamanho da consulta.
% Outra característica positiva do Telesto é que ele apresentou um crescimento linear no tempo gasto de acordo com o aumento do tamanho da base de dados indexada (Figura~\ref{test:rangea}). 
% Ainda mais importante, com exceção da consulta de tamanho 12 que apresentou tempo gasto bastante reduzido, pode-se observar que o tempo gasto pelo Telesto no processamento da consulta foi praticamente indiferente ao tamanho da consulta utilizada (Figura~\ref{test:rangeb}).
% Conclui-se, portanto, que Telesto também é escalável em relação ao tamanho da consulta, além de ser muito eficiente.

The second set of experiments evaluated the \textbf{querying stage}. 
First, we show in Figure~\ref{test:range} the time spent to process range queries.
The results depicted in Figure \ref{test:rangea} evaluate the impact of the database size increase and in Figure \ref{test:rangeb} evaluate the impact of the query size increase using a database of size 250K.
As can be observed, in both cases Telesto's performance was far superior to sequential scan.
In fact, Telesto provided a performance gain that ranged from 116 to 176 times considering the impact of database size increase, and ranged from approximately 180 to 220 times considering the impact of query size increase.
Another positive feature is that Telesto showed a linear growth in query cost in response to increased database sizes (Figure \ref{test:range}).
Even more important, except for the query size of 12 symbols, which showed a greatly reduced time spent, it can be observed that Telesto's time spent during range query processing was almost indifferent to the size of the query  (Figure \ref{test:rangeb}).

\begin{figure}[h]
    \centering
		\subfigure[Increasing database size]{
			\label{test:rangea}
			\includegraphics[height=4.5cm]{figuras/rangeSize}
		}
		\subfigure[Increasing query size]{
		   \label{test:rangeb}
		   \includegraphics[height=4.5cm]{figuras/rangeQuery}
		}
	\caption{
		Time comparison of range query processing.
	}
	\label{test:range}
\end{figure}

Figure~\ref{test:1nn} depicts the performance results for NN queries.
While the results shown in Figure \ref{test:1nnSize} evaluate the impact of the database size increase, the results shown in Figure \ref{test:1nnQuery} evaluate the impact of a query size increase using the database of size 250K.
% One can be observed that in both cases, the Telesto's performance was far superior to the sequential scan performance.
Telesto provided a performance improvement of up to 20 times considering the impact of the database size increase, and up to almost 168 times considering the impact of the query size increase.
Similar to the range query performance results, Telesto also showed a linear growth in NN query costs in response to increased database sizes (Figure \ref{test:1nnSize}).
We can conclude that Telesto is scalable in the size of the query, and it is very efficient.

\begin{figure}[h]
    \centering
		\subfigure[Increasing database size]{
			\label{test:1nnSize}
			\includegraphics[height=4.5cm]{figuras/1nnSize}
		}
		\subfigure[Increasing query size]{
		   \label{test:1nnQuery}
		   \includegraphics[height=4.5cm]{figuras/1nnQuery}
		}
	\caption{
		Time comparison of NN query processing.
	}
	\label{test:1nn}
\end{figure}
