% by Mirella M. Moro; version: January/18/2012 @ 04:16pm
% -- 01/18/2012: more discussion on SBBD + JIDM; overall revision
% -- 09/03/2010: bib file with names for proceedings and journals; cls with shrinked {received}
% -- 08/27/2010: appendix, table example, more explanation within comments, editors' data
%
%

\documentclass[jidm,a4paper]{jidm} % NOTE: JIDM is published on A4 paper
\usepackage{graphicx,url}  % for using figures and url format
\usepackage[T1]{fontenc}   % avoids warnings such as "LaTeX Font Warning: Font shape 'OMS/cmtt/m/n' undefined"

%\usepackage{cite} % NOTE: do **not** include this package because it conflicts with jidm.bst

\usepackage{inputenc}
\usepackage[tight]{subfigure}
\usepackage{tikz}
\usepackage{pgfplots}
\pgfplotsset{compat=1.8}
\usepackage{float} 
\usepackage[mathcal]{euscript}
\usepackage{algorithm}    
\usepackage{algpseudocode} 
\usepackage{amsmath}

% Standard definitions
\newtheorem{theorem}{Theorem}[section]
\newtheorem{conjecture}[theorem]{Conjecture}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{lemma}[theorem]{Lemma}
\newdef{definition}[theorem]{Definition}
\newdef{remark}[theorem]{Remark}

% New environment definition
\newenvironment{latexcode}
{\ttfamily\vspace{0.1in}\setlength{\parindent}{18pt}}
{\vspace{0.1in}}

\newcommand{\ie}{\emph{i.e.}}

% ALL FIELDS UNTIL BEGIN{document} ARE MANDATORY

% The following data (volume, number and page) are given by the editors prior to publishing your article
\jidmVolume{5}
 \jidmNumber{2}
 \jidmYear{14}
 \jidmMonth{June}
\setcounter{page}{1}


% Includes headers with simplified name of the authors and article title
\markboth{Ricardo C. Sperandio et al.}
{Exploring Strategies for Minimizing Overlap Between Nodes in a Multimodal Metric Tree}
%  -> \markboth{}{}
%         takes 2 arguments
%         ex: \markboth{M. M. Moro}{Any article title}


% Title of the article
\title{Exploring Strategies for Minimizing Overlap \\ Between Nodes in a Multimodal Metric Tree}


