\section{The \fonion}
\label{sec:Theoretical}

The \fonion~\cite{CareloEtAl2011} is a main-memory MAM that divides the metric space into disjoint subspaces (i.e. regions) by selecting two pivots per node.
Its partitioning method is based on the concept of \textit{expansion}, which determines the number of \textit{disjoint regions} that the nodes of a \fonion\ should have.
In detail, the number of expansions is equal to $F$, the number $R$ of disjoint regions is determined by  $R = F * 3 + 4$, and all nodes of a given \fonion\ have the same number of disjoint regions.

Figure~\ref{figExpansionOnion}c depicts a node of a F-Onion-tree ($F = 2$) indexing the set $S = {s_1, s_2, ..., s_n}$, using ${s_1, s_2}$ as pivots.
It is composed of ten disjoint regions, which are generated by the partitioning method as detailed as follows: 
(i) expansion 0 (Figure~\ref{figExpansionOnion}a) represents the initial structure of a node with four regions I, II, III and IV;
(ii) expansion 1 (Figure~\ref{figExpansionOnion}b) generates the node with seven regions I, II, III, IV', V', VI' and VII'; and
(iii) expansion 2 (Figure~\ref{figExpansionOnion}c) generates the node with ten regions I, II, III, IV', V', VI', VII'', VIII'', IX'' and X''.
The distance $r = d(s_1, s_2)$ between the pivots defines the initial radius of the ball centered at each pivot. The other radii are determined using the multiplicity of $r$,~i.e. 
$2r$ for expansion 1 and $3r$ for expansion 2.  
Each expansion adds three regions to the node, since the previous external region becomes the first region of the expansion.

\begin{figure}[htb]
\begin{center}
\includegraphics[scale=0.55]{figExpansion.png}
\end{center}
\caption{Generation of a F-\onion's node with 2 expansions, adapted from Car\'{e}lo et al. (2011)}
\label{figExpansionOnion}
\end{figure}

Let $s_i$ be an element of $S$ to be inserted into the index.
The \ee\ performs as follows.
During the insertion of $s_i$, the index is traversed to search for an appropriate node to hold the element.
At each node, the insertion calculates two distances: $d_1$, which is the distance between $s_i$ and the first pivot of the node, and $d_2$, which is the distance between $s_i$ and the second pivot of the node.
The region to hold $s_i$ is determined according to the following rules:
(i) if $d_1 < r$ and $d_2 < r$, then $s_i$ is associated with region I;
(ii) if $d_1 < r$ and $d_2 > r$, then $s_i$ is associated with region II;
(iii) if $d_1 > r$ and $d_2 < r$, then $s_i$ is associated with region III; and
(iv) if $d_1 > r$ and $d_2 > r$, then $s_i$ is associated with the external region of the \fonion, which can be region IV or any other region generated by the expansions.
If $s_i$ is associated with an external region of a current expansion \textit{E} ($0 \leq E < F$), the previous rules are applied considering the multiplicity of the initial radius $r$ according to the value of the next expansion \textit{E + 1}. 
Also, if $s_i$ should be inserted into a region that already has two pivots, the \ee\ is called recursively to insert this element as a child of the region pivots.

The new element $s_i$ is assigned to a leaf node when an empty leaf node is reached or when a leaf node with only one element is reached.
Also,  the \fonion\ may replace one of the pivots of a full leaf node just before inserting $s_i$ into this node. 
This is based on a replacement policy that performs a combinatorial analysis between the distances of $s_i$ and the two pivots, and changes any of the pivots with $s_i$ if needed.  
It also updates the radius of the node with the distance between $s_i$ and the non-chosen pivot. 
The \onion\ may use three different replacement policies: (i) the keep-small, which states that the distance between the pivots should be the closest to half of the parent node's radius; (ii) the maximize-expansions, which chooses as pivots the elements that are the closest; and (iii) the minimize-expansions policy, which chooses as pivots the elements that are the most distant.  
Here, we are interested in the keep-small replacement policy, which according to Car\'{e}lo et al. (2011)\nocite{CareloEtAl2011}, invariably outperformed the other replacement policies.

Figure~\ref{figBrazilianCities} graphically illustrates a F-Onion-tree for a real-world dataset that contains the geographical coordinates of Brazilian cities (\url{www.ibge.gov.br}). 
We used the tool introduced in~\cite{TrainaTFS02} to show a visualization of the level 4 of the structure using the keep-small replacement policy.
We applied only one expansion to the F-\onion's nodes.
Thus, it is possible to easily see regions I, II, III, IV', V', VI' and VII' of some nodes.

\begin{figure}[htb]
\begin{center}
\includegraphics[scale=0.20]{figBrazilianCities.png}
\end{center}
\caption{Visualization of the level 4 of a F-\onion\ with 1 expansion.}
\label{figBrazilianCities}
\end{figure} 

Regarding the range query algorithm, for each pivot of a node, it first analyses if the distance between the query element $s_q$ and the pivot is smaller than the query radius $r_q$. 
If this comparison returns true, then the pivot is added to the output set. 
Next, for each region of the node, the algorithm is called recursively if this region is covered by $r_q$. 
On the other hand, the \knn\ query algorithm starts calculating the distances between $s_q$ and the pivots of the node. 
An active radius is maintained with its value equals to the distance of the farthest element of the result set from the moment that the algorithm finds $k$ elements.
If the distance between $s_q$ and any of the pivots is smaller than the active radius, the corresponding pivot is added to the result set, keeping it sorted by the distances.
Next, the algorithm is called recursively for each region that intersects the active radius.
The \knn\ query algorithm visits expansions and regions as follows. 
First, it visits the expansion \textit{E} in which $s_q$ is assigned. 
The first region of \textit{E} to be visited is where $s_q$ lies.
The remaining regions are visited according to their proximity to $s_q$, such that the closest regions to $s_q$ are visited before the farthest regions.
Then, the \knn\ query algorithm visits expansions \textit{E - 1} and \textit{E + 1}, and for each expansion, applies the same visit order for their regions.
The algorithm performs recursively for the remaining expansions until $k$ elements be recovered.




