\section{The Proposed HeightBL Algorithm}
\label{sec:heightBLalgorithm}

In this section, we detail the HeightBL (\textbf{Height} \textbf{B}ulk-\textbf{L}oading) algorithm, which performs a top-down \bl\ of \fonions.
It organizes the elements to be inserted into the index in advance to define the best insertion order of these elements.  
Also, it builds the  index structure by using samples to choose the pivots of the nodes.
Furthermore, it defines a strategy to estimate the ideal height that a \fonion\ should have, so that the final index structure has approximately this estimated height.

In a glance, the \hbl\ works as follows (Figure~\ref{fig:Processo}).
In the \st, the algorithm selects elements from the dataset, which are used as samples. 
Then it starts an iterative process to analyze the samples in order to identify pivots.
It generates pairs of samples and evaluates them to investigate which one is the best pair to be chosen, according to the estimated height. 
The chosen pair of samples is inserted into the index, creating a new node whose pivots are these samples.
The tasks of \textit{selecting pivots}, \textit{evaluating pivots} and \textit{node creation} are repeated recursively to obtain subtrees.
Section \ref{sub:consideracoesSample} details the \textit{sampling task}, and Section \ref{sec:algAlturas}  describes the proposed \hbl.

\begin{figure}[h]
\begin{center}
	\includegraphics[scale=0.5]{figProcesso.png}
\end{center}
\caption{General view of the \hbl.}
\label{fig:Processo}
\end{figure}

\subsection{The Sampling Task}
\label{sub:consideracoesSample}

To avoid the need to verify each pair of elements of the dataset to identify the best pair of pivots to create a new node, the \st\ chooses elements to be tested, which are used as samples. 
Therefore, it only investigates these samples to identify the best pair of pivots, pruning a large amount of data to be analyzed and reducing the time spent to build the \fonion.  

The notion used by the \st\ to generate samples is described as follows. 
It discards pairs of elements from the dataset that would generate highly unbalanced structures, i.e. structures that would provide a poor query performance. 
Consider a pair of elements. 
There are two situations in which this occurs. 
The first one occurs when the distance between the elements is too far so that the elements are located in extreme portions of the dataset. 
If this pair of elements were chosen, then most of the remaining elements would be associated with the region I of the \fonion.
The second situation occurs when the distance between the elements is too close, generating a \fonion\ with most of the remaining elements associated with its region IV (or another external region). 

Consider the dataset $S = {s_1, s_2, ..., s_n}$.
To choose samples, the \st\ performs four sequential subtasks: 
(1) finding an approximated medoid;
(2) calculating the median of the  approximated medoid;
(3) building a ring of samples; and
(4) filtering the samples.
They are described as follows. 

\vspace{0.3cm}
\noindent
\textbf{Subtask 1. Finding an approximated medoid}
 
\noindent
Subtask 1 is aimed to find an approximated medoid.
First, it randomly chooses an element $s_x \in S~(1 \leq x \leq n)$.
It also chooses two other elements, $s_v \in S$ and $s_w \in S$, such that $s_v$ is the farthest element from $s_x$ and $s_w$ is the farthest element from $s_v$.
Then, it calculates $m_v$, which is the median of the distances between $s_v$ and each remaining element of $S$, and $m_w$, which is the median of the distances between $s_w$ and each remaining element of $S$.

The generation of the approximated medoid is an iterative process that analyzes the intersection region determined by the balls centered at $s_v$ and $s_w$, using $m_v$ and $m_w$ as radii, respectively (Figure~\ref{fig:Samples}a).
Two different situations can occur.
In the first one, the intersection region contains elements, which are selected as candidates.
In the second situation, there are no elements in the intersection region. 
In this case, both radii $m_v$ and $m_w$ are incremented by a value determined by Equation~\ref{eq3} to increase the intersection region.
These radii may be incremented several times, until an intersection region that contains elements be generated and the candidates be selected.
The subtask selects the \textit{approximated medoid} from the candidates by choosing the element whose sum of distances to the remaining elements of $S$ is the smallest. 

