\section{Performance Evaluation}
\label{sec:experimentalEvaluation}

The advantages of our proposed solutions (that is, the \name\ ADT and the \nameimp\ improvement) were analyzed through experimental tests that process spatial queries with vague topological predicates. We analyze topological predicates since they incur high costs of processing and they are very common in spatial applications. Section~\ref{subsec:experimentalSetup} introduces the experimental setup used in the performance evaluation. Section~\ref{subsec:srq} and Section~\ref{subsec:sj} discusses the performance results of execution of vague spatial range queries and vague spatial joins, respectively.

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

\subsection{Experimental Setup}
\label{subsec:experimentalSetup}

We used the data sets $D_1$ and $D_2$. $D_1$ was composed of 100,000 vague region objects synthetically generated as follows. First, we constructed a Voronoi diagram on of 200,000 crisp points randomly generated, which produced the same number of crisp regions. Second, for each crisp region, we added more points to increase its complexity. As a result, each crisp region was formed by averagely 313 points. Third, we created pairs of crisp regions that were disjoint or adjacent. Each pair was created by selecting randomly a crisp region and then by selecting the nearest crisp region that was disjoint or adjacent to the first one. We randomly assigned a crisp region as the kernel and the other crisp region as the conjecture, which formed a vague region object. After creating a pair, we discarded the used regions, such that these regions were not used to create another pair. In the total, we generated 100,000 vague region objects in order to compute vague spatial range queries. The same process was used to create the data set $D_2$; but, instead of 100,000 vague region objects, two sets of 10,000 vague region objects were created in order to compute vague spatial joins between them.

We computed two type of spatial queries, vague spatial range queries and vague spatial joins. For the vague spatial range queries, we considered the following predicates: \emph{vague disjoint}, \emph{vague overlap}, \emph{vague inside}, \emph{vague intersects}, \emph{vague coveredBy}, and \emph{vague meets}. The workload was composed of 100 vague spatial range queries for each vague topological predicate. We also defined a query window for each vague spatial range query, which was composed of a vague region object that had the rectangular format for the kernel and the conjecture. Therefore, we randomly generated 100 different query windows. For the vague spatial joins, we considered the following predicates: \emph{vague disjoint}, \emph{vague overlap}, \emph{vague inside}, \emph{vague coveredBy}, and \emph{vague meets}.

We defined the following configurations: (i) \baseline\ that used current functionalities provided by the PostgreSQL with the PostGIS spatial extension; (ii) \nametest\ that used the proposed \name\ ADT without improvements; and (iii) \nameimptest\ that used \name\ empowered with the proposed \nameimp\ improvement. For the \baseline\ configuration, we implemented vague topological predicates by using the Procedural Language/PostgreSQL (PL/pgSQL), which had ``TRUE'', ``FALSE'', or ``MAYBE'' as possible return textual values. For their use, we stored the kernel and the conjecture of each vague spatial object in separated columns in a relational table.

Note that we did not employ the approaches surveyed in Section~\ref{sec:relatedWork} here due to the following limitations. While the approaches proposed in~\citeN{Zinn07VLDB}, \citeN{Krai04Thesis}, \citeN{Dilo06FDSIU}, and \citeN{Carn15GeoInfo2} \emph{do not provide support for vague topological predicates}, the approaches described in~\citeN{PaulySch08QASDM} and \citeN{PaulySch10IS} are \emph{specifically implemented in Oracle}, which has license restrictions. Further, we used PostgreSQL in the performance tests to isolate the effects of the DBMS, and thus providing a fair comparison.

