\section{Introduction}
\label{sec:Introduction}

A metric access method (MAM) aims to provide efficient access to a large number of applications that require comparison between complex data, such as images, audio and video. 
To improve the access to complex data, MAMs reduce the search space, leading the search to portions of the dataset where the stored elements probably have higher similarity with the searched element.
The similarity measure between two elements can be expressed by a metric that becomes smaller as the elements become more similar \cite{HjaltasonS03}. 
As MAMs partition the metric space into subspaces, queries do not have to access the complete dataset.

Formally, a metric space is an ordered pair 
\mbox{$<{S}, d>$}, such that 
\mbox{${S}$}
is the domain of data elements and 
\mbox{${d}$}: \mbox{${S}$} \begin{math}\times\end{math} \mbox{${S}$} \begin{math}\rightarrow\end{math} \mbox{${R}^+$}
is the metric. 
For any 
\mbox{$s_1, s_2, s_3 \in {S}$}, the metric must have the following properties: (i)  identity: 
\mbox{$d(s_1,s_1)=0$}; 
(ii) symmetry:  
\mbox{$d(s_1,s_2)=d(s_2,s_1)$}; 
(iii)  non-negativity: 
\mbox{$d(s_1,s_2) \geq 0$}; 
and (iv) triangular inequality: 
\mbox{$d(s_1,s_2) \leq d(s_1,s_3) + d(s_3,s_2)$}~\cite{ChavezNBM01}.
Providing a metric to enable handling complex data as a metric space helps reducing the problems derived from the curse of dimensionality, because MAMs tend to follow the dimensionality of the element represented by the data (the so-called intrinsic dimensionality) instead of the dimensionality of the space where the element is embedded (the embedded dimensionality)~\cite{TrainaJr2010b,PolaTT2009}. 
In addition to the fact that the intrinsic dimensionality is usually lower than the embedded one~\cite{KornPF2001}, many complex data do not have a defined dimensionality. 
Thus, handling datasets of low intrinsic-dimensionalities using MAMs is an interesting way to speed up similarity queries. 

The two most useful types of similarity queries using MAMs are the range query and the \knn\ query.
Consider a query element s\begin{math}_q\end{math} \begin{math}\in\end{math}  \mbox{${S}$}.
Given a query radius $r_q$, the range query returns each element $s_i\in S$ that satisfies the condition $d(s_i,s_q) \leq r_q$. 
On the other hand, given a value $k \geq 1$, the \knn\ query returns the $k$ elements in $S$ that are  the nearest from the query element $s_q$.

The work on MAMs is quite extensive.
An important research challenge involved is the development of main-memory MAMs, which is motivated by several factors.
Due to hardware advances, the storage capacity of the main memory is increasingly growing, at the same time that its costs are lowering.    
Another motivation is related to the fact that main-memory MAMs are able to process similarity queries very fast, as they do not need to minimize disk accesses as disk-based MAMs do and, therefore, can provide a better partitioning of the metric space. 
Furthermore, main-memory MAMs are very useful to optimize subqueries when processing complex queries. 
In this scenario, the query optimizer of database management systems can generate a main-memory MAM on runtime to process more efficiently parts of a query or the whole query.
In this article, we address main-memory MAMs.

There are few main-memory MAMs that have been proposed in the literature, such as the GH-tree~\cite{Uhlmann91}, the GNAT~\cite{Brin95}, the VP-tree~\cite{Yianilos93} and its extensions~\cite{BozkayaOzsoyoglu1997,BozkayaOzsoyoglu1999,FuCCM2000}, the MM-tree~\cite{PolaTT07} and the \onion~\cite{CareloEtAl2011}. 
To the best of our knowledge, the \onion\ is the most efficient main-memory MAM to date~\cite{CareloEtAl2011}. 
Thus, we focus our work on the \onion.

The main characteristics of the \onion\ are summarized as follows.
It has a partitioning method that indexes complex data by dividing the metric space into several disjoint subspaces by using two pivots per node. 
It replaces the pivots of a leaf node during insertion operations by using a replacement policy that ensures good partitioning of the metric space.
Also, its algorithms for processing similarity queries can efficiently use its partitioning method.
The \onion\ has two versions: (i) the \fonion, which divides each node of the structure into the same number of subspaces; and (ii) the \vonion, which applies different numbers of subspaces to the nodes.   
Here, we are interested in the \fonion, which according to Car\'{e}lo et al. (2011)\nocite{CareloEtAl2011}, invariably outperformed the \vonion. 

However, the \fonion\ only performs \ee\ into its structure.
Another important issue is the mass loading technique, called \bl, which builds the index considering all elements of the dataset at once. 
This technique is useful in the case of reconstructing the index or inserting a large number of elements simultaneously. 
It is also very useful for the query optimizer of database management systems due to the following factors. 
As the entire input dataset is already known, it is expected that the \bl\ generate more compact structures, thus decreasing the memory space required to store the index. 
It is also expected that the index generated by the \bl\ provide better performance in the processing of range and \knn\ queries, which can be repeated several times after the index is created.
Despite the importance of the \bl\ technique, to the best of our knowledge, there are not in the literature \bl\ algorithms for the \fonion.

In this article, we fill this gap. 
We propose the \hbl\ for bulk-loading \fonions.
The proposed algorithm calculates a priori the estimated height of the index, according to the number of elements to be inserted into the structure and the quantity of subspaces of the \fonion. 
It selects, for each node, the pair of elements of the dataset that will generate a structure with approximately the estimated height. 
Also, to avoid the need to verify each pair of elements, the algorithm chooses samples to be tested.
By combining these characteristics, the proposed \hbl\ fulfills the requirements of the \bl\ technique:
compared with the element-by-element insertion, performance tests showed that the \hbl\ produced more compact indices and guaranteed expressive performance gain in range and \knn\ query processing. 

This article is organized as follows. 
Section \ref{sec:RelatedWork} reviews related work, 
Section \ref{sec:Theoretical} details the main  characteristics of the \fonion,
Section \ref{sec:heightBLalgorithm} introduces the proposed bulk-loading algorithm,
Section \ref{sec:experiments} validates the algorithm through performance tests,
and Section \ref{sec:Conclusions} concludes the article.

