\section{Experiments and Results}
\label{sec:experiments}

In this section, we detail the experiments carried out to validate the proposed \hbl.
In the experiments, we used three datasets, with different dimensionalities (i.e. from 32 to 117) and number of elements (i.e. from 2,536 to 102,240).
Table~\ref{tabDados} describes each dataset, indicating its name, number of elements, dimensionality and description.
Note that these datasets are the most representative ones used in the original article of the \onion~\cite{CareloEtAl2011}.

\begin{table} [htb]
\centering
\caption{Characteristics of the datasets} 
\begin{tabular}{l@{\ \ \ }c@{\ \ \ }c@{\ \ \ }p{7.5cm}}
\toprule
Dataset & ~~~\#Elements~~~~& Dimensionality & Description \\ 
\midrule
\ch & 68,025  & 32 & Images histograms from the KDD repository of the University of California  at Irvine (\url{kdd.ics.uci.edu}) \\ 
\oz  & 2,536   & 73 & Time-series from 1998 to 2004 for ozone level detection (\url{archive.ics.uci.edu/ml/datasets/Ozone+Level+Detection}) \\ 
\kdd           & 102,240 & 117 & Dataset  containing cancer images (\url{www.kddcup2008.com})  \\
\hline
\end{tabular}
\label{tabDados}
\end{table} 

We compared the \hbl\ with the \ee\ of the \fonion\ because, to the best of our knowledge, there are no algorithms for bulk-loading \fonions\ in the literature. 
We implemented the proposed algorithm using the C++ language, and used the original implementation in C++ of the insertion-by-insertion algorithm.
The source code of the \hbl\ and the Onion-tree can be downloaded from \url{gbd.dc.ufscar.br/download/HeightBL} and \url{gbd.dc.ufscar.br/download/Onion-tree}, respectively.

In the tests, we considered the following values of expansions: 
7 for the \ch\ dataset, 
7 for the \oz\ dataset, and 
11 for the \kdd\ dataset. 
These values guarantee the best index performance for each dataset~\cite{CareloEtAl2011}.
We applied the metric $L_2$~\cite{WilsonM97} to index the \ch\ and the \kdd\ datasets, and the costly \textit{dynamic time warping}~\cite{BerndtC1994} to index the \oz\ dataset.  
Also, we applied the keep small technique as the replacement policy (Section~\ref{sec:Theoretical}).

The experiments were performed on a computer with an Intel Core i7 2.67 GHz processor and 12 GB of main memory. 
We analyzed the cost to build the index and the cost to process similarity queries. 
We collected the average number of distance calculations and the average elapsed time in seconds, which were recorded building the index 10 times and issuing 500 queries centered at elements randomly chosen from the datasets. 
We also collected the size of the indices in kilobytes.
The range queries were performed varying the radii to recover nearly from 1\% to 10\% of the elements of each dataset, and the \knn\ queries were performed varying the value of \textit{k} from 2 to 20, encompassing the most common values of  \textit{k} used when performing similarity queries.


\subsection{Building the Index}
\label{sec:Tempo}

Figure \ref{figBuildDistCalElTime} depicts the performance results to build the indices, and also shows the performance differences regarding these results. 
As expected, the \ee\ outperformed the \hbl\ with regard to the number of distance calculations (Figures~\ref{figBuildDistCalElTime}a to \ref{figBuildDistCalElTime}c)  and the elapsed time (Figures~\ref{figBuildDistCalElTime}d to \ref{figBuildDistCalElTime}e).
The \hbl\ required more distance calculations as it calculates the distance between all elements of a level during the construction of the index. 
Also, the \hbl\ was slower because it analyzes more elements during the \bl.
Considering the number of distance calculations, as the data volume and the data dimensionality increased, the performance losses of the \hbl\ also increased, ranging from 33.33\% to 42.86\%.  
As for the elapsed time, the use of a costly metric for the \oz\ impaired the proposed algorithm. 
For this dataset, the \hbl\ was 53.33\% slower.

On the other hand, the \hbl\ generated much more compact structures, as depicted in Figure~\ref{figBuildSize}.  
This is due to the fact that the \hbl\ is aimed to find pivots that guarantee a better division of the metric space, while the \ee\ may generate unbalanced structures that require the storage of several pointers to empty regions.
According to the performance differences shown in this figure, as the data volume and the data dimensionality increased, the performance gain of the \hbl\ also increased, ranging from 53.42\% up to 71.25\%. 