Table~\ref{tab:template} depicts the SQL templates of the vague spatial range queries and vague spatial joins used in the three configurations. Consider the template for the \baseline. \emph{baselineTable}, \emph{baselineTable1}, and \emph{baselineTable2} are tables composed of three attributes: (i) \emph{id} that is the primary key, (ii) \emph{kernel\_geo} that represents the kernel of a vague region object, and (iii) \emph{conjecture\_geo} that represents the conjecture of a vague region object. Further,~$R$~is the textual return value that may contain ``TRUE'', ``FALSE'', or ``MAYBE'' and~$P$~is the vague topological predicate. For vague spatial range queries,~$QW$~is the query window. Regarding the \nametest\ and the \nameimptest\ configurations, \emph{vaguegeom}, \emph{vaguegeom1}, and \emph{vaguegeom2} are tables that stored vague region objects in the attribute \emph{vg} by using our proposed \name. In addition, $O$ corresponds to the use of the SQL operators introduced in Section~\ref{subsec:nativeSQL}. This means that the operator~$\sim\sim$~was used to specify that $P$ returned maybe, the operator $\&$ was used to specify that $P$ returned true, and the combination of the operator $\&$ with the operator $!$ (that is, $\&!$) was used to specify that $P$ returned false. Note that the SQL templates are equivalent for each type of query, that is, they generate the same result, but using the specific functionalities provided by the corresponding configurations.

\begin{table}[tb]
	\begin{center}
	\caption{\label{tab:template} SQL templates of the vague spatial range queries and vague spatial joins.}
		\begin{tabular}{m{2.5cm}@{\hspace{1mm}}  m{4.6cm}@{\hspace{3mm}}  m{7.5cm}}
		\toprule
        &                                       \multicolumn{2}{c}{\textbf{SQL Template}}\tabularnewline
		\centering\textbf{Configuration}	&	\centering\textbf{Vague Spatial Range Query} &	\centering\textbf{Vague Spatial Join}\tabularnewline
       \midrule
	   \centering\baseline		 &	{\small \texttt{SELECT id \newline FROM baselineTable \newline
									WHERE \textit{R} = \textit{P}(kernel\char`_geo, conjecture\char`_geo, $QW_k$, $QW_c$)}} & {\small \texttt{SELECT A.id, B.id \newline FROM baselineTable1 as A, baselineTable2 as B \newline WHERE \textit{R} = \textit{P}(A.kernel\char`_geo, A.conjecture\char`_geo, B.kernel\char`_geo, B.conjecture\char`_geo)}}\tabularnewline
\vspace{0.05cm}										
			\centering\nametest\  \nameimptest &	\vspace{0.1cm}{\small \texttt{SELECT id \newline FROM vaguegeom \newline WHERE \textit{O} \textit{P}(vg, $QW$)}} & \vspace{0.1cm}{\small \texttt{SELECT A.id, B.id \newline FROM vaguegeom1 as A, vaguegeom2 as B \newline WHERE \textit{O} \textit{P}(A.vg, B.vg)}}\tabularnewline
   \bottomrule 			
		\end{tabular}
	\end{center}
\end{table}

The experiments were conducted on a computer with an Intel$^\circledR$ Core\textsuperscript{TM} i7-4770 processor with frequency of 3.40GHz, 2 TB SATA hard drive with 7200 RPM, and 32 GB of main memory. The operating system was CentOS 6.5 with Kernel Version 2.6.32-431.el6.x86 64. We employed PostgreSQL 9.3.3, PostGIS 2.2.0, and GEOS 3.4.2.% GEOS is used by PostGIS and \name\ for the computation of spatial operations, such as crisp 9-intersection matrices.

We collected the elapsed time in seconds. In detail, we executed 100 vague spatial range queries for each vague topological predicate and each value of return. Further, we executed each vague spatial range query and vague spatial join 10 times and calculated their average elapsed time. Furthermore, we performed the tests locally to avoid network latency and we flushed the system cache after the execution of each query.

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

\subsection{Execution of Vague Spatial Range Queries}
\label{subsec:srq}

This experimental evaluation was conducted on data set $D_1$ and its results are reported in Figure~\ref{fig:resultsvsr}. For each configuration and each return value of the three-valued logic (that is, true, false, and maybe), we gathered similar elapsed times for processing the spatial queries. This means that the performance results showed a similar complexity for each return value.

Clearly, the performance of the \nametest\ configuration overcame the \baseline\ configuration. In fact, the internal structures of the \name\ were more efficient than the definition of vague topological predicates by using current functionalities of the spatial DBMS. The performance gain imposed by the \nametest\ configuration over the \baseline\ configuration ranged from 23\% up to 53\%, where the performance gain is calculated as the percentage that determines how much more efficient one configuration was than another configuration.