% List of authors
%IF THERE ARE TWO or more institutions, please use:
%\author{Name of Author1\inst{1}, Name of Author2\inst{2}, Name of Author3\inst{2}}
\author{Ricardo C. Sperandio, Zenilton K.G. Patroc\'{\i}nio Jr., Hugo B. de Paula, Silvio J.F. Guimar\~{a}es}


%Affiliation and email
\institute{Pontif\' {\i}cia Universidade Cat\' {o}lica de Minas Gerais -- PUC Minas, Brazil \\ \email{rcarlini@gmail.com, \{zenilton, hugo, sjamil\}@pucminas.br}
%\and Universidade Federal Fluminense \\ \email{vanessa@ic.uff.br}
% IF THERE IS ANOTHER INSTITUTION:
%\and Name_of_the_second_institution \\
%\email{address@whatever.com}
}


% Article abstract - it should be from 100 to 300 words
\begin{abstract}
\emph{Slim\textsuperscript{2}-tree} is a multimodal metric tree which enables video indexing and retrieval by using information from multiple modalities. Experimental results have demonstrated its efficiency when compared to other multimodal solutions. This article explores different strategies related to the use of a \emph{post-processing} algorithm for the \emph{Slim\textsuperscript{2}-tree} -- named multimodal \emph{Slim-down}, which tries to minimize the overlap between tree nodes. Experiments have also shown the performance improvement obtained by the policy, in which any element that presents the larger distance value to the pivot for any modality is selected as candidate to be moved. Moreover the results are better when that policy is repeatedly used during insertion.
\end{abstract}


% ACM Computing Classification System categories
\category{H.2.4}{Database Management}{Systems}[Multimedia databases]
\category{H.3.1}{Information Storage and Retrieval}{Content Analysis and Indexing}[Indexing methods]
\category{H.3.3}{Information Storage and Retrieval}{Information Search and Retrieval}[Retrieval models and Search process]
%\category{H.2}{Database Management}{Miscellaneous} 
%\category{H.3}{Information Storage and Retrieval}{Miscellaneous}
%\category{I.7}{Document and Text Processing}{Miscellaneous}

% Categories and Descriptors are available at the 1998 ACM Computing Classification System
% http://www.acm.org/about/class/1998/
%  -> \category{}{}{}
%         takes 3 arguments for the Computing Reviews Classification Scheme.
%         ex: \category{D.3.3}{Programming Languages}{Language Constructs and Features}
%                   [data types and structures]
%                   the last argument, in square brackets, is optional.

% Article keywords
\keywords{content based video retrieval, metric access methods, multimedia database, multimodal video retrieval}
%\keywords{JIDM, SBBD, template}
%  -> \keywords{} (in alphabetical order \keywords{document processing, sequences,
%                      string searching, subsequences, substrings})


% THE ARTICLE BEGINS
\begin{document}

% This is optional:
\begin{bottomstuff}
The authors are grateful to PUC Minas, CNPq, CAPES and FAPEMIG for the financial support of this work.
%The authors also thank to the anonymous reviewers for their valuable comments and suggestions.
% similar to \thanks
% for authors' addresses; research/grant statements
\end{bottomstuff}

\maketitle
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%INICIO DO TEXTO
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\section{Introduction}

Video is an effective medium for storing information about events of the real world, and a vast amount of video materials exists, covering a wide range of applications. However, widespread use of video in computer applications is often prohibited by the lack of effective tools to store, index and recover this type of media. 
To avoid misunderstanding, in this article a digital video encompasses information from different data sources, such as visual and acoustic data.
The trivial way to implement video query systems is through the use of previously registered annotations for each video in the database. 

This approach may be inadequate for large databases of videos, since it involves great human effort in generating annotations~\cite{Shao2008}. Furthermore, ambiguous or incomplete descriptions can negatively impact search results. Therefore, the use of the video content for indexing and retrieval may provide an alternative approach, which gives rise to content-based video retrieval systems (\textit{Content-Based Video Retrieval} -- CBVR). In this scenario, similarity search is the fundamental tool for those systems, and there were several studies in the last two decades about this topic~\cite{AlmeidaVTL10}. However, similarity search for digital videos has been generally focused solely on the use of visual data, completely neglecting another important source of video information -- the acoustic track.

This article is an enhanced version of a previous work~\cite{DBLP:conf/webmedia/SperandioPPG13} that proposes a new
multimodal metric tree -- \emph{Slim\textsuperscript{2}-tree} -- which enables video indexing and retrieval by using information from multiple modalities. Experimental results have shown its efficiency when compared to other multimodal solutions. It is worth mentioning that tests results have also shown that \emph{Slim\textsuperscript{2}-tree} supports queries using only one modality with a computational cost similar to a unimodal solution. This is an important property of \emph{Slim\textsuperscript{2}-tree}, since it can be used instead of several others. 

This article has the following improvements on top of the previous work: (i) the text have been reviewed and only the major issues related to the creation and use of \emph{Slim\textsuperscript{2}-tree} remain; (ii) the dataset is better described and some frame samples are presented; (iii) a detailed description of a multimodal \emph{post-processing} algorithm -- named multimodal \emph{Slim-down} -- is given; and (iv) different strategies related to the use of multimodal \emph{Slim-down} (\ie, policies for choosing elements to be moved and the context for its application) are fully described and evaluated. Experiments have also shown that multimodal \emph{Slim-down} can improve the test results, specially when the candidate to be moved defines at least one of the radii of the hyperregion associated with the tree node.

The remainder of this article is organized as follows. Section~\ref{sec:related} covers the main concepts and related works. The new multimodal metric index structure -- \emph{Slim\textsuperscript{2}-tree} -- is briefly reviewed in Section~\ref{sec:slim2}. Section~\ref{sec:slimdown} gives a detail description of the multimodal \emph{Slim-down}  along with different strategies for its use. In Section~\ref{sec:experiment}, experimental results are shown and analyzed. Finally, Section~\ref{sec:conclusion} draws some conclusions and proposes future directions for research.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\section{Related work}\label{sec:related}

The support to multimodal queries -- the ones that involve data from different nature, such as visual and acoustic -- is extremely valuable for CBVR. For example, queries such as ``\emph{find news videos in which president Dilma Rousseff talks about 2014 FIFA World Cup}'' require more than one modality to be answered adequately.
According to~\cite{Atrey2010,Yan2007}, the combination of multiple modalities may consistently improve, in terms of precision, the obtained results when compared to the use of each modality separately. However, the use of multiple modalities involves the adoption of a fusion strategy. 
In~\cite{Atrey2010}, different fusion techniques are described and analyzed, specially \emph{early fusion} techniques, in which several features extracted from the data are combined before their effective use; and \emph{late fusion} techniques, in which features are processed separately and their results are combined later. 

The need of indexing and retrieval of more complex types of data, such as images, sounds, videos, and others, 
initiated a series of studies, since these types of data are not totally ordered. Techniques, such as \emph{R-tree} and \emph{KD-tree}, among others, are based on vector space~\cite{Gaede:1998:MAM:280277.280279} and represent data as points in the space in order to group and organize the information that they represent.
However, for CBVR the huge number of dimensions generates a performance problem known as \emph{``the curse of dimensionality''}~\cite{Chavez:2001:SMS:502807.502808}. For this scenario, metric access methods were developed to support similarity queries based on a distance function used to measure the (dis)similarity between data. 
These methods are based on the following approach: partitioning the set of objects using a distance function and choosing one of them as the representative (pivot) of the entire set. During the search, the representatives are used to reduce the search space using the \textit{triangular inequality} -- which allows the computation of lower and upper bounds for the distances between the query object and every element of a set based on the distance between the query object and the set pivot.

The first metric access methods proposed in the literature, such as \emph{VP-tree} and \emph{FQ-tree}, 
were static, and they did not support neither insertions nor removals after their creation. 
The first dynamic metric access method was \emph{M-tree}~\cite{Patella1997}. It is a balanced tree, in which data are stored in the leaves and internal nodes have pointers to direct the search to the correct leaf.
This paradigm has become very popular, and many access methods extending the original \emph{M-tree} have been proposed. 
In relation to this work, two extensions should be mentioned: \emph{Slim-tree} and \emph{M\textsuperscript{2}-tree}.

The first one -- \emph{Slim-tree} -- tries to minimize the overlapping between regions~\cite{Traina00slim-trees:high}. Similar to \emph{M-tree}, the space is divided in regions (represented by subtrees) that are not disjoint. Each one of those regions is defined by one representative object ($O_r$) -- used as reference to the others in that subtree, and by a covering radius which should be large enough to cover all elements stored in that subtree. This allows the search algorithms to ignore entire tree branches using the \textit{triangular inequality}.
Beyond that, \emph{Slim-tree} tries to minimize the overlapping between regions by applying a heuristic called \emph{Slim-down} which moves objects between leaf nodes in order to reduce the covering radius of those nodes. During insertion, 
\emph{Slim-tree} has also proposed a heuristic based on minimal occupancy (\texttt{MinOccup}) --  which is responsible for balancing the objects distribution among subtrees, and the use of \textit{Minimum Spanning Tree} (MST) for node splitting and pivot selection.

Another important extension of \emph{M-tree} is \emph{M\textsuperscript{2}-tree} which was proposed to support complex queries between objects represented by multiple feature descriptors~\cite{Ciaccia2000}. This approach combines in a single structure all descriptors related to different metric spaces, allowing the use of distinct distance functions for each feature.  
Besides, \emph{M\textsuperscript{2}-tree} adopts a monotonic increasing \emph{score} function to combine the distances of each distinct feature in a single value (\emph{early fusion}) which is used during insertion and search. Unfortunately, the authors only provide a very brief description of it, \ie, they claim that \emph{M\textsuperscript{2}-tree} works in a very similar way to \emph{M-tree} -- using the same policies and heuristics -- except for the adoption of a \emph{score} function to implement the \emph{early fusion}.

Other structures for multiple features have also been proposed in the literature. In the \emph{MOSAIC-tree}~\cite{Goh2000219}, each feature is stored in a distinct layer using \emph{R-trees}. The leaf nodes from a superior layer are connected to the root of the associated tree in the layer below. But the use of multidimensional trees only allows its application with low dimensional feature descriptors due to ``\textit{the curse of dimensionality}''.
The \emph{MFI-tree}~\cite{HeY10} adopts a single distance value calculated by a linear combination of the several distances which is used to index the object. The major issue is how to determine the weights for that linear combination in a scalable and data-independent approach, but the authors left that problem for a future work. 
More recently, the \emph{TEMPOM\textsuperscript{2}-tree}~\cite{Doller12} proposes the use of two data structures in parallel, one is a \emph{M\textsuperscript{2}-tree} for content-based video indexing and another for representing the video temporal structure. Finally, the \emph{M\textsuperscript{3}-tree}~\cite{Bustos:2012:AMI:2317099.2317138} allows searches through a dynamic combination of distinct metrics (defined by the user when a query is executed), instead of using a fixed combination such as \emph{MFI-tree}. 

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\section{Slim\textsuperscript{2}-tree}\label{sec:slim2}

An efficient access method for multimodal and unimodal video retrieval, named \emph{Slim\textsuperscript{2}-tree}, was proposed in~\cite{DBLP:conf/webmedia/SperandioPPG13}. Here we briefly review the major issues related to its creation and use for performing similarity queries.

\emph{Slim\textsuperscript{2}-tree} supports the use of features from distinct domains (or modalities) in a single index structure and it adopts a monotonic increasing \emph{score} function for dealing with fusion (\emph{early fusion}) -- similar to \emph{M\textsuperscript{2}-tree}, but one should notice that \emph{M\textsuperscript{2}-tree} only supports multimodal queries. Since \emph{Slim\textsuperscript{2}-tree} borrows (and adapts to the ``\textit{multimodal world}'') some of the node management policies used during insertion from the \emph{Slim-tree}, it is named after it (although it is good to remember that a single \emph{Slim-tree} can not easily handle multimodal queries by itself). 

\begin{table}[!b]
\caption{Structure of an entry belonging to a leaf node.}
\label{tab:estrutura-folha}
\sffamily % CHANGES THE FONT WITHIN THE TABLE TO sans serif
\centering
\begin{tabular}[]{c|l}
\hline
\hline
\textbf{Symbol} & \multicolumn{1}{c}{\textbf{Definition}}\\
\hline
$O_j.F_i$ & Feature value for object $O_j$ in domain (or modality) $\mathcal{D}_i$. \\
%
$oid(O_j)$ & Object identifier $O_j$.\\
%
$d_i(O_j,P(O_j))$ & Distance, in domain $\mathcal{D}_i$, from object $O_j$ to its pivot.\\
\hline
\hline
\end{tabular}
\rmfamily % RESTORES TO TIMES, SO THAT CAPTION IS WRITTEN PROPERLY
\end{table}

Unimodal data structures, such as \emph{M-tree} and \emph{Slim-tree}, are capable of indexing objects from a single metric space $\mathcal{M} = (\mathcal{D},d)$ -- in which $\mathcal{D}$ represents the data domain and $d$ is a (metric) distance function used to assess the (dis)similarity between objects. \emph{Slim\textsuperscript{2}-tree} 
allows indexing of objects represented by a collection of metric spaces $\mathcal{M}^n = \{(\mathcal{D}_i,d_i),\forall i=1,\ldots,n\}$, in a way that each pair $(\mathcal{D}_i, d_i)$ is associated with a different modality.
Since \emph{Slim\textsuperscript{2}-tree} nodes represent hyperregions of that collection of metric spaces, it is possible to use triangular inequality for search and insertion operations.
Thus, there are $n$ distinct domains $\mathcal{D}_i$, one for each modality, adopting a particular (and, perhaps, distinct) distance function $d_i$ defining a hyperregion that is associated to each \emph{Slim\textsuperscript{2}-tree} node. Therefore, the hyperregion associated with a tree node is defined by all those $n$ distance functions, and it is not just a simple hypersphere (as in \emph{Slim-tree}) but it represents the data space in a more complex way.
Thus, when $n$ features $F_1,\ldots,F_n$ are considered along with their distance functions $d_1,\ldots,d_n$ and a representative object $O_r = (O_r.F_1,\ldots,O_r.F_n) \in \mathcal{D}_1 \times \ldots \times \mathcal{D}_n$, the hyperregion associated to $O_r$ in the collection of metric spaces $\mathcal{M}^n$ can be seen as the non negative orthant of the $n$ domain space. %, as illustrated in Fig.~\ref{fig:regiaonos2}.

In a leaf node, an entry for each object $O_j$ is used to store the object identifier $oid(O_j)$, the values for its $n$ features $F_i~  \forall i=1,\ldots,n$,  along with $n$ distance values $d_i(O_j,P(O_j))$ between $O_j$ and its parent (or pivot) $P(O_j)$, \ie, the routing object $O_r$ which is stored in the node $N^p$ (from a level immediately above the leaf node) and which is used to make a reference to node $N$ (where object $O_j$ is stored). Table~\ref{tab:estrutura-folha} presents the structure of an entry belonging to a leaf node. Thus, a leaf node entry should be defined as follows:
\[
entry(O_j) =  \langle  oid(O_j), 
     array\_of\langle O_j.F_i, d_i(O_j,P(O_j)) ~\forall i=1,\ldots,n \rangle \rangle\mbox{.}
\]

On the other hand, in an internal node, each entry for a routing object (or pivot) $O_r$ is used to store: a pointer $ptr(T(O_r))$ to the root of subtree $T(O_r)$ covered by (related to) the routing object $O_r$; the number of objects stored in the subtree $T(O_r)$; the $n$ values for the features $F_i$ assigned to the routing object $O_r$ during promotion, along with $n$ values for covering radii $r_i(O_r) > 0$ and $n$ distance values $d_i(O_r,P(O_r))$ between $O_r$ and its parent $P(O_r)$ which is stored in a higher level of the tree (except for the tree root). Table~\ref{tab:estrutura-interno} presents the structure of an entry belonging to an internal node. Therefore, an internal node entry should be defined as follows:
\[
entry(O_r) = \langle ne, ptr(T(O_r)), 
array\_of\langle O_r.F_i, d_i(O_r,P(O_r)), r_i(O_r)~\forall i=1\ldots n 
\rangle \rangle\mbox{.}
\]

\begin{table}[!t]
\caption{Structure of an entry belonging to an internal node.}
\label{tab:estrutura-interno}
\sffamily % CHANGES THE FONT WITHIN THE TABLE TO sans serif
\centering
\begin{tabular}[]{c|p{8cm}}
\hline
\hline
\textbf{Symbol} & \multicolumn{1}{c}{\textbf{Definition}}\\
\hline
$O_r.F_i$ & Feature value for representative $O_r$ in domain (or modality) $\mathcal{D}_i$. \\
%
$ne$ & Number of entries stored in subtree $T(O_r)$.\\
%
$ptr(T(O_r))$ & Pointer to the root of subtree $T(O_r)$.\\
%
$r_i(O_r)$ & Covering radius associated to object $O_r$ in domain $\mathcal{D}_i$. \\
%
$d_i(O_r,P(O_r))$ & Distance, in domain $\mathcal{D}_i$, from object $O_r$ to its pivot.\\
\hline
\hline
\end{tabular}
\rmfamily % RESTORES TO TIMES, SO THAT CAPTION IS WRITTEN PROPERLY
\end{table}

The creation and use of \emph{Slim\textsuperscript{2}-tree} for performing similarity queries are delineated in the following. 
In~\cite{Sperandio2014}, all algorithms for creating and searching are fully described.

\subsection{Construction of a \emph{Slim\textsuperscript{2}-tree}}\label{sec:slim2:construcao}

The building algorithms for \emph{Slim\textsuperscript{2}-tree} specify how objects are inserted in the tree structure as well as how node overflows are treated.
First, \emph{Slim\textsuperscript{2}-tree} building parameters should be set: the number of modalities -- $n$; the domain of each modality with its distance function, \ie, $\mathcal{M}^i = (\mathcal{D}_i,d_i), \forall i=1,\ldots,n$; the \emph{score} function $S_f$ to be used in \textit{early fusion} strategy; and the maximum number of objects per node -- $m$. As shown in~\cite{Ciaccia2000}, any monotonic increasing function combining the distances of all modalities could be used as \emph{score} function, such as $\max\{d_i,\forall i=1,\ldots,n\}$, or $\sum_{i=1,\ldots,n}{\theta_i d_i}$, with $\theta_i \geq 0, \forall i=1,\ldots,n$ and $\sum_{i=1,\ldots,n} \theta_i = 1$.

During the \texttt{insertion} of a new object, the procedure recursively descends the \emph{Slim\textsuperscript{2}-tree} trying to locate the most suitable leaf node for accommodating the new object $O_n$. This could possibly trigger a node split if the selected leaf is full.
The principle used to select the most suitable leaf node to insert the new object is to locate a subtree $T(O_r)$  which does not need an enlargement of its covering radii, \ie, $d_i(O_r,O_n) \leq r_i(O_r), \forall i \in 1,\ldots,n$. 
If multiple subtrees are qualified, the choice is made using one of the following heuristics (which are similar to the ones of \emph{Slim-tree}):
(i) \texttt{Random}: choose a subtree randomly; 
(ii) \texttt{MinDist}: choose the subtree whose pivot is closer to the new object; and 
(iii) \texttt{MinOccup}: choose the subtree which contains the smallest number of objects.
In this article, the choice of the subtree where the new object is inserted is made by \texttt{MinOccup} since the authors in~\cite{Traina00slim-trees:high} have demonstrated its efficiency for \emph{Slim-tree}.

The search for routing objects which do not need an enlargement in their covering radii is optimized though the use of \textit{triangular inequality}, reducing the computational cost since many distance calculations are avoided.
If there is no routing object satisfying $d_i(O_r,O_n) \leq  r_i(O_r),\forall i \in  1,\ldots,n$, the choice will be made heuristically minimizing the increasing of the \emph{score} function $S_f$, \ie, choosing a routing object $\tilde{O}_r$ such as
\[\tilde{O}_r = \underset{O_r}{\arg\min}{\left\{S_f(d_i(O_r,O_n) - r_i(O_r)), \forall  i \in 1,\ldots,n\right\}},\]

\vspace*{-10pt}
\noindent and this is possible since $S_f$ is monotonic increasing. Here, the main idea is to minimize the average covering volume for each domain associated with the routing object. 

Similar to what happens with other dynamic trees, \emph{Slim\textsuperscript{2}-tree} is built in a \emph{bottom-up} approach. When an overflow occurs in a node $N$, a new sibling node $N'$ is created (in the same level) and all entries are divided between the two nodes. Moreover, the copies of two objects $O_{r_1}$ and $O_{r_2}$ are selected and promoted to the father node and they will be used as pivots (routing objects) for the new regions represented by the nodes $N$ and $N'$. When the tree root is divided, a new root is created and the tree increases one level.
An ``ideal'' policy for promotion should select two routing objects and divide the other elements into two subsets in a way to reduce the regions volume and, consequently, the overlapping between them.
The division policy adopted in \emph{Slim\textsuperscript{2}-tree} follows an approach based on MST -- first used by \emph{Slim-tree} %~\cite{Traina00slim-trees:high}. 
-- see \cite{DBLP:conf/webmedia/SperandioPPG13,Sperandio2014} for a detailed description.

\subsection{Processing Similarity Queries in \emph{Slim\textsuperscript{2}-tree}}\label{sec:slim2:consulta}

\emph{Slim\textsuperscript{2}-tree} supports a multimodal range query (with a fixed value for search radius) and a multimodal search for the $k$-nearest neighbors. More important, it also allows both multimodal and unimodal (in which only one modality is used) search using the same structure for that.

Range queries in \emph{Slim\textsuperscript{2}-tree} could be unimodal -- in which only one modality is considered -- or multimodal, when the \emph{score} function is used to analyze all modalities simultaneously.
Given a collection of indexed objects $C$, a query object $O_q$ and a query radius $r(O_q)$, a unimodal range query \texttt{range$_i$}$(O_q,r(O_q), C)$ for a given modality $i$ consists in returning all objects $O_j \in C$ for which $d_i(O_j,O_q) \leq r(O_q)$, for a given modality $i$. 
On the other hand, a multimodal range query using a monotonic increasing \emph{score} function $S_f$ -- $\texttt{range}_{S_f}(O_q,r(O_q), C)$ -- consists in locating all objects $O_j \in C$ for which $S_f(d_i(O_j,O_q),\forall i=1,\ldots,n) \leq r(O_q)$. 
It is worth mentioning that the \emph{score} function $S_f$ should be the same used during insertions.
Another range query that is possible to be made is a multimodal search which allows distinct values for each modality radius $\texttt{range}_{r}(O_q,r_1(O_q),\ldots ,r_n(O_q), C)$. In this case, the search will return all objects $O_j \in C$ for which $d_i(O_j,O_q) \leq r_i(O_q), \forall i=1,\ldots,n$.

Search algorithms are omitted due to space limitations -- see \cite{DBLP:conf/webmedia/SperandioPPG13,Sperandio2014} for a detailed description.
In all of them, \textit{triangular inequality} is used to optimize the search by reducing the number of both distance calculations and disk accesses.

The \texttt{kNN\_Search} algorithm searches for the $k$-nearest neighbors given a query object $O_q$ -- supposing that \emph{Slim\textsuperscript{2}-tree} has at least $k$ objects. The steps of the \texttt{kNN\_Search} are similar to 
the ones of a range search; however, the criteria used to obtain performance improvements are dynamic, since query radii are defined based on the distances between $O_q$ and $O_k$ -- which represents the $k$-th closest neighbor in any moment during the search. The implementation of \texttt{kNN\_Search} could also be unimodal or multimodal -- using only one feature and distance function for the unimodal case; or adopting the \emph{score} function $S_f$ for the multimodal version -- see \cite{Sperandio2014}. 

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\section{Multimodal \emph{Slim-down} Algorithm}\label{sec:slimdown}

Similarly to~\cite{Traina00slim-trees:high}, a multimodal \emph{post-processing} algorithm is proposed for \emph{Slim\textsuperscript{2}-tree} -- multimodal \emph{Slim-down}.
The main idea is to move an element from a leaf node to a sibling node without increasing the radius (or radii) of the hyperregion associated with the receiving node. If the selected object is the farthest from the pivot of the supplying node, this may allow a reduction of the radius (radii) of the hyperregion associated with it. Therefore, the use of multimodal \emph{Slim-down} may help improving search performance of \emph{Slim\textsuperscript{2}-tree}, since it could minimize the overlap between nodes.

\begin{algorithm}[!b]
\caption{Multimodal \emph{Slim-down} algorithm applied to \emph{Slim\textsuperscript{2}-tree}.} 
\label{alg:slimdown}
\scriptsize
%
\footnotesize
\begin{algorithmic}[1]
\Procedure{SlimDown}{$RootNode$}
\State $num\_repeat \leftarrow 0$
\State $abort \leftarrow \textbf{false}$
\Repeat
  \State $moved \leftarrow \textbf{false}$
  \State $abort \leftarrow \Call{SlimDownalyze}{RootNode}$ \Comment Starts recursive procedure.
  \If{$abort = \textbf{true}$} 
    \State \textbf{break}
  \EndIf
\Until{$moved = \textbf{true}$}
\Comment Repeat again every time an object is moved.
\EndProcedure
\end{algorithmic}
\end{algorithm}

\begin{algorithm}[!t]
\caption{Recursive procedure responsible for analyzing tree nodes and executing \emph{Slim-down}.} 
\label{alg:slimdown2}
\scriptsize
\begin{algorithmic}[1]
\Procedure{SlimDownalyze}{$N$}
\State\textbf{Input:} $N$ -- Subtree root node (initially \emph{Slim\textsuperscript{2}-tree} root node).
\Statex
\If{$N ~\neg \Call{isLEAF}{}$}
  \ForAll{ $O_r \in N $} 
  \Comment Recursively call to \texttt{SlimDownalyze} for each node entry.
    \State $abort \leftarrow \Call{SlimDowalyze}{ptr(O_r)}$
    \If{$abort = \textbf{true}$}
      \State \Return $abort$; 
    \EndIf
  \EndFor
\ElsIf{$N ~\Call{isLEAF}{}$ \textbf{and} $N ~\neg\Call{isROOT}{}$} \Comment{Try to reduce the overlap involving a leaf node.}
  \State $O_p \leftarrow \Call{Pivot}{N}$
  \Comment{Representative of $N$.}
  \State $O_f \leftarrow O_p$
  \Comment{Initialize the farthest element of $N$.}
  \State $D_f[i] \leftarrow d_i(O_f,O_p) \forall i \in 1,\ldots,n$
  \Comment{Initialize distances between $O_f$ and $O_p$.}
  \State $moved \leftarrow \textbf{false}$
  \ForAll{$O_j \in N$}
  \Comment Look for the farthest element of $N$.  
    \If{$d_i(O_j,O_p) > D_f[i] \forall i \in 1,\ldots,n$}      
      \State $O_f \leftarrow O_j$ \Comment A new farthest element is found.
      \State $D_f[i] \leftarrow d_i(O_j,O_p)\forall i \in 1,\ldots,n$       
    \EndIf
  \EndFor
  \State $N^p \leftarrow  \Call{Parent}{N}$
  \Comment Parent node of N.
  \State $\mathcal{N}^s \leftarrow N \in \{ N^p \setminus \{N\} \}$
  \Comment Set of siblings of N.
  \State $num\_repeat \leftarrow num\_repeat + 1$
   \If{$num\_repeat > 3 \times \Call{NEntries}{N^p}$}
      \State $abort \leftarrow \textbf{true}$
      \Comment Maximum number of iteration is reached.
      \State $\Return~abort$
   \EndIf
  \ForAll{$N' \in \mathcal{N}^s$}
  \Comment Search for suitable node among the siblings of $N$.
    \State ${O_p}' \leftarrow \Call{Pivot}{N'}$    
    \If{$(d_i(O_f,{O_p}') \leq 
r_i({O_p}')\forall i \in 1,\ldots,n) ~\textbf{and}~ N' ~\neg 
\Call{isFULL}{}$}       
       \State $moved \leftarrow \textbf{true}$
       \Comment A suitable node is found.
       \State $\textbf{break}$
     \EndIf
  \EndFor
  \If{$moved = \textbf{true}$}
     \State $\Call{Move}{O_f,N,N'}$
     \Comment Move $O_f$ from $N$ to $N'$.
  \EndIf
\EndIf
\EndProcedure
\end{algorithmic}
\end{algorithm}

Multimodal \emph{Slim-down} algorithm (see Algorithm~\ref{alg:slimdown} and Algorithm~\ref{alg:slimdown2}) is similar to the one adopted by \emph{Slim-tree}, \ie, the farthest object $O_f$ belonging to a node $N$ (which is responsible for defining the radii of the associated hyperregion) is selected and it is moved to a sibling node $N'$ which already covers the object, so there is no need of modifying the radii of $N'$. 
This heuristic procedure is applied until no more exchanges between nodes are possible or until the maximum number of iterations is reached (to prevent an infinite loop) -- see \textit{lines 24--27} in Algorithm~\ref{alg:slimdown2}. 
However, since a \emph{Slim\textsuperscript{2}-tree} node is associated with a hyperregion defined by multiple domains, different policies could be used to select the farthest object $O_f$ within a tree node $N$. 
Two of those policies are considered in this article  (see \textit{lines 15--20} in Algorithm~\ref{alg:slimdown2}):  
(i) \texttt{POL1}: choose the node element that presents all distance values to the pivot (for each modality) larger than the others; and 
(ii) \texttt{POL2}: choose any node element that presents the larger distance value to the pivot (for any modality) when compared to the others.

The first policy \texttt{POL1} selects an element that is responsible for defining all the radii of the associated hyperregion (this policy is the one implemented in \textit{line 16} of Algorithm~\ref{alg:slimdown2}), while the second policy \texttt{POL2} chooses any element associated with at least one of the radii of the hyperregion associated with the node. \texttt{POL2} is obtained by changing \textit{line 16} to one that looks for just one larger distance value, \ie, $\exists i \in 1,\ldots,n\;|\; d_i(O_j,O_p)) > D_f[i]$ (\textit{line 18} should also be adjusted accordingly).
Although policy \texttt{POL1} is more similar to the original unimodal version of \emph{Slim-down}, in which generally only one element is responsible for defining the radius of the hypersphere in \emph{Slim-tree}, it may not provide the best results since it might be harder to find an element that is solely responsible for defining all the radii of the associated hyperregion, and, therefore, no object would be moved between nodes. On the other hand, policy \texttt{POL2} always finds at least one candidate object which is related to the maximum distance from the pivot for each modality 
%(\ie, the radius value of the hyperregion for that modality), 
and, consequently, it may produce better results.

\citeN{Traina00slim-trees:high} only present results for one scenario of \textit{Slim-down} application (\ie, when it is executed after the tree creation), since they did not obtain different results for distinct scenarios.
However, here two different contexts are considered for the use of multimodal \emph{Slim-down}:
(i) \texttt{SDW1}: when it is executed only once after the \emph{Slim\textsuperscript{2}-tree} is fully constructed; and 
(ii) \texttt{SDW2}: when it is executed repeatedly after $num\_sdw$ insertions.
There is a possible interference between the context of application (\texttt{SDW1} or \texttt{SDW2}) and the selected policy (\texttt{POL1} or \texttt{POL2}). 
Actually, \texttt{POL1} should only be affected by \texttt{SDW2} for very small values of $num\_sdw$, since it would be easier to find an element that were solely responsible for all radii of a tree node. 
For larger values of $num\_sdw$, \texttt{POL1} may not promote any performance improvement, since it might be harder to find any suitable candidates. 
This is similar to what it is expected when \texttt{POL1} is applied at end of Slim-tree construction (\texttt{SDW1}). 
However, \texttt{POL2} may promote a greater  improvement of \emph{Slim\textsuperscript{2}-tree} performance, since it might find many candidates, especially when \texttt{SDW2} is adopted (as shown in the analysis of test results).

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\section{Experimental results}\label{sec:experiment}

In this section, we present some experiments in order to assess the performance of \emph{Slim\textsuperscript{2}-tree}. Our video corpora consists of TV broadcast, recorded directly and continuously from cable TV channels, and Internet retrieved videos. The dataset is composed by 48 videos of different categories/genres, like documentary, movie, news, 
TV series, and others (almost 21 hours). Each video was divided in fixed length videoclips of 01 second and, then, each one of these clips has its visual and acoustic features extracted and stored in the \emph{Slim\textsuperscript{2}-tree} -- a total of 74,744 videoclips. 
Those short-length videoclips were used to avoid degradation with time, especially in relation to the acoustic data which may change a lot in a short period of time.
Table~\ref{tab:categorias} shows some information about our video dataset and Fig.~\ref{fig:samples} presents some samples of frames belonging to videos from each distinct class of the dataset. 
As one can see in Fig.~\ref{fig:samples}, since videos were recorded continuously, the dataset presents a great variety of content even inside of the same class. And this poses a great challenge during the search of some  videoclips among the others of the same class (as it will be shown forward), since for some classes there is not a strong correlation (neither visual nor acoustic) among the contents of their videoclips.
The experiments were performed on a Xeon 2.40GHz with 48 GB of main memory. All structures were implemented from scratch in Java under Debian Linux 3.9.8-1/\emph{OpenJDK RT (IcedTea 2.3.9)}.

\begin{table}[!t]
\caption{Information about video dataset and queries.} \label{tab:categorias}
\sffamily % CHANGES THE FONT WITHIN THE TABLE TO sans serif
\centering
\scriptsize
%\footnotesize
\renewcommand{\tabcolsep}{3pt}
\begin{tabular}{l|l|c|c|c|c|c}
\hline \hline
\multicolumn{1}{c|}{Category} & \multicolumn{1}{c|}{Class} &  \multicolumn{1}{c|}{\# Videos} & \multicolumn{1}{c|}{\# Clips} & \multicolumn{1}{c|}{Length}  & \multicolumn{1}{c|}{\# Queries} & \multicolumn{1}{c}{Percentage} \\
\hline 
Musical       & Adele       &  04 &\ \ 5,878 & 01:37:59 & 284  & 4.83\%\\
					    & RogerWaters &  04 & 18,102 & 05:01:43 & 876  & 4.84\% \\ \hline
Documentary   & Africa      &  03 &\ \ 2,701 & 00:45:01 &\ \ 89  & 3.30\% \\
					    & Ocean       &  01 &\ \ 2,699 & 00:44:59 & 129  & 4.78\%\\  \hline
Sports		    & F1          &  05 &\ \ 4,844 & 01:20:47 & 234  & 4.83\% \\
 					    & Soccer      &  16 &\ \ 9,954 & 02:46:01 & 481  & 4.83\%\\  \hline
News          & TV news     &  03 &\ \ 6,671 & 01:51:12 & 322  & 4.83\% \\ \hline
Cartoon       & Simpsons    &  03 &\ \ 3,865 & 01:04:27 & 129  & 3.33\%\\  \hline
Variety       & Nigella     &  03 &\ \ 5,169 & 01:26:10 & 235  & 4.55\%\\
					    & TopGear     &  03 & 11,027 & 03:03:48 & 538  & 4.88\%\\ \hline
TV series     & BigBang     &  03 &\ \ 3,834 & 01:03:55 & 183  & 4.77\%\\
\hline
\multicolumn{2}{c|}{Total} &  48 & 74,744 & 20:45:44 & 3,500 & --- \\
\hline \hline
\end{tabular}
\rmfamily % RESTORES TO TIMES, SO THAT CAPTION IS WRITTEN PROPERLY
\end{table}

\begin{figure}[!b]
\centering
\tiny
\subfigure[Adele]{\label{fig:samples:adele}
\centering
\includegraphics [width=.47\linewidth]{Fig3a.jpg}
}
\subfigure[RogerWaters]{\label{fig:samples:roger}
\centering
\includegraphics [width=.47\linewidth]{Fig3b.jpg}
}\\[-5pt]
\subfigure[Africa]{\label{fig:samples:africa}
\centering
\includegraphics [width=.47\linewidth]{Fig3c.jpg}
}
\subfigure[Ocean]{\label{fig:samples:ocean}
\centering
\includegraphics [width=.47\linewidth]{Fig3d.jpg}
}\\[-5pt]
\subfigure[F1]{\label{fig:samples:f1}
\centering
\includegraphics [width=.47\linewidth]{Fig3e.jpg}
}
\subfigure[Soccer]{\label{fig:samples:soccer}
\centering
\includegraphics [width=.47\linewidth]{Fig3f.jpg}
}\\[-5pt]
\subfigure[TV News]{\label{fig:samples:news}
\centering
\includegraphics [width=.47\linewidth]{Fig3g.jpg}
}
\subfigure[Simpsons]{\label{fig:samples:simpsons}
\centering
\includegraphics [width=.47\linewidth]{Fig3h.jpg}
}\\[-5pt]
\subfigure[Nigella]{\label{fig:samples:nigella}
\centering
\includegraphics [width=.47\linewidth]{Fig3i.jpg}
}
\subfigure[TopGear]{\label{fig:samples:topgear}
\centering
\includegraphics [width=.47\linewidth]{Fig3j.jpg}
}\\[-5pt]
\subfigure[BigBang]{\label{fig:samples:bigbang}
\centering
\includegraphics [width=.47\linewidth]{Fig3k.jpg}
}\\[-5pt]
\caption{Some samples of frames belonging to videos from each distinct class of the dataset.}\label{fig:samples}
\end{figure}

For each videoclip, only one visual keyframe is extracted (in the middle of the clip), while acoustic frames of 01 second are sampled at 22.05 Hz (16 bits) monaural. In our experiments, visual data are described using GIST~\cite{Oliva06buildingthe} and acoustic information is represented by  \textit{Mel-Frequency Cepstral Coefficient} -- MFCC~\cite{Ganchev05comparativeevaluation}.
Most of the works using the GIST descriptor resize the image in a preliminary stage, producing a small square image. %typically ranging from 32 to 128 pixels. 
Following~\cite{Douze:2009}, we adopt a size of $32\times 32$ pixels -- and visual frames are rescaled to that size irrespective of their aspect ratio. After resizing, color GIST descriptor is calculated for each visual frame producing a 960-dimensional feature vector.
In the acoustic domain, MFCC is used to describe the one-second audio frames adopting a 40 ms window with 25\% overlap which generates a 13-dimensional feature vector for each window -- those vectors are concatenated in a single 377-dimensional feature vector for each acoustic frame. A simple \emph{min-max} normalization is applied for both domains. Finally, a total number of 149,488 (visual and acoustic) descriptors are stored in a \emph{Slim\textsuperscript{2}-tree}.

\begin{figure}[!t]
\centering
\tiny
\subfigure[Precision]{\label{fig:pr-global}
\centering
\begin{tikzpicture}
\begin{axis}[ymin=0,ymax=1,
 font=\tiny,
 xlabel={\# Correct clips},
 ylabel={Avg. Precision}, 
     xlabel style={xshift=0.9ex, anchor=center,font=\tiny},
     ylabel style={yshift=0.1cm, anchor=center,font=\tiny},
 grid=both, 
 grid=both, 
 legend pos=south east,
 legend style={fill=none,draw=none,font=\tiny, at={(0.5 ,0.25)}, anchor=east},
 height=3.25cm, width=5.0cm,
]
\addplot +[smooth,mark=asterisk] table[x index=0, y index=1, col sep=comma] 
{./media_revocacao-global.txt};
%\addlegendentry{$M^2$\emph{-tree}}

\addplot +[smooth,mark=square] table[x index=0, y 
index=2, col sep=comma] {./media_revocacao-global.txt};
%\addlegendentry{$Slim^2$\emph{-tree}}

\addplot +[smooth,mark=triangle] table[x index=0, y 
index=5, col sep=comma] {./media_revocacao-global.txt};
%\addlegendentry{\emph{Late fusion}}
\end{axis}
\end{tikzpicture}
}\qquad
\subfigure[Time\hspace*{1.75cm}]{\label{fig:tempo-knn-global}
\begin{tikzpicture}
\begin{axis}[
 font=\tiny,
 xlabel={$k$}, 
 ylabel={Avg. time (ms)},
 xlabel style={xshift=0.9ex, anchor=center,font=\tiny},
 ylabel style={yshift=0.1cm, anchor=center,font=\tiny},
 grid=both, 
 legend pos=south east,
 legend style={font=\tiny, at={(1.8,0.5)}, anchor=east},
 height=3.25cm, width=5.0cm,
]

\addplot +[smooth,blue,mark=asterisk] table[x index=0, y index=1, col sep=comma] 
{./media_knn_tempo-global.txt};
\addlegendentry{$M^2$\emph{-tree}}

\addplot +[smooth,color=red,mark=square] table[x index=0, y 
index=2, col sep=comma] {./media_knn_tempo-global.txt};
\addlegendentry{$Slim^2$\emph{-tree}}

\addplot +[smooth,mark=triangle] table[x index=0, y index=9, col sep=comma] 
{./media_knn_tempo-global.txt};
\addlegendentry{\emph{Late-fusion}}
\end{axis}
\end{tikzpicture}
}\\[-5pt]
\caption{Average precision and time for multimodal $k$-NN search (Global).}
\end{figure}

\begin{figure}[!b]
\centering
\tiny
\subfigure[Disk access]{\label{fig:knn-disk-global}
\begin{tikzpicture}
\begin{axis}[
 font=\tiny,
 xlabel={$k$}, 
 ylabel={Avg. \# Disk Access},
 xlabel style={xshift=0.9ex, anchor=center,font=\tiny},
 ylabel style={ yshift=0.1cm, anchor=center,font=\tiny},
 grid=both, 
 legend pos=south east,
 legend style={fill=none,draw=none,font=\tiny, at={(1,0.5)}, anchor=east},
 height=3.25cm, width=5.0cm,
]

\addplot +[smooth,blue,mark=asterisk] table[x index=0, y index=1, col sep=comma] 
{./media_knn_es-global.txt};
%\addlegendentry{$M^2$\emph{-tree}}

\addplot +[smooth,color=red,mark=square] table[x index=0, y 
index=2, col sep=comma] {./media_knn_es-global.txt};
%\addlegendentry{$Slim^2$\emph{-tree}}

\addplot +[smooth,mark=triangle] table[x index=0, y 
expr=\thisrowno{3} + \thisrowno{4}, col sep=comma] 
{./media_knn_es-global.txt};
%\addlegendentry{\emph{Late-fusion}}
\end{axis}
\end{tikzpicture}
}\qquad
\subfigure[Distance calculation\hspace*{1.75cm}]{\label{fig:knn-dist-global}
\begin{tikzpicture}
\begin{axis}[
 xlabel={$k$},
 ylabel={Avg. \# Dist. Calc.},
     xlabel style={xshift=0.9ex, anchor=center,font=\tiny},
     ylabel style={yshift=0.1cm, anchor=center,font=\tiny},
 font=\tiny, 
 grid=both, 
 legend pos=south east,
 legend style={font=\tiny, at={(1.8,0.5)}, anchor=east},
 height=3.25cm, width=5.0cm,
]

\addplot +[smooth,blue,mark=asterisk] table[x index=0, y index=1, col sep=comma] 
{./media_knn_cpu-global.txt};
\addlegendentry{$M^2$\emph{-tree}}

\addplot +[smooth,color=red,mark=square] table[x index=0, y 
index=2, col sep=comma] {./media_knn_cpu-global.txt};
\addlegendentry{$Slim^2$\emph{-tree}}

\addplot +[smooth,mark=triangle] table[x index=0, y 
expr=\thisrowno{3} + \thisrowno{4}, col sep=comma] 
{./media_knn_cpu-global.txt};
\addlegendentry{\emph{Late-fusion}}

\addplot +[smooth,mark=+] table[x index=0, y expr=74743*2 ,col sep=comma] 
{./media_knn_cpu-global.txt};
\addlegendentry{\emph{Sequencial}}
\end{axis}
\end{tikzpicture}
}\\[-5pt]
\caption{Avg. number of disk accesses and distance calculations 
for multimodal $k$-NN search (Global). The number of disk accesses for sequential access is omitted since it is much larger than the others.}\label{fig:knn-global}
\end{figure}

Since we are not able to find any data structure developed specifically for multimodal content-based video retrieval, we compare the results of \emph{Slim\textsuperscript{2}-tree} with those obtained by an implementation of \emph{M\textsuperscript{2}-tree} and by a \emph{late fusion} strategy based on the combination of the results generated by two distinct \emph{Slim-trees} -- one for each modality. We have also developed an implementation of \emph{M\textsuperscript{2}-tree} based on the standard policies of \emph{M-tree}, as described by its authors in~\cite{Ciaccia2000}. The \emph{score} function $S_f = \max\{d_i, \forall i=1,\ldots,n\}$ was used with \emph{Slim\textsuperscript{2}-tree} and \emph{M\textsuperscript{2}-tree} -- the same function adopted in~\cite{Ciaccia2000}; and the maximum number of objects per node $m$ is set to 30.

Tests were made using a set of 3,500 queries selected randomly from the dataset ($\approx 5\%$ of the video dataset). Table~\ref{tab:categorias} also presents information about the query clips. 
In order to evaluate query results, we consider as correct (relevant) answers 
any clip that belongs to the same class of the query. 
This was done due to the lack of a standard benchmark for evaluating  multimodal CBVR using visual and acoustic data. 
Moreover, the use of this criteria to establish a ground-truth emulates better the subjective evaluation found in a human assessment.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\subsection{Results for Similarity Queries}

Fig.~\ref{fig:pr-global} presents average precision values obtained by \emph{Slim\textsuperscript{2}-tree},  \emph{M\textsuperscript{2}-tree}, and \emph{late fusion} strategy for all 3,500 queries. It can be easily seen that \emph{Slim\textsuperscript{2}-tree} and \emph{M\textsuperscript{2}-tree} present similar results and both are superior to those of \emph{late fusion} strategy. Moreover, the \textit{mean average precision} -- MAP values obtained by \emph{Slim\textsuperscript{2}-tree}, \emph{M\textsuperscript{2}-tree} and \emph{late fusion} strategy are 21.62\%, 21.62\% and 21.45\%, respectively (which are statistically equivalent with a confidence level of 95\%), but  
they present distinct values for computational time. 
Fig.~\ref{fig:tempo-knn-global} shows the average time per query associated with \emph{Slim\textsuperscript{2}-tree}, \emph{M\textsuperscript{2}-tree} and \emph{late fusion} strategy, while 
Fig.~\ref{fig:knn-global} presents the average number of disk accesses and distance calculations for multimodal k-NN search. \emph{Slim\textsuperscript{2}-tree} exhibits an expressive reduction of the disk accesses when compared to the other approaches ($\approx40\%$). Considering the distance calculations, \emph{Slim\textsuperscript{2}-tree} and \emph{M\textsuperscript{2}-tree} have presented very similar results (less than $1.3\%$ of difference). 
In Fig.~\ref{fig:pr-conjuntos1}, the average precision values for some video classes are shown (one class for each category). It is worth mentioning that results obtained by both \emph{Slim\textsuperscript{2}-tree} and \emph{M\textsuperscript{2}-tree} are superior to the ones achieved by \emph{late fusion} strategy. In particular, the improvement is larger for categories and classes in which there is a greater correlation between visual and acoustic content, as well as in the situations when they exhibit little variability through the entire duration of the video content, because this may help in the recognition of a clip of the same class -- see the results obtained for classes \emph{Adele} and \emph{F1}.

\begin{figure*}[!t]
\tiny
\centering
 {
\tiny
\centering
\begin{tikzpicture}
\begin{axis}[ymin=0,ymax=1,
 font=\tiny,
 xlabel={\# Correct clips (Adele)},
 ylabel={Avg.Precision}, 
     xlabel style={xshift=0.9ex, yshift=-.5ex, anchor=center,font=\tiny},
     ylabel style={ yshift=0.1cm, anchor=center,font=\tiny},
 grid=both, 
 grid=both, 
 legend pos=south east,
 legend style={fill=none,draw=none,font=\tiny, at={(1.03 ,0.5)}, anchor=east},
 height=3.3cm, width=4.35cm,
% height=3.5cm, width=4.6cm,
]
\addplot +[smooth,mark=asterisk] table[x index=0, y index=1, col sep=comma] 
{./media_revocacao-adele.txt};
%\addlegendentry{$M^2$\emph{-tree}}

\addplot +[smooth,mark=square] table[x index=0, y 
index=2, col sep=comma] {./media_revocacao-adele.txt};
%\addlegendentry{$Slim^2$\emph{-tree}}

\addplot +[smooth,mark=triangle] table[x index=0, y 
index=5, col sep=comma] {./media_revocacao-adele.txt};
%\addlegendentry{\emph{Late fusion}}
\end{axis}
\end{tikzpicture}
%
\begin{tikzpicture}
\begin{axis}[ymin=0,ymax=1,
 font=\tiny,
 xlabel={\# Correct clips (F1)},
     xlabel style={xshift=0.9ex, yshift=-.5ex, anchor=center,font=\tiny},
 grid=both, 
 legend pos=south east,
 legend style={fill=none,draw=none,font=\tiny, at={(1.03 ,0.5)}, anchor=east},
 height=3.3cm, width=4.35cm,
% height=3.5cm, width=4.6cm,
]
\addplot +[smooth,mark=asterisk] table[x index=0, y index=1, col sep=comma] 
{./media_revocacao-f1.txt};
%\addlegendentry{$M^2$\emph{-tree}}

\addplot +[smooth,mark=square] table[x index=0, y 
index=2, col sep=comma] {./media_revocacao-f1.txt};
%\addlegendentry{$Slim^2$\emph{-tree}}

\addplot +[smooth,mark=triangle] table[x index=0, y 
index=5, col sep=comma] {./media_revocacao-f1.txt};
%\addlegendentry{\emph{Late fusion}}
\end{axis}
\end{tikzpicture}
%
\begin{tikzpicture}
\begin{axis}[ymin=0,ymax=1,
 font=\tiny,
 xlabel={\# Correct clips (Nigella)},
     xlabel style={xshift=0.9ex, yshift=-.5ex, anchor=center,font=\tiny},
 grid=both, 
 legend pos=south east,
 legend style={fill=none,draw=none,font=\tiny, at={(1.03 ,0.5)}, anchor=east},
 height=3.3cm, width=4.35cm,
% height=3.5cm, width=4.6cm,
]
\addplot +[smooth,mark=asterisk] table[x index=0, y index=1, col sep=comma] 
{./media_revocacao-nigella.txt};
%\addlegendentry{$M^2$\emph{-tree}}

\addplot +[smooth,mark=square] table[x index=0, y 
index=2, col sep=comma] {./media_revocacao-nigella.txt};
%\addlegendentry{$Slim^2$\emph{-tree}}

\addplot +[smooth,mark=triangle] table[x index=0, y 
index=5, col sep=comma] {./media_revocacao-nigella.txt};
%\addlegendentry{\emph{Late fusion}}
\end{axis}
\end{tikzpicture}
%
\begin{tikzpicture}
\begin{axis}[ymin=0,ymax=1,
 font=\tiny,
 xlabel={\# Correct clips (Ocean)},
     xlabel style={xshift=0.9ex, yshift=-.5ex, anchor=center,font=\tiny},
 grid=both, 
 legend pos=south east,
 legend style={fill=none,draw=none,font=\tiny, at={(1.03 ,0.5)}, anchor=east},
 height=3.3cm, width=4.35cm,
% height=3.5cm, width=4.6cm,
]
\addplot +[smooth,mark=asterisk] table[x index=0, y index=1, col sep=comma] 
{./media_revocacao-oceano.txt};
%\addlegendentry{$M^2$\emph{-tree}}

\addplot +[smooth,mark=square] table[x index=0, y 
index=2, col sep=comma] {./media_revocacao-oceano.txt};
%\addlegendentry{$Slim^2$\emph{-tree}}

\addplot +[smooth,mark=triangle] table[x index=0, y 
index=5, col sep=comma] {./media_revocacao-oceano.txt};
%\addlegendentry{\emph{Late fusion}}
\end{axis}
\end{tikzpicture}\\
\begin{tikzpicture}
\begin{axis}[ymin=0,ymax=1,
 font=\tiny,
 xlabel={\# Correct clips (BigBang)},
 ylabel={Avg.Precision}, 
     xlabel style={xshift=0.9ex, yshift=-.5ex, anchor=center,font=\tiny},
     ylabel style={ yshift=0.1cm, anchor=center,font=\tiny},
 grid=both, 
 legend pos=south east,
 legend style={fill=none,draw=none,font=\tiny, at={(1.03 ,0.8)}, anchor=east},
 height=3.3cm, width=4.35cm,
% height=3.5cm, width=4.6cm,
]
\addplot +[smooth,mark=asterisk] table[x index=0, y index=1, col sep=comma] 
{./media_revocacao-bigbang.txt};
%\addlegendentry{$M^2$\emph{-tree}}

\addplot +[smooth,mark=square] table[x index=0, y 
index=2, col sep=comma] {./media_revocacao-bigbang.txt};
%\addlegendentry{$Slim^2$\emph{-tree}}

\addplot +[smooth,mark=triangle] table[x index=0, y 
index=5, col sep=comma] {./media_revocacao-bigbang.txt};
%\addlegendentry{\emph{Late fusion}}
\end{axis}
\end{tikzpicture}
\!\!\!\!\!\!
\begin{tikzpicture}
\begin{axis}[ymin=0,ymax=1,
 font=\tiny,
 xlabel={\# Correct clips (TV News)},
     xlabel style={xshift=0.9ex, yshift=-.5ex, anchor=center,font=\tiny},
 grid=both, 
 legend pos=south east,
 legend style={fill=none,draw=none,font=\tiny, at={(1.03 ,0.8)}, anchor=east},
 height=3.3cm, width=4.35cm,
% height=3.5cm, width=4.6cm,
]
\addplot +[smooth,mark=asterisk] table[x index=0, y index=1, col sep=comma] 
{./media_revocacao-jornal.txt};
%\addlegendentry{$M^2$\emph{-tree}}

\addplot +[smooth,mark=square] table[x index=0, y 
index=2, col sep=comma] {./media_revocacao-jornal.txt};
%\addlegendentry{$Slim^2$\emph{-tree}}

\addplot +[smooth,mark=triangle] table[x index=0, y 
index=5, col sep=comma] {./media_revocacao-jornal.txt};
%\addlegendentry{\emph{Late fusion}}
\end{axis}
\end{tikzpicture}
\!\!\!\!\!\!\!
\begin{tikzpicture}
\begin{axis}[ymin=0,ymax=1,
 font=\tiny,
 xlabel={\# Correct clips (Simpsons)},
     xlabel style={xshift=0.9ex, yshift=-.5ex, anchor=center,font=\tiny},
 grid=both, 
 legend pos=south east,
 legend style={font=\tiny, at={(2.23 ,0.5)}, anchor=east},
% legend style={font=\tiny, at={(2.15 ,0.5)}, anchor=east},
 height=3.3cm, width=4.35cm,
% height=3.5cm, width=4.6cm,
]
\addplot +[smooth,mark=asterisk] table[x index=0, y index=1, col sep=comma] 
{./media_revocacao-simpsons.txt};
\addlegendentry{$M^2$\emph{-tree}}

\addplot +[smooth,mark=square] table[x index=0, y 
index=2, col sep=comma] {./media_revocacao-simpsons.txt};
\addlegendentry{$Slim^2$\emph{-tree}}

\addplot +[smooth,mark=triangle] table[x index=0, y 
index=5, col sep=comma] {./media_revocacao-simpsons.txt};
\addlegendentry{\emph{Late fusion}}
\end{axis}
\end{tikzpicture}
}\\[-5pt]
\caption{Average precision per class for multimodal $k$-NN search.}\label{fig:pr-conjuntos1}
\end{figure*}

\emph{Slim\textsuperscript{2}-tree} also performs unimodal search (based on only one modality). 
In order to assess this capacity, the results obtained for unimodal search by \emph{Slim\textsuperscript{2}-tree} are compared to those obtained by a \emph{Slim-tree} using only one modality and by an adaptation of \emph{M\textsuperscript{2}-tree} developed for this purpose (notice that the original version of \emph{M\textsuperscript{2}-tree} does not exhibit that capacity). Since those methods are exact, precision results obtained by these three approaches are identical (which was already expected), but the computational cost associated with the unimodal search made by \emph{Slim\textsuperscript{2}-tree} is very close to the one presented by the unimodal search made by a \emph{Slim-tree} using only one modality.
Fig.~\ref{fig:knn-mv-global} presents the average values of disk accesses and distance calculations for the k-NN search using only visual modality, while Fig.~\ref{fig:knn-ma-global} shows the same metrics when only acoustic modality is used. 
Considering the distance calculations, both \emph{Slim\textsuperscript{2}-tree} and \emph{M\textsuperscript{2}-tree} adaptation have achieved results that are close to the ones presented by a \emph{Slim-tree} for only one modality. But, in relation to the disk accesses, \emph{Slim\textsuperscript{2}-tree} exhibits a performance quite superior to  \emph{M\textsuperscript{2}-tree} adaptation, and again its results are close to the ones presented by a \emph{Slim-tree} for only one modality.
This is a great advantage of \emph{Slim\textsuperscript{2}-tree} when compared to the other analyzed multimodal approaches, because it is possible with a single data structure (the \emph{Slim\textsuperscript{2}-tree}) to perform both multimodal and unimodal searches. Moreover, \emph{Slim\textsuperscript{2}-tree} is capable of answering unimodal queries with a computational cost very similar to the one associated to a ``specialized'' data structure built using only one modality.

\begin{figure}[!b]
\centering
\subfigure[Using only visual data]{\label{fig:knn-mv-global}
\tiny
\centering
\begin{tikzpicture}
\begin{axis}[
 font=\tiny,
 xlabel={$k$},
 ylabel={Avg. \# Disk Access}, 
     xlabel style={xshift=0.9ex, anchor=center,font=\tiny},
     ylabel style={ yshift=0.1cm, anchor=center,font=\tiny},
 grid=both, 
 legend pos=south east,
 legend style={fill=none,draw=none,font=\tiny,at={(1,0.7)}, anchor=east},
 height=3.25cm, width=5.0cm,
]
\addplot +[smooth,blue,mark=asterisk] table[x index=0, y index=5, col sep=comma] 
{./media_knn_es-global.txt};
%\addlegendentry{$M^2$\emph{-tree}}

\addplot +[smooth,color=red,mark=square] table[x index=0, y 
index=7, col sep=comma] {./media_knn_es-global.txt};
%\addlegendentry{$Slim^2$\emph{-tree}}

\addplot +[smooth,mark=triangle] table[x index=0, y 
index=4, col sep=comma] {./media_knn_es-global.txt};
%\addlegendentry{\emph{Slim-tree Visual}}

\end{axis}
\end{tikzpicture}\qquad
\begin{tikzpicture}
\begin{axis}[ 
 font=\tiny,
 xlabel={$k$},
 ylabel={Avg. \# Dist. Calc.}, 
     xlabel style={xshift=0.9ex, anchor=center,font=\tiny},
     ylabel style={ yshift=0.1cm, anchor=center,font=\tiny},
 grid=both, 
 legend pos=south east,
 legend style={font=\tiny, at={(1.8,0.5)}, anchor=east},
 height=3.25cm, width=5.0cm,
]
\addplot +[smooth,blue,mark=asterisk] table[x index=0, y index=5, col sep=comma] 
{./media_knn_cpu-global.txt};
\addlegendentry{$M^2$\emph{-tree}}

\addplot +[smooth,color=red,mark=square] table[x index=0, y 
index=7, col sep=comma] {./media_knn_cpu-global.txt};
\addlegendentry{$Slim^2$\emph{-tree}}

\addplot +[smooth,mark=triangle] table[x index=0, y 
index=4, col sep=comma] {./media_knn_cpu-global.txt};
\addlegendentry{\emph{Slim-tree}}

\addplot +[smooth,mark=+] table[x index=0, y expr=74743,col sep=comma] 
{./media_knn_cpu-global.txt};
\addlegendentry{\emph{Sequencial}}

\end{axis}
\end{tikzpicture}
}\\[-5pt]
\subfigure[Using only acoustic data]{\label{fig:knn-ma-global}
\tiny
\centering
\begin{tikzpicture}
\begin{axis}[
 font=\tiny,
 xlabel={$k$},
 ylabel={Avg. \# Disk Access}, 
     xlabel style={xshift=0.9ex, anchor=center,font=\tiny},
     ylabel style={ yshift=0.1cm, anchor=center,font=\tiny},
 grid=both, 
 legend pos=south east,
 legend style={fill=none,draw=none,font=\tiny, at={(1,0.7)}, anchor=east},
 height=3.25cm, width=5.0cm,
]
\addplot +[smooth,blue,mark=asterisk] table[x index=0, y index=6, col sep=comma] 
{./media_knn_es-global.txt};
%\addlegendentry{$M^2$\emph{-tree}}

\addplot +[smooth,color=red,mark=square] table[x index=0, y 
index=8, col sep=comma] {./media_knn_es-global.txt};
%\addlegendentry{$Slim^2$\emph{-tree}}

\addplot +[smooth,mark=triangle] table[x index=0, y 
index=3, col sep=comma] {./media_knn_es-global.txt};
%\addlegendentry{\emph{Slim-tree Acústica}}

\end{axis}
\end{tikzpicture}\qquad
\begin{tikzpicture}
\begin{axis}[
 font=\tiny,
 xlabel={$k$},
 ylabel={Avg. \# Dist. Calc.}, 
     xlabel style={xshift=0.9ex, anchor=center,font=\tiny},
     ylabel style={ yshift=0.1cm, anchor=center,font=\tiny},
 grid=both, 
 legend pos=south east,
 legend style={font=\tiny, at={(1.8,0.5)}, anchor=east},
 height=3.25cm, width=5.0cm,
]
\addplot +[smooth,blue,mark=asterisk] table[x index=0, y index=6, col sep=comma] 
{./media_knn_cpu-global.txt};
\addlegendentry{$M^2$\emph{-tree}}

\addplot +[smooth,color=red,mark=square] table[x index=0, y 
index=8, col sep=comma] {./media_knn_cpu-global.txt};
\addlegendentry{$Slim^2$\emph{-tree}}

\addplot +[smooth,mark=triangle] table[x index=0, y 
index=3, col sep=comma] {./media_knn_cpu-global.txt};
\addlegendentry{\emph{Slim-tree}}

\addplot +[smooth,mark=+] table[x index=0, y expr=74743,col sep=comma] 
{./media_knn_cpu-global.txt};
\addlegendentry{\emph{Sequencial}}
\end{axis}
\end{tikzpicture}
}\\[-5pt]
\caption{Average number of disk accesses and distance calculations
for unimodal $k$-NN search (Global). The number of disk accesses for sequential access is omitted since it is much larger than the others.}\label{fig:knn-uni-global}
\end{figure}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\subsection{Results for Multimodal \emph{Slim-down}}

In order to assess the multimodal \emph{Slim-down} algorithm, the same set of 
3,500 queries was used again. 
% to measure the impact on the \emph{Slim\textsuperscript{2}-tree} performance. 
Since \emph{Slim\textsuperscript{2}-tree} represents an exact solution 
for similarity queries no difference in the quality of the results (values of average precision) should be expected, but performance numbers should improve if multimodal \emph{Slim-down} %algorithm 
really helps minimizing the overlap between nodes. Tests were made with the two policies -- \texttt{POL1} and \texttt{POL2}, considering both context -- \texttt{SDW1} and \texttt{SDW2} (with $num\_sdw = 60$ which is the double of the \emph{Slim\textsuperscript{2}-tree} node capacity).
Independently of the context (\texttt{SDW1} or \texttt{SDW2}), tests with policy \texttt{POL1} did not present
any improvement of \emph{Slim\textsuperscript{2}-tree} performance and their results will be omitted. 
This can be explained by the fact that policy \texttt{POL1} has only selected a very few candidates to be moved, and, therefore, a great minimization of the overlap between nodes was not possible.

Table~\ref{tab:slim-down-const} shows the total number of disk accesses, distance calculations and time spent with multimodal \emph{Slim-down} with policy \texttt{POL2}. It is worth mentioning that context \texttt{SDW2} took 40 times more time them \texttt{SDW1}. However, tests with \texttt{POL2} considering context \texttt{SDW2} have achieved a reduction of 1.5\% in the average number of disk accesses without compromising the average number of distance calculations, while context \texttt{SDW1} did not show any improvement, see Fig.~\ref{fig:knn-multimodal-slimdown}.
\emph{Slim-down} was also applied to the unimodal \emph{Slim-trees} used for the \emph{late fusion} approach.
But in this case, no improvement has been observed independently of the context used (\texttt{SDW1} or \texttt{SDW2}) -- see Fig.~\ref{fig:knn-unimodal-slimdown}. 
Fig.~\ref{fig:time-class} presents the average time for some video classes. As one can see the impact of multimodal \emph{Slim-down} over the average time of multimodal $k$-NN search is greater for lower values of $k$ ($\leq 20$).

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{table}[!t]
\caption{Total number of disk accesses, distance calculations and time spent by \emph{Slim-down} 
using \texttt{POL2}.}
\label{tab:slim-down-const}
\sffamily % CHANGES THE FONT WITHIN THE TABLE TO sans serif
\centering
%\footnotesize
\scriptsize
\begin{tabular}{l|r|r}
\hline
\hline
\multicolumn{1}{c|}{Context} & \multicolumn{1}{c|}{\texttt{SDW1}}  & \multicolumn{1}{c}{\texttt{SDW2}}\\
\hline
\# Disk accesses       & 2,190 &  225,374\\
\# Dist. calculations  & 1,090 &  15,599\\
Time (ms) & 1,947 &  79,568\\
\hline
\hline
\end{tabular}
\rmfamily % RESTORES TO TIMES, SO THAT CAPTION IS WRITTEN PROPERLY
\end{table}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{figure}[!t]
\centering
\tiny
\subfigure[Results for \emph{Slim\textsuperscript{2}-tree}]{\label{fig:knn-multimodal-slimdown}
\begin{tikzpicture}
\begin{axis}[
 font=\tiny,
 xlabel={$k$}, 
 ylabel={Avg. \# Disk Access},
 xlabel style={xshift=0.9ex, anchor=center,font=\tiny},
 ylabel style={ yshift=0.1cm, anchor=center,font=\tiny},
 grid=both, 
 legend pos=south east,
 legend style={fill=none,draw=none,font=\tiny, at={(1,0.5)}, anchor=east},
 height=3.25cm, width=5.0cm,
]
\addplot +[smooth,blue,mark=asterisk] table[x index=0, y index=4, col 
sep=comma] 
{./media_knn_all-global_slim2down_only.txt};
%\addlegendentry{$Slim^2$\emph{-tree}}

\addplot +[smooth,color=red,mark=square] table[x index=0, y 
index=5, col sep=comma] {./media_knn_all-global_slim2down_only.txt};
%\addlegendentry{$Slim^2$\emph{-tree}+\emph{swd1}}

\addplot +[smooth,mark=triangle] table[x index=0, y 
index=6, col sep=comma] {./media_knn_all-global_slim2down_only.txt};
%\addlegendentry{$Slim^2$\emph{-tree}+\emph{swd2}}
\end{axis}
\end{tikzpicture}
%}
\qquad
\begin{tikzpicture}
\begin{axis}[
 xlabel={$k$},
 ylabel={Avg. \# Dist. Calc.},
     xlabel style={xshift=0.9ex, anchor=center,font=\tiny},
     ylabel style={yshift=0.1cm, anchor=center,font=\tiny},
 font=\tiny, 
 grid=both, 
 legend pos=south east,
 legend style={font=\tiny, at={(2.0,0.5)}, anchor=east},
 height=3.25cm, width=5.0cm,
]
\addplot +[smooth,blue,mark=asterisk] table[x index=0, y index=1, col 
sep=comma] 
{./media_knn_all-global_slim2down_only.txt};
\addlegendentry{$Slim^2$\emph{-tree}}

\addplot +[smooth,color=red,mark=square] table[x index=0, y 
index=2, col sep=comma] {./media_knn_all-global_slim2down_only.txt};
\addlegendentry{$Slim^2$\emph{-tree}+\texttt{SDW1}}

\addplot +[smooth,mark=triangle] table[x index=0, y 
index=3, col sep=comma] {./media_knn_all-global_slim2down_only.txt};
\addlegendentry{$Slim^2$\emph{-tree}+\texttt{SDW2}}
\end{axis}
\end{tikzpicture}
}\\[-5pt]
\subfigure[Results for \textit{Late fusion}]{\label{fig:knn-unimodal-slimdown}
\begin{tikzpicture}
\begin{axis}[
 font=\tiny,
 xlabel={$k$}, 
 ylabel={Avg. \# Disk Access},
 xlabel style={xshift=0.9ex, anchor=center,font=\tiny},
 ylabel style={ yshift=0.1cm, anchor=center,font=\tiny},
 grid=both, 
 legend pos=south east,
 legend style={fill=none,draw=none,font=\tiny, at={(1,0.5)}, anchor=east},
 height=3.25cm, width=5.0cm,
]
\addplot +[smooth,blue,mark=asterisk] table[x index=0, y index=9, col 
sep=comma] 
{./media_knn_es-global.txt};
%\addlegendentry{\emph{Late fusion}}

\addplot +[smooth,color=red,mark=square] table[x index=0, y 
index=6, col sep=comma] {./media_knn_es-global-slimdown.txt};
%\addlegendentry{\emph{Late fusion}+\emph{swd1}}

\addplot +[smooth,mark=triangle] table[x index=0, y 
index=6, col sep=comma] {./media_knn_es-global-slimdown.txt};
%\addlegendentry{\emph{Late fusion}+\emph{swd2}}
\end{axis}
\end{tikzpicture}
\qquad
\begin{tikzpicture}
\begin{axis}[
 xlabel={$k$},
 ylabel={Avg. \# Dist. Calc.},
     xlabel style={xshift=0.9ex, anchor=center,font=\tiny},
     ylabel style={yshift=0.1cm, anchor=center,font=\tiny},
 font=\tiny, 
 grid=both, 
 legend pos=south east,
 legend style={font=\tiny, at={(2.0,0.5)}, anchor=east},
 height=3.25cm, width=5.0cm,
]
\addplot +[smooth,blue,mark=asterisk] table[x index=0, y index=9, col 
sep=comma] 
{./media_knn_cpu-global.txt};
\addlegendentry{\emph{Late fusion}}

\addplot +[smooth,color=red,mark=square] table[x index=0, y 
index=6, col sep=comma] {./media_knn_cpu-global-slimdown.txt};
\addlegendentry{\emph{Late fusion}+\texttt{SDW1}}

\addplot +[smooth,mark=triangle] table[x index=0, y 
index=6, col sep=comma] {./media_knn_cpu-global-slimdown.txt};
\addlegendentry{\emph{Late fusion}+\texttt{SDW2}}
\end{axis}
\end{tikzpicture}
}\\[-5pt]
\caption{Average number of disk accesses and distance calculations for multimodal $k$-NN search before and after using \emph{Slim-down} (Global).}
\label{fig:knn-down-global}
\end{figure}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{figure*}[!b]
\tiny
\centering
 {
\tiny
\centering
\begin{tikzpicture}
\begin{axis}[
 ymin=6400,ymax=7200,
 font=\tiny,
 xlabel={\# Correct clips (Adele)},
 ylabel={Avg. time (ms)}, 
     xlabel style={xshift=0.9ex, yshift=-.5ex, anchor=center,font=\tiny},
     ylabel style={ yshift=0.1cm, anchor=center,font=\tiny},
 grid=both, 
 grid=both, 
 legend pos=south east,
 legend style={fill=none,draw=none,font=\tiny, at={(1.03 ,0.5)}, anchor=east},
 height=3.3cm, width=4.35cm,
]
%\addplot +[smooth,mark=asterisk] table[x index=0, y index=1, col sep=comma] 
%{./media_knn_tempo-adele.txt};
%\addlegendentry{$M^2$\emph{-tree}}

\addplot +[smooth,mark=square] table[x index=0, y 
index=2, col sep=comma] {./media_knn_tempo-adele.txt};
%\addlegendentry{$Slim^2$\emph{-tree}}

\addplot +[smooth,mark=triangle] table[x index=0, y 
index=1, col sep=comma] {./media_knn_tempo-adele-slimdown.txt};
%\addlegendentry{$Slim^2$\emph{-tree}+sdw}
\end{axis}
\end{tikzpicture}
%
\begin{tikzpicture}
\begin{axis}[
 ymin=6400,ymax=7200,
 font=\tiny,
 xlabel={\# Correct clips (TopGear)},
 ylabel={Avg. time (ms)}, 
     xlabel style={xshift=0.9ex, yshift=-.5ex, anchor=center,font=\tiny},
     ylabel style={ yshift=0.1cm, anchor=center,font=\tiny},
 grid=both, 
 legend pos=south east,
 legend style={fill=none,draw=none,font=\tiny, at={(1.03 ,0.5)}, anchor=east},
 height=3.3cm, width=4.35cm,
]
%\addplot +[smooth,mark=asterisk] table[x index=0, y index=1, col sep=comma] 
%{./media_knn_tempo-topgear.txt};
%\addlegendentry{$M^2$\emph{-tree}}

\addplot +[smooth,mark=square] table[x index=0, y 
index=2, col sep=comma] {./media_knn_tempo-topgear.txt};
%\addlegendentry{$Slim^2$\emph{-tree}}

\addplot +[smooth,mark=triangle] table[x index=0, y 
index=1, col sep=comma] {./media_knn_tempo-topgear-slimdown.txt};
%\addlegendentry{$Slim^2$\emph{-tree}+sdw}
\end{axis}
\end{tikzpicture}
%
\begin{tikzpicture}
\begin{axis}[
 ymin=6400,ymax=7200,
 font=\tiny,
 xlabel={\# Correct clips (Soccer)},
     xlabel style={xshift=0.9ex, yshift=-.5ex, anchor=center,font=\tiny},
 grid=both, 
 legend pos=south east,
 legend style={fill=none,draw=none,font=\tiny, at={(1.03 ,0.5)}, anchor=east},
 height=3.3cm, width=4.35cm,
]
%\addplot +[smooth,mark=asterisk] table[x index=0, y index=1, col sep=comma] 
%{./media_knn_tempo-futebol.txt};
%\addlegendentry{$M^2$\emph{-tree}}

\addplot +[smooth,mark=square] table[x index=0, y 
index=2, col sep=comma] {./media_knn_tempo-futebol.txt};
%\addlegendentry{$Slim^2$\emph{-tree}}

\addplot +[smooth,mark=triangle] table[x index=0, y 
index=1, col sep=comma] {./media_knn_tempo-futebol-slimdown.txt};
%\addlegendentry{$Slim^2$\emph{-tree}+sdw}
\end{axis}
\end{tikzpicture}
%
\begin{tikzpicture}
\begin{axis}[
 ymin=6400,ymax=7200,
 font=\tiny,
 xlabel={\# Correct clips (Ocean)},
     xlabel style={xshift=0.9ex, yshift=-.5ex, anchor=center,font=\tiny},
 grid=both, 
 legend pos=south east,
 legend style={fill=none,draw=none,font=\tiny, at={(1.03 ,0.5)}, anchor=east},
 height=3.3cm, width=4.35cm,
]
%\addplot +[smooth,mark=asterisk] table[x index=0, y index=1, col sep=comma] 
%{./media_knn_tempo-oceano.txt};
%\addlegendentry{$M^2$\emph{-tree}}

\addplot +[smooth,mark=square] table[x index=0, y 
index=2, col sep=comma] {./media_knn_tempo-oceano.txt};
%\addlegendentry{$Slim^2$\emph{-tree}}

\addplot +[smooth,mark=triangle] table[x index=0, y 
index=1, col sep=comma] {./media_knn_tempo-oceano-slimdown.txt};
%\addlegendentry{$Slim^2$\emph{-tree}+sdw}
\end{axis}
\end{tikzpicture}\\
\begin{tikzpicture}
\begin{axis}[
 ymin=6400,ymax=7200,
 font=\tiny,
 xlabel={\# Correct clips (BigBang)},
 ylabel={Avg. time (ms)}, 
     xlabel style={xshift=0.9ex, yshift=-.5ex, anchor=center,font=\tiny},
     ylabel style={ yshift=0.1cm, anchor=center,font=\tiny},
 grid=both, 
 legend pos=south east,
 legend style={fill=none,draw=none,font=\tiny, at={(1.03 ,0.8)}, anchor=east},
 height=3.3cm, width=4.35cm,
]
%\addplot +[smooth,mark=asterisk] table[x index=0, y index=1, col sep=comma] 
%{./media_knn_tempo-bigbang.txt};
%\addlegendentry{$M^2$\emph{-tree}}

\addplot +[smooth,mark=square] table[x index=0, y 
index=2, col sep=comma] {./media_knn_tempo-bigbang.txt};
%\addlegendentry{$Slim^2$\emph{-tree}}

\addplot +[smooth,mark=triangle] table[x index=0, y 
index=1, col sep=comma] {./media_knn_tempo-bigbang-slimdown.txt};
%\addlegendentry{$Slim^2$\emph{-tree}+sdw}
\end{axis}
\end{tikzpicture}
%
\begin{tikzpicture}
\begin{axis}[
 ymin=6400,ymax=7200,
 font=\tiny,
 xlabel={\# Correct clips (TV News)},
     xlabel style={xshift=0.9ex, yshift=-.5ex, anchor=center,font=\tiny},
 grid=both, 
 legend pos=south east,
 legend style={fill=none,draw=none,font=\tiny, at={(1.03 ,0.8)}, anchor=east},
 height=3.3cm, width=4.35cm,
]
%\addplot +[smooth,mark=asterisk] table[x index=0, y index=1, col sep=comma] 
%{./media_knn_tempo-jornal.txt};
%\addlegendentry{$M^2$\emph{-tree}}

\addplot +[smooth,mark=square] table[x index=0, y 
index=2, col sep=comma] {./media_knn_tempo-jornal.txt};
%\addlegendentry{$Slim^2$\emph{-tree}}

\addplot +[smooth,mark=triangle] table[x index=0, y 
index=1, col sep=comma] {./media_knn_tempo-jornal-slimdown.txt};
%\addlegendentry{$Slim^2$\emph{-tree}+sdw}
\end{axis}
\end{tikzpicture}
%
\begin{tikzpicture}
\begin{axis}[
 ymin=6400,ymax=7200,
 font=\tiny,
 xlabel={\# Correct clips (Simpsons)},
     xlabel style={xshift=0.9ex, yshift=-.5ex, anchor=center,font=\tiny},
 grid=both, 
 legend pos=south east,
 legend style={font=\tiny, at={(2.275 ,0.5)}, anchor=east},
 height=3.3cm, width=4.35cm,
]
%\addplot +[smooth,mark=asterisk] table[x index=0, y index=1, col sep=comma] 
%{./media_knn_tempo-simpsons.txt};
%\addlegendentry{$M^2$\emph{-tree}}

\addplot +[smooth,mark=square] table[x index=0, y 
index=2, col sep=comma] {./media_knn_tempo-simpsons.txt};
%\addlegendentry{$Slim^2$\emph{-tree}}
\addlegendentry{Before \emph{Slim-down}}

\addplot +[smooth,mark=triangle] table[x index=0, y 
index=1, col sep=comma] {./media_knn_tempo-simpsons-slimdown.txt};
%\addlegendentry{$Slim^2$\emph{-tree}+sdw}
\addlegendentry{After \emph{Slim-down}}
\end{axis}
\end{tikzpicture}
}\\[-5pt]
\caption{Average time per class for multimodal $k$-NN search before and after using \emph{Slim-down}.}\label{fig:time-class}
\end{figure*}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\section{Conclusion}\label{sec:conclusion}

\emph{Slim\textsuperscript{2}-tree} is a new multimodal metric tree which enables video indexing and retrieval by using information from multiple modalities. Experimental results have demonstrated its efficiency when compared to other multimodal solutions. Moreover, it also supports queries using only one modality with a computational cost similar to an unimodal solution.
This article explores different strategies related to the use of a \emph{post-processing} algorithm 
for the \emph{Slim\textsuperscript{2}-tree} -- named multimodal \emph{Slim-down}. 
Experiments have also shown the performance improvement obtained by the policy, in which any element that presents the larger distance value to the pivot for any modality is selected as candidate to be moved, i.e., any element which defines at least one of the radii of the hyperregion associated with the node. 
Moreover the results are better when that policy is repeatedly used during insertion.
Future works should address the impact of different \emph{score} functions in the \emph{Slim\textsuperscript{2}-tree} results. Moreover, it is also important to assess the \emph{Slim\textsuperscript{2}-tree} performance when facing an increasing number of modalities and when multiple features of a same modality are used.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%FIM DO TEXTO
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

% INCLUDE BIBLIOGRAPHY WHICH MUST FOLLOW jidm.bst TEMPLATE
\bibliographystyle{jidm}
\bibliography{jidmb}
% For information on how to write bibliography entries, 
% see file jidmb.bib

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{received}
\end{received}

\end{document}