Equation \ref{eq3} represents the \textit{distance policy}, which is used by the subtasks of the \st\ to select near elements and to increase and decrease values.
Intuitively, for datasets with high dimensionality and a large number of elements, there is a high probability to find close elements, even if we consider short distances. 
Thus, this equation uses the \textit{number of elements} of the dataset and the \textit{dimensionality} of the dataset to select near elements.
These elements should be discarded, as we discuss in subtask 4.  
This equation also determines a value that is used as an increment and a decrement in situations where it is necessary to build a ring of samples, as we discuss in subtask 3.
The motivation of Equation \ref{eq3} is to generate values between 0 and 1 using the characteristics of the dataset, such as data volume and data dimensionality. 
For non-dimensional datasets, the \textit{dimensionality} can be defined as the value of its intrinsic dimensionality.

\begin{align}
DistancePolicy = \frac{NumberOfElements}{Dimensionality + NumberOfElements}
\label{eq3}
\end{align}

\vspace{0.3cm}
\noindent
\textbf{Subtask 2. Calculating the median of the  approximated medoid}
 
\noindent
To calculate the median of the approximated medoid, subtask 2 determines the median \textit{med}  of the distances between the \textit{approximated medoid} and the remaining elements of $S$. 

\vspace{0.3cm}
\noindent
\textbf{Subtask 3. Building a ring of samples}
 
\noindent
Subtask 3 builds a ring of samples as described as follows.
First, it builds a ball centered at the \textit{approximated medoid} using \textit{med} as radius (i.e. the ball drawn with dashed line in Figure~\ref{fig:Samples}b). 
Lets consider \textit{m\_sup} and \textit{m\_inf} two other balls that are copies of the first ball, i.e. their radii are initially \textit{med} and their centers are the approximated medoid. 
Then, the subtask decrements the radius \textit{m\_inf} by the value determined by Equation~\ref{eq3}, and increments the radius \textit{m\_sup} by the value determined by Equation~\ref{eq3}.
The two new balls are those drawn with continuous line in Figure~\ref{fig:Samples}b.
The \textit{ring} is the area delimited by these balls.  

In the following, subtask 3 counts the number of elements $l$ contained in the ring.
If $2 \leq l \leq dimensionality~of~S$, these elements are selected as \textit{samples}.
Otherwise, two different situations can occur.
When $l < 2$, \textit{m\_sup} and \textit{m\_inf} are respectively incremented and decremented again by the value determined by Equation~\ref{eq3}, until generating a ring that contains an appropriate number of elements.  
When $l > dimensionality~of~S$, the subtask selects as \textit{samples} the $l$ nearest elements to the \textit{approximated medoid} that are inside the ring, such that $l = dimensionality~of~S$. 

\vspace{0.3cm}
\noindent
\textbf{Subtask 4. Filtering the samples}
 
\noindent
Subtask 4 reduces the number of samples selected in the previous subtask by filtering the samples.
To this end, it removes samples that are too close, i.e. the samples whose distance between them is less than the result provided by Equation \ref{eq3}.
Otherwise, the number of samples to be tested could be very large.

\begin{figure}[h]
\begin{center}
\includegraphics[scale=0.4]{figSampling.png}
\end{center}
\caption{(a) Example of an intersection region. (b) Example of a ring of samples.}
\label{fig:Samples}
\end{figure}


\subsection{Detailing the Algorithm}
\label{sec:algAlturas}

Before performing the tasks described in Figure~\ref{fig:Processo}, the \hbl\ determines the estimated height that a \fonion\ should have, i.e. the height that a balanced \fonion\ should have.  
Equation~\ref{f3} defines this estimated height, using the notion that the total number of elements $n$ that can be stored in a completely full \fonion\ is given by the sum of the number of elements that can be stored at each level $h$ of the index, i.e. $n = \sum_{h=0}^{h=H}2 \times R^{h}$, where $R$ is the number of regions, and \textit{2} represents that there are two pivots per node. 
Equation~\ref{f3} is obtained from this sum, considering that it can be seen as a sum of the $H + 1$ first terms of a geometric progression with ratio \textit{R} and the first term \textit{2}, and isolating \textit{h}. 

\begin{align}
EstimatedHeight = \lceil\log_{R}^{(\frac{n \times \left(R-1\right)}{2}+1)}-1\rceil
\label{f3}
\end{align}

Algorithm 1 details the \hbl.
Its inputs are the elements of the dataset, the estimated height of the \fonion\ calculated using Equation~\ref{f3}, the number F of expansions to be applied to the nodes of the index and a reference to the parent node. 
In the first execution of the algorithm, the reference to the parent node is $null$. 