\begin{figure}[t]
	\begin{center}
		\begin{tabular}{c@{\hspace{1mm}}c@{\hspace{1mm}}c}			
			\hspace{-0.3cm}\begin{tabular}{c}
				\includegraphics[scale=0.26]{figs/vspatialrange_true}
			\end{tabular}
			&
			\begin{tabular}{c}
				\includegraphics[scale=0.26]{figs/vspatialrange_false}
			\end{tabular}
            &
            \begin{tabular}{c}
				\includegraphics[scale=0.26]{figs/vspatialrange_maybe}
			\end{tabular}\\
			(a) & (b) & (c)
		\end{tabular}
		\caption{\label{fig:resultsvsr} Performance results of the execution of vague spatial range queries for each vague topological predicate considering the returning values of true (a), false (b), and maybe (c).}
	\end{center}
\end{figure}
%
\begin{figure}[t]
	\begin{center}
		\begin{tabular}{c@{\hspace{1mm}}c@{\hspace{1mm}}c}			
			\hspace{-0.3cm}\begin{tabular}{c}
				\includegraphics[scale=0.26]{figs/vspatialjoin_true}
			\end{tabular}
			&
			\begin{tabular}{c}
				\includegraphics[scale=0.26]{figs/vspatialjoin_false}
			\end{tabular}
            &
            \begin{tabular}{c}
				\includegraphics[scale=0.26]{figs/vspatialjoin_maybe}
			\end{tabular}\\
			(a) & (b) & (c)
		\end{tabular}
		\caption{\label{fig:resultsvsj} Performance results of the execution of vague spatial joins for each vague topological predicate considering the returning values of true (a), false (b), and maybe (c).}
	\end{center}
\end{figure}

Despite the expressive performance gains obtained by the \nametest\ configuration, we gathered yet better results with the improvement proposed in Section~\ref{sec:improvement}. The \nameimptest\ configuration leaded to a performance gain that ranged from 72\% up to 84\% if compared with the \baseline\ configuration.
Further, compared to the \nametest\ configuration, the \nameimptest\ configuration provided a performance gain that ranged from 63\% up to 66\%. This means that the use of the \nameimp\ improvement drastically reduced the necessity of processing crisp 9-intersection matrices in vague topological predicates.

Regarding storage space, the \baseline\ configuration required 961~MB, the \nametest\ configuration required 960 MB, and the \nameimptest\ configuration required 963~MB. We can conclude that the storage cost were almost the same. In addition, the storage of the MBRs of the kernel and the conjecture of each \name\ object in the \nameimptest\ configuration did not introduce overhead in the execution of the spatial queries.

\subsection{Execution of Vague Spatial Joins}
\label{subsec:sj}

This experimental evaluation was conducted on data set $D_2$ that stored two sets of 10,000 vague region objects. Figure~\ref{fig:resultsvsj} depicts the performance results. Similarly to the discussed results in Section~\ref{subsec:srq}, we obtained similar elapsed times for processing the spatial queries for each return value (that is, true, false, and maybe).

Again, the performance of the \nametest\ configuration greatly overcame the \baseline\ configuration. The performance gain imposed by the \nametest\ configuration over the \baseline\ configuration ranged from 21\% up to 58\%. The performance gain is increased when \nameimptest\ is considered. By using the improvement proposed in Section~\ref{sec:improvement}, we obtained an expressive performance gain of at least 98\% if compared with the \baseline\ configuration. If we compare the \nametest\ and \nameimptest, the \nameimptest\ configuration provided a performance gain that ranged from 96\% up to 97\%. This means that the use of the \nameimp\ improvement is highly recommended in the vague spatial join processing since it drastically avoided the computation of crisp 9-intersection matrices in vague topological predicates. Moreover, each configuration required approximately 194~MB to store the data set $D_2$, which indicates that \nameimptest\ did not introduce overhead in the storage and it guaranteed the best obtained results.