Not only the impressive reduced size of the indices but also the great improvement in query processing (Section~\ref{sec:Consultas}) provided by the \hbl\ over the \ee\ overcome the performance losses of our proposal for building the index.
These positive aspects demonstrate the applicability of our algorithm to index real-world data.

\begin{figure}[h]
\begin{center}
	\includegraphics[scale=0.35]{figBuildDistCalElTime.png}
\end{center}
\caption{Number of distance calculations and elapsed time to build the indices.}
\label{figBuildDistCalElTime}
\end{figure}

\begin{figure}[ht]
\begin{center}
\includegraphics[scale=0.4]{figBuildSize.png}
\end{center}
\caption{Size in kilobytes of the indices.}
\label{figBuildSize}
\end{figure}

\subsection{Processing Range and \knn\ Queries}
\label{sec:Consultas}

The \hbl\ greatly outperformed the \ee\ for all the datasets, with regard to the number of distance calculations and the elapsed time in query processing.
This is due to the fact that the proposed algorithm provides a better organization of the elements among the regions of the \fonion, guaranteeing a better division of the metric space and generating more efficient index structures.   
In detail, calculating a priori the estimated height of the index and generating a structure with approximately the estimated height provides a better distribution of the elements in the metric space. 
Thus, range and \knn\ queries usually require fewer distance calculations and spend less time to be processed over index structures generated by the \hbl, improving query performance.
On the other hand, the index structures produced by the \ee\ require that range and \knn\ queries perform more recursive calls to reach a leaf node or to find elements that answer these queries, impairing query performance.

Table~\ref{tab:RangeResults} shows that the performance gains of the \hbl\ in range query processing varied from 18.75\% up to 99.94\% in the number of distance calculations and from 10.00\% up to 99.04\% in the elapsed time.
Also, as the data volume and the data dimensionality increased, the performance gain of the \hbl\ also increased.
These results are detailed in Figure~\ref{figRangeResults}, which depicts the measures average number of distance calculations and average elapsed time for range queries recovering from 1\% to 10\% of the elements of the datasets. 
   

\begin{table}[htb]
\centering
\caption{The \hbl's performance gains (range queries)}
\begin{tabular}{l@{\ \ \ }c@{\ \ \ }c@{\ \ \ \ }c@{\ \ \ }c}
\toprule
\multirow{2}{*}{Dataset} & \multicolumn{2}{c}{\textbf{Distance calculations}}  & \multicolumn{2}{c}{\textbf{Elapsed time}} \\
& minimum & maximum & minimum & maximum \\ \midrule
\ch & 28.25\% & 38.73\% & 10.00\% & 20.00\% \\
\oz & 27.75\% & 96.43\% & 11.43\% & 76.92\% \\
\kdd & 18.75\% & 99.94\% & 16.43\% & 99.04\% \\
\bottomrule
\end{tabular}
\label{tab:RangeResults}
\end{table}

\begin{figure}[h]
\begin{center}
\includegraphics[scale=0.3]{figRangeResults.png}
\end{center}
\caption{Range queries results.}
\label{figRangeResults}
\end{figure}


Table~\ref{tab:KnnResults} shows that the performance gains of the \hbl\ in \knn\ query processing ranged from 13.38\% to 51.66\% in the number of distance calculations and from 8.57\% to 30\% in the elapsed time.
The best case referred to the \oz\ dataset, which was indexed using the costly \textit{dynamic time warping}.  
These results are detailed in Figure~\ref{figKnnResults}, which depicts the measures average number of distance calculations and average elapsed time for the value of \textit{k} ranging from 2 to 20. 

\begin{table}[htb]
\centering
\caption{The \hbl's performance gains (\knn\ queries)}
\begin{tabular}{l@{\ \ \ }c@{\ \ \ }c@{\ \ \ \ }c@{\ \ \ }c}
\toprule
\multirow{2}{*}{Dataset} & \multicolumn{2}{c}{\textbf{Distance calculations}}  & \multicolumn{2}{c}{\textbf{Elapsed time}} \\
& minimum & maximum & minimum & maximum \\ \midrule
\ch & 13.38\% & 30.38\% & 8.57\% & 16.67\% \\
\oz & 16.88\% & 51.66\% & 13.33\% & 30.00\% \\
\kdd & 37.45\% & 39.53\% & 11.67\% & 15.44\% \\
\bottomrule
\end{tabular}
\label{tab:KnnResults}
\end{table}

\begin{figure}[h]
\begin{center}
\includegraphics[scale=0.30]{figKnnResults.png}
\end{center}
\caption{\knn\ queries results.}
\label{figKnnResults}
\end{figure}