Initially, the algorithm selects the samples to be analyzed as pairs of pivots (line 2). 
To this end, it performs the four subtasks of the \st\ detailed in Section~\ref{sub:consideracoesSample}. 
Then, the algorithm starts a loop to determine the pair of pivots that should be chosen to create a new node in the index (lines 4 to 15).
In detail, 
in line 6 it selects a pair of pivots from the sample,
in line 7 it associates the remaining elements of the dataset with the regions of the node, 
in line 8 it calculates for each region of the node the height of its subtree, and selects the highest height as the \textit{calculatedHeight}, and
in line 9 it updates the value of \textit{calculatedHeight} so that this value also consider the current level of the index.
Next, if the calculated height is less or equal than estimated height, then the algorithm chooses the pair of pivots of the current node and ends the loop (lines 11 to 14).
The notions of selecting the highest height and increasing it by the current level aim to guarantee that the height of each subtree does not exceed the estimated height of the final \fonion. 
For instance, suppose that $EstimatedHeight = 3$. 
In the first execution of the algorithm, the current level is equal to 0, and the highest height should be at most 3; 
in the second execution of the algorithm, the current level is equal to 1, and the highest height should be at most 2; and so on. 

In the following, the algorithm creates the new node using the selected pivots (line 17).
Furthermore, for each region of the created node, it verifies the number of elements to be associated with this region (line 19). 
If this number is greater than 2, the algorithm is called recursively to that region using as input the elements to be associated with the region, the estimated height calculated before the execution of the algorithm, the number F of expansions and the new node (lines 20 to 22). 
Otherwise the elements of that region are inserted into a new node that is a child of the current node (line 24). 


\begin{algorithm*}[htb]
\begin{small}
\SetKwInOut{Input}{Input}\SetKwInOut{Output}{Output}
\Input{$Elements$ \{elements of the dataset\} 
\\~$EstimatedHeight$ \{height estimated to the F-Onion-tree\}
\\~$Expansions$ \{number of expansions of the F-Onion-tree, i.e. F\}
\\~$ParentNode$ \{reference to the parent node\}}
\Output{$\fonion$ \{the final \fonion\}}
        \hspace{1.0cm}\textbf{// the sampling task}\\		
		$sample$ $\leftarrow$ sampling($Elements$, $sizeSample$);		
		  
		$findPivots$ $\leftarrow$ false;\\
	  \While{existsPivots($sample$) \KwAnd $findPivots$ = false}{
			 \hspace{1.0cm}\textbf{// the selecting pivots task}\\			  		    			 
			 $pivots$ $\leftarrow$ selectPivots($sample$);\\
			 $elementsRegions$ $\leftarrow$ verifyRegions($pivots$, $Elements$ - $pivots$, $Expansions$);\\
			 $calculatedHeight$ $\leftarrow$ estimatesHeight($elementsRegions$, $Expansions$);\\
			  $calculatedHeight$ $\leftarrow$  $calculatedHeight$ + getCurrentLevel();\\
			 \hspace{1.0cm}\textbf{// the evaluating pivots task}\\
			 \If{$calculatedHeight$ $\leq$ $EstimatedHeight$}  {
			 			$findPivots$ $\leftarrow$ true;\\			 						
			 			$selectedPivots$ $\leftarrow$ $pivots$;\\
			 }			 		 
    }			 
    \hspace{1.0cm}\textbf{// the node creation task}\\
    $newNode$ $\leftarrow$ insertNode($selectedPivots$,$ParentNode$);\\
		\For{each $region$ in NumberOfRegions($Expansions$)}{
			 		  $input$ $\leftarrow$ elementsByRegion($elementsRegions$,$region$); \\			 		
			 		  \If{sizeOf($input$) $>$ 2}{
			 		        HeightBL($input$, $EstimatedHeight$, $Expansions$, $newNode$);
			 		  }			 	
			 		  \Else{
			 		  	   insertChildNode($input$, $newNode$, $region$);\\
			 		  }		
		}		
\caption{\texttt{HeightBL} 
}
\end{small}
\label{alg:heightBL}
\end{algorithm*}

The complexity of the \hbl\ is determined as follows. 
Consider $n$ the number of elements of the dataset, and $m$ the number of samples generated from the \st. 
The complexity of the \st\ is $O(n*log(n))$, since the distances between the elements are sorted to generate the median, and the complexity of the loop between the tasks of \textit{selecting pivots} and \textit{evaluating pivots} is $m^2$.
Also, the complexity of the \textit{node creation} task is $O(1)$.
As $m$ is much smaller than $n$, the complexity of the \hbl\ is $O(n*log(n))$.


