\section{Related Work}
\label{sec:RelatedWork}

The first dynamic disk-based MAM is the M-tree~\cite{CiacciaPZ97}. 
Its leaf nodes store all the elements of the dataset, while its internal nodes store selected elements called representatives, each having a covering radius. 
The \bl\ algorithm for the M-tree described in \cite{Ciaccia98bulkloading} randomly chooses \textit{k} elements from the dataset as samples and assigns the remaining elements to the nearest sample, thus producing \textit{k} groups. 
The algorithm is recursively applied to each group until the subset is small enough to fit in one node. 
The \bl\ algorithm for the M-tree introduced in \cite{SextonSwinbank2004} clusters the input data so that the generated M-tree reflects the performance requirements of the structure.
Further, the Slim-tree~\cite{TrainaTFS02} was the first disk-based MAM explicitly designed to reduce the overlap degree between nodes in a metric tree. 
Its \bl\ algorithm~\cite{VespaTT07,Vespa09} builds the structure in a top-down fashion, based on sampling techniques, and creates balanced trees with little overlap in each node, using the metric domain's distance function and a bound limit to group and determine the number of elements in each partition of the dataset at each step of the algorithm. 
As the M-tree and the Slim-tree are disk-based MAMs, their \bl\ algorithms are designed to reduce the overlap between the nodes, which is a problem that is not faced by the main-memory \fonion. 

Bercken and Seeger (2001)~\nocite{BerckenEvaluation} introduce two generic \bl\ algorithms, in the sense that they can be applied to access methods based on trees, including MAMs.
The basic idea behind these algorithms is to recursively partition the dataset by using a main-memory index of the same type as the target index to be built.
In these algorithms, elements (i.e., samples) of the dataset are inserted into the index maintained in the main memory until the available memory is filled up. 
Then, a bucket on disk is associated with each leaf node, and the remaining elements of the dataset are inserted into the index guided to the buckets of the corresponding leaf node. 
When all the elements have been processed, the nodes in the main memory are written to disk.  
These algorithms can not be applied to \bl\ \fonions\ because they are based on the premise that the amount of data to be inserted in the index does not fit entirely in the main memory and therefore the index should be stored on disk. 
Also, these algorithms do not explore the characteristics of the \onion, such as its partitioning method. 

In addition to the aforementioned related work, it is also important to survey proposals for \bl\ multidimensional access methods, especially the R-tree.
The TGS algorithm~\cite{GarciaTGS} partitions the input data into subtrees in a top-down fashion, and at each level of the tree, it rearranges the input data that should be positioned under a node in construction according to a cost function. 
The OMT algorithm~\cite{LeeL03OMT} first determines the topology of the resulting R-tree and then groups the input data to create the entries of the root node, aiming to minimize the overlapped area. 
The remaining nodes are  constructed by recursively partitioning each entry to create lower level nodes. 
The algorithm described in \cite{ArgeBLRtree} is based on a buffering technique that attaches buffers to the nodes of the R-tree.
An operation is first guided to the buffers of each node and, when any buffer is full, the operation is performed in the index.
Finally, Bercken et al. (1997) \nocite{BerckenGeneric} describe an algorithm based on the buffering technique to perform the \bl\ of multidimensional structures, which is based on the use of the split and the merge operations of the index to which the \bl\  is being applied. 
Although these related work are used as a basis for the proposal of several \bl\ techniques, they can not be directly applied to \bl\ \fonions\ as they are based on the characteristics of multidimensional access methods, such as the use of specific partitioning methods, the use of approximations such as the minimum bound rectangle (MBR) and the sort of MBRs to reduce their size and area of overlap. 

To generate more compact indices and to provide better query performance than the \ee, \bl\ algorithms should take advantage of the particular characteristics of the index structure.  
In this article, we use the well-known concept of \textit{sampling} as a basis of our \bl\ algorithm, but we apply new ideas to it, which respect the characteristics of the \fonion.
First, the proposed \hbl\ chooses samples in a subspace of the metric space by avoiding pair of pivots whose distance is too far or too close. 
Second, it selects two pivots per node according to their distribution in the metric space, differently from the algorithms described in \cite{Ciaccia98bulkloading,Vespa09}, which randomly select only one pivot per node after clustering the remaining elements.  
Third, the \hbl\ defines a strategy to estimate the ideal height that a \fonion\ should have in order to generate a better index structure.
