\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

% 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}}

% 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{3}
\jidmNumber{3}
\jidmYear{12}
\jidmMonth{October}
\setcounter{page}{1}


% Includes headers with simplified name of the authors and article title
\markboth{Santiago A. Nunes et al.}
{JIDM - Journal of Information and Data Management}
%  -> \markboth{}{}
%         takes 2 arguments
%         ex: \markboth{M. M. Moro}{Any article title}


% Title of the article
\title{Finding spatio-temporal patterns in multidimensional data streams}


% 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{Alberto H. F. Laender, Mirella M. Moro}

\author{Santiago A. Nunes\inst{1},
Luciana A. S. Romani\inst{2},
Ana M. H. Avila\inst{3},
Priscila P. Coltri\inst{3},
Agma J. M. Traina\inst{1},
Elaine P. M. Sousa\inst{1}}

%Affiliation and email
%\institute{University of S\~ao Paulo at S\~ao Carlos, Brazil \\ \email{\{nunes, agma, parros\}@icmc.usp.br}
% \and Embrapa Agricultural Informatics - Campinas - Brazil \\    \email{luciana.romani@embrapa.br}
% \and Cepagri - University of Campinas - Brazil \\               \email{\{avila, pcoltri\}@cpa.unicamp.br}

%\institute{Universidade Federal de Minas Gerais, Brazil      \\ \email{\{laender, mirella   \}@dcc.ufmg.br}
\institute{University of S\~ao Paulo at S\~ao Carlos, Brazil \\ \email{\{santiago, agma, parros\}@icmc.usp.br}
\and Embrapa Agricultural Informatics - Campinas - Brazil \\    \email{luciana.romani@embrapa.br}
\and Cepagri - University of Campinas - Brazil \\               \email{\{avila, pcoltri\}@cpa.unicamp.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}
In the last few decades, advances in data acquisition technology have contributed to generation of huge volumes of data in diverse application areas, creating new research challenges in knowledge discovery.
The analysis of these data has become an important task in several domains such as sensor networks, web-logs, financial transactions and climate change monitoring.
In this article, we propose the Spatio-Temporal Behavior Meter (STB-meter) method to identify spatio-temporal patterns in multidimensional evolving data streams.
Our approach combines a multi-resolution hierarchical structure to deal with spatial information with fractal-based analysis to monitor non spatial information of the multidimensional data stream.
Experimental evaluation on real climate data shows that our method allows finding relevant spatio-temporal patterns in evolving data at different spatial and temporal resolutions and therefore it can be a useful tool to assist domain specialists in climate change researches.

\end{abstract}


% ACM Computing Classification System categories
\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{spatio-temporal data, fractals, multi-resolution spatial structure}
%  -> \keywords{} (in alphabetical order \keywords{document processing, sequences,
%                      string searching, subsequences, substrings})


% THE ARTICLE BEGINS
\begin{document}

% This is optional:
\begin{bottomstuff}

%\section*{Acknowledgments}
The authors thank Embrapa, FAPESP, Microsoft Research, CNPq and Capes for the financial support, and Agritempo for the climate data used in this work. 

\end{bottomstuff}

\maketitle


\section{Introduction}

In this century scientists from different fields of knowledge have the challenge of dealing with big data. One reason is the increasing number of data generation environments spatially distributed and interrelated. 
Examples of these environments include different kinds of sensor networks connecting remote sensors, mobiles, RFID, GPS and so on.

Another motivating factor is the improving quality of technological equipments that allow more and more data to be generated or captured in real time. 
This continuous flow of a very large data volume can quickly deplete storage capacity or overload systems. In general, much of these data might be analyzed / monitored continuously without storage. In this scenario, computational techniques that have not been designed to deal with continuous data efficiently may quickly become obsolete.

Therefore, the new generation of algorithms for knowledge discovery should consider new issues, such as space, time and data structure to deal with huge volumes of data. Additionally, the formulation and submission of responses must be faster, as well. The number of mobile devices grows very quickly and information is accessed anytime and anywhere. Also, sensor networks have been deployed to assist in monitoring different aspects of modern life, such as climate, vehicles traffic, and so on. 

A sensor network can involve a large number of different devices, depending on the complexity and extent of territory that it is intended to monitor. Therefore, the computational challenge becomes even greater since it becomes necessary to combine the spatial information to the increasing flow of data. 

The spatio-temporal analysis of data streams can handle a continuous data stream, considering the data reading, timestamp and also the geographic position where the sensor (data source) is located. The algorithms for mining spatio-temporal data streams must run efficiently in order to properly detect recent patterns considering the georeferenced data, representing a new challenge in the knowledge discovery area \cite{Gama:2010:KDD:1855075}. As an example, studies on climate change have imposed several challenges to scientific and governmental communities. Food security and sustainable development are certainly the most important. 
Additionally, terabytes of data are generated during each execution of climate models, depending on the number of parameters employed, which commonly goes up to a few tens of parameters such as temperature, humidity, wind direction and intensity, among others.
According to the last IPCC (Intergovernmental Panel on Climate Change) report, climate change could cause a migration of crops adapted to a specific area to other regions to compensate for alterations on climate conditions. As climate scenarios show different changes in the future, consequences for agricultural production may have greater or smaller impact in different regions.


In this context, we propose the  \textit{Spatio-Temporal Behavior meter} (STB-meter), a method based on a hierarchical data structure to represent multidimensional data streams in order to allow a spatio-temporal assessment. 
The STB-meter's approach integrates representation of spatial information in a hierarchical data structure and the measure of the correlation fractal dimension $D_2$ to detect spatio-temporal patterns and changes in the stream's behavior.

We have conducted experiments on real climate data, such that multiple georeferenced climate time series are represented as a multidimensional data stream - each time series defines an attribute of the stream. Therefore, it is possible to integrate multiple climate variables in a unified analysis process, aiming to detect spatio-temporal patterns, behavior changes and extremes.  Results have shown that the proposed method is effective to detect spatio-temporal variations in data behavior. In particular, experiments performed on data from meteorological sensors located in the state of S\~ao Paulo show that STB-meter allows a spatio-temporal analysis of real data and therefore it is also useful in applied sciences. 

This article is organized as follows: Section \ref{sec:background} presents background concepts and related work. Section \ref{sec:STB} describes the \textit{Spatio-Temporal Behavior meter} method, the approach we propose to conduct a spatio-temporal analysis of multidimensional data streams. Section \ref{sec:experiments} details experimental results on real climate data and Section \ref{sec:conclusions} presents final remarks.

\section{Background and Related Work}\label{sec:background}

The method we propose in this work integrates fractal-based analysis with a multi-resolution, hierarchical data structure in order to support spatio-temporal analysis of evolving data streams. Thus, this section provides an overview of concepts from the Fractal Theory applied to data analysis, spatio-temporal issues and related work. 

A fractal is a self-similar object, i.e., it presents roughly the same characteristics over a large range of scales \cite{Schroeder:1991}. A well-known example of fractal is the Sierpinski Triangle, illustrated in Figure \ref{fig:fractals}a. Fractal behavior is also observed in nature and real datasets, as illustrated in Figures \ref{fig:fractals}b and c.  
A real dataset exhibiting fractal behavior is exactly or statistically self-similar, such that parts of any size of the data present the same general characteristics of the whole dataset. In fact, Faloutsos and Kamel \cite{DBLP:conf/pods/FaloutsosK94} show that most of the real datasets exhibit fractal behavior.    

\begin{figure} [ht]
  \centering
  \includegraphics[width=0.8\textwidth]{fig/Fractais.png}
  \caption{Examples of Fractals: a) geometric fractal; b) fractal in nature; c) real fractal dataset.}
  \label{fig:fractals}
\end{figure}

The fractal dimension, in particular the Correlation Fractal Dimension $D_2$, is a useful tool for data analysis, as it provides an estimate of the intrinsic dimension $D$ of real datasets. The intrinsic dimension gives the dimensionality of the object represented by the data regardless of the dimension $E$ of the space in which it is embedded \cite{DBLP:conf/pods/FaloutsosK94,Traina:05}. For instance, a set of points defining a line embedded in a three-dimensional space ($E=3$) has all its attributes correlated, resulting in $D=1$.    

A well-known approach to measure the fractal dimension of datasets embedded in $E$-dimensional spaces is the \textit{Box-Counting} method \cite{Schroeder:1991}, which defines $D_2$ as presented in Equation \ref{eq:CFD}:

\begin{equation}\label{eq:CFD}
       D_2 \equiv \frac{\partial log (\sum_i C^{2}_{r,i})}{\partial log(r)} \ \ \ \ \
       r \in [r_1,r_2]\\
\end{equation}

\noindent
where $r$ is the side of the cells in a (hyper) cubic grid that divides the address space of the dataset and $C_{r,i}$ is the count of points in the $i$th cell.
 
Based on the Box-Counting method, Traina et al. \cite{DBLP:conf/sbbd/TrainaTWF00} proposed a $O(N)$ algorithm (N is the number of elements in the dataset) to compute $D_2$. 
The main strategy of the algorithm is the construction of a hierarchical data structure (\textit{counting tree}) to map a multi-resolution hyper-grid dividing the address space of the dataset. Each level of this hyper-grid has a radius $r$ which is a fraction of the previous level, i.e., in the first level the grid has a radius $r$, in the second level the grid has radius of $r/2$ and so on. The counting of incident points is accomplished in each cell of the hyper-grid as we can see in Figure \ref{fig:counting}. The \textit{counting tree} supports fast counting of points for different values of $r$ (see \cite{DBLP:conf/sbbd/TrainaTWF00} for details). Thus, $D_2$ can be a useful tool to estimate the intrinsic dimension $D$ of real datasets with feasible computational cost.

\begin{figure} [t]
  \centering
  \includegraphics[width=0.6\textwidth]{fig/CountingTree.png}
  \caption{Five points of a bi-dimensional dataset represented in a bi-dimensional grid and the corresponding \textit{counting tree}.}  
  \label{fig:counting}
\end{figure}

Concepts from the Fractal Theory have been applied to several tasks in data mining and data analysis, such as selectivity estimation \cite{Bohm:00a} \cite{Faloutsos:00,DBLP:conf/ssdbm/BaiocoTT07}, clustering \cite{DBLP:reference/dmkdh/BarbaraC10,Cordeiro2013}, time series forecasting \cite{DBLP:conf/cikm/ChakrabartiF02}, correlation detection \cite{DBLP:journals/datamine/SousaTTWF07}, data distribution analysis \cite{Traina:05}, among others.  

The information of intrinsic behavior provided by the fractal dimension can also be applied to detect temporal patterns and changes in evolving data streams.  Essentially, the idea is to continuously measure the fractal dimension of the data stream over time in order to monitor its evolving behavior. Thus, significant variations in successive measures of the fractal dimension can indicate changes in the intrinsic characteristics of the data and temporal patterns. 

Sousa et al. \cite{deSousa:2007:MED:1553698.1553701} propose a technique and the algorithm \textit{SID-meter} to continuously measure the fractal dimension $D_2$  over time and track behavior changes of evolving data streams. The \textit{SID-meter}'s approach deals with a data stream as a potentially unbounded, implicitly ordered sequence of events $<e_1, e_2, ... >$, such that each event is represented by an array of $E$ measures (attributes). 
A sliding window bounds recent, successive events to be considered into the calculation of $D_2$. As new events come, oldest events are forgotten. Therefore, the value of $D_2$ is continuously computed for the events inside the window and updated whenever new events are available. 
The window is divided into $n_c$ periods where each period is defined by a predetermined number of events or units of time ($n_i$). Hence, $n_c \times n_i$ gives the size of the window and $n_i$ determines its update interval. Both $n_c$ and $n_i$ are user-defined parameters. Figure \ref{fig:window} illustrates a sliding window over a three-dimensional data stream - attributes $a_1$,$a_2$ and $a_3$ - and the fractal dimension $D_2$ measured at times $t$ and $t+1$. Notice that the window has five periods ($n_c = 5$), each one corresponding to a unit of time $n_i = 1$. 

\begin{figure} [t]
  \centering
  \includegraphics[width=0.9\textwidth]{fig/sliding_window.png}
  \caption{A sliding window over a three-dimensional data stream used to measure fractal dimension at time $t$ and time $t+1$, respectively: a) $D_{2_{(t)}}$; and b) $D_{2_{(t+1)}}$}  \label{fig:window}
\end{figure}

\textit{SID-meter} is also based on a \textit{counting tree} tuned to support important requirements of a data stream environment, mainly: single pass on data, events processed (counted) only once and updated responses. 

The fractal-based approach, as discussed herein, can be applied to temporal analysis of data streams. However, in several data stream environments, data includes spatial information related to its generators. The spatial characteristics and relationships may be meaningful for data analysis and mining tasks. Moreover, by dealing with spatial properties in addition to temporal information it is possible to conduct data stream analysis   from the spatio-temporal perspective. In this context, some work has been done, for instance, on stream modeling and trend mining \cite{Meng:06}, clustering on sensor networks \cite{Yoon:2007} and spatio-temporal continuous query processing \cite{Mokbel:08}. 

%Não necessariamente uma quadtree, o necessário é que seja uma estrutura hierarquica
In this article, we propose a technique for spatio-temporal analysis of data streams which combines the temporal information provided by the fractal-based approach with spatial indexing provided by a hierarchical data structure \cite{Samet:1984:QRH:356924.356930}.  
%

Hierarchical data structures are of major importance as a tool in several computational techniques, from image processing to geographic information systems. These structures are based on recursive decomposition of the data space and therefore allow focus on subsets of the original dataset. Several research papers have proposed indexing structures to represent points in space, regions, curves, surfaces and volumes (see \cite{Gaede:98} and \cite{Bohm:01} for surveys). In this work we have used a quadtree like structure as our hierarchical data structure, but it is worthy to highlight that the proposed method can be implemented with any hierarchical data structure to represent spatial attributes. 

\section{The Spatio-Temporal Behavior meter}\label{sec:STB}

The main idea of the STB-meter is to continuously measure the fractal dimension $D_2$ of multidimensional data streams considering the spatial aspects of the data. For this purpose, we developed a data structure called STB-tree that allows the calculation of fractal dimension for different subsets of data based on their spatial information.

The STB-tree is built by associating a counting tree to a hierarchical data structure. In this work, we have used a quadtree like structure extended to any dimensionality.
 
\begin{table}[htb]
  \caption{Example of a sequence of events that compose a data stream.} \label{tab:datastream}
  \begin{center}
    \begin{tabular}{|c|c|}  \hline
      Events  & Attributes  \\\hline
      {$e_1$} & \{1,1,4,8\} \\\hline
      {$e_2$} & \{4,4,5,8\} \\\hline
      {$e_3$} & \{7,7,8,2\} \\\hline
      {$e_4$} & \{8,6,6,3\} \\\hline
      {$e_5$} & \{7,5,4,5\} \\\hline
    \end{tabular}
  \end{center}
\end{table}

The building process of the STB-tree requires prior knowledge about which attributes are the spatial attributes, as they are used to construct the hierarchical data structure. The non-spatial attributes are used to construct a counting tree, following an approach similar to the method SID-meter aforementioned.

The STB-tree integrates the hierarchical data structure with a counting tree modified to attend an indexing that depends on the subregion of the hierarchical data structure to which it is associated as well as the addressing defined by the non-spatial attributes. In other words, each level contains a set of subregions of the hierarchical data structure and each of these subregions contains a set of cells of the counting tree.

The cell indexing of the counting tree depends on the subregion of the hierarchical data structure to which they are related as well as their non-spatial attributes. In the same manner, indexing each subregion of the hierarchical data structure depends on the counting tree cell to which it is associated as well as its spatial attributes.

For illustration purposes, Table \ref{tab:datastream} presents a dataset containing 5 events where the first two attributes represent spatial information while the other two contain non-spatial information.

The STB-Tree is built according to the following steps:

\begin{enumerate}
 \item First define which attributes are spatial and non-spatial
 \item To each new event of data stream, split spatial attributes from non-spatial attributes
 \item Use spatial attributes to identify the subregion of the space represented by hierarchical structure
 \item \label{item:ini} In this subregion of the hierarchical structure use the non-spatial information to identify the counting tree cell corresponding to the subregion of the hierarchical structure
 \item Increment the cell's counter
 \item Use the spatial information to identify the hierarchical data structure subregion corresponding to the counting tree cell
 \item Repeat this process from step \ref{item:ini} recursively until the desired depth is reached in the STB-Tree
\end{enumerate}

Figure \ref{fig:STBTree} shows a STB-tree with depth 3 for the events shown in Table \ref{tab:datastream}. We can see the representation of spatial attributes on a quadtree as well as the representation of non-spatial attributes.
For each level in the quadtree, one cell list is created in order to identify the position of the event in the counting tree of non-spatial attributes.

Thus, as it can be seen in Figure \ref{fig:STBTree}, the event $e_1$ showed in Table \ref{tab:datastream} has its spatial information defined in the values \{1,1\} and its non-spatial information defined in the values \{4,8\}. With the spatial information, initially the subregion $01$ of  the hierarchical structure is found. The algorithm then searches for the corresponding cell in the counting tree associated to that subregion. In Figure \ref{fig:STBTree} we can verify that the counting tree cell is addressed in the index $00$.

Analogously, the spatial information of event $e_5$ (\{7,5\}) is addressed in the subregion $10$ of the hierarchical structure, and its non-spatial information (\{4,5\}) is also addressed in a cell $00$ of the counting tree. However, as the spatial location of event $e_5$ differs from the location of event $e_1$, its contribution in the counting tree occurs in the cell $00$ that is related to subregion $10$ of the hierarchical structure.

This process is performed for all events in the dataset to be analyzed. Whenever a new event is inserted into the STB-Tree, the appropriate counter $C$ is incremented, in order to store a count of events considering the spatial and non-spatial aspects of the dataset.
To perform the calculation of fractal dimension of a particular region of the hierarchical structure, Equation \ref{eq:CFD} is used with the counting of the nodes of the STB-tree. Through STB-Tree it is possible to perform the counting of  hierarchical subregions by accomplishing only one reading of each event.

Once data streams are potentially infinite and due to their evolving nature, we have used an approach based on sliding windows.
The STB-tree has thus been extended to support a continuous analysis of multidimensional data streams, following the SID-meter strategy of setting parameters $n_c$ and $n_i$ to respectively define the number of counting periods and the number of events (or units of time) per each counting period.

The parameters $n_c$ and $n_i$ determine the temporal granularity used in the analysis, and therefore are strongly dependent on the type of analysis to be performed. For instance, if the analysis focuses on the events that occur monthly, an oversized window can smooth changes in the monthly behavior. On the other hand, if the size of the window is underestimated then behavior changes may not be detected. Previous work  \cite{DBLP:journals/jidm/NunesRATST11} shows that windows of different sizes detect different events, such as El Niño and La Niña. 

In order to enable a more complex analysis of the data, the sliding window based approach was extended such that parameters $n_c$ and $n_i$ receive a range of values. Based on these ranges, the minimum and maximum number of counting periods are computed so it is possible calculate the fractal dimension for any combination of $n_c$ and $n_i$ in the ranges defined by the user.

\begin{figure} [ht]
  \centering
  \includegraphics[width=1\textwidth]{fig/stbtree.png}
  \caption{STB-tree corresponding to the events shown in Table \ref{tab:datastream}.}
  \label{fig:STBTree}
\end{figure}

For this purpose, the STB-tree has also been extended so that each counter $C$ uses an array to store the counts for each counting period. 
When the number $n_i$ of events arrive, the counters corresponding to $n_i$ oldest events are discarded and start to consider only the $n_i$ new events.

Figure \ref{fig:STBTreeSlidingWindow} illustrates the extended node of the STB-tree, with $n_c$ ranging from 1 to 3 and $n_i$ ranging from 30 to 120. In this example, it is possible to compute the fractal dimension for any combination of $n_c \subset \{1,2,3\}$ and $n_i \subset \{30, 60, 90, 120\}$. For instance, given $n_c = 2$, $n_i = 60$ and the current $n_c$ counter positioned at $7$, the count on the node will consider $C[4], C[5], C[6]$ and $C[7]$ to calculate the fractal dimension.

\begin{figure} [ht]
  \centering
  \includegraphics[width=0.7\textwidth]{fig/stbCounting.png}
  \caption{STB-Tree Node extended to support sliding windows.}
  \label{fig:STBTreeSlidingWindow}
\end{figure}

By using the STB-tree structure, the STB-meter method was developed to allow the continuous calculation of fractal dimension on different subsets of data.
This method allows an analysis in multiple spatial resolutions as well as different temporal granularities, performing only one reading of each event in the data stream.

The output of the method are values of the fractal dimension $D_2$ calculated over time for each subregion represented in the hierarchical data structure, from the smallest subregions until it encompasses all the points represented.
Analysis of these results allows to identify behavior changes in each subregion of the space and to find patterns, differences and similarities among the subregions over time.

The combined analysis of multidimensional data streams considering spatial and temporal aspects of the data set can be useful in detecting patterns and extreme events occurring in different regions and in different situations.

\section{Experimental Results}\label{sec:experiments}

To evaluate the STB-meter method, experiments were performed using synthetic data streams constructed so that each region of the data set presents a specific known behavior. This set of synthetic data was projected to assess whether the STB-Meter can calculate correctly the fractal dimension of different subregions in space. Thus, each subregion of space in this dataset contains non-spatial attributes correlated in order to detect different values of correlation in each region.

Another goal of this synthetic set is performed tests in multiple levels in order to verify it is possible find behavior different from general behavior of dataset. For instance, a region presents a specific fractal dimension and subregions which compose it presents a fractal dimension that differs it from that.

Figure \ref{fig:syntAllRegion} illustrates the arrangement of built synthetic dataset containing two spatial attributes and four non-spatial attributes.

\begin{figure} [ht]
  \centering
  \includegraphics[width=0.25\textwidth]{fig/syntAllRegion.png}
  \caption{Correlation of synthetic data regions.}
  \label{fig:syntAllRegion}
\end{figure}

\begin{table}[htb]
  \caption{Arrangement of synthetic dataset in each region.} \label{tab:SynData}
  \begin{center}
    \begin{tabular}{|c|c|}  \hline
      Spatial Index  & $D_2$  \\\hline
      {00} & 1 \\\hline
      {01} & 2 \\\hline
      {10} & 3 \\\hline
      {11} & 4 \\\hline
    \end{tabular}
  \end{center}
\end{table}

This dataset contains 36000 events such that in region \textbf{00} all non-spatial attributes are correlated, then the fractal dimension expected to this region is $D_2 = 1$.

In the region \textbf{01} spatial attributes are divided into two subregions as illustrated in Figure \ref{fig:synt00Region}, where subregion 00 contains pairs of correlated attributes, generating a fractal dimension $D_2 = 2$ and subregion \textbf{11} contains attributes without any correlation, with a fractal dimension $D_2 = 4$. 

In region \textbf{10} only two non-spatial attributes are correlated, therefore, fractal dimension of this region is $D_2 = 3$ and in region \textbf{11} no non-spatial attribute is correlated, being $D_2 = 4$.

\begin{figure} [ht]
  \centering
  \includegraphics[width=0.5\textwidth]{fig/synt00Region.png}
  \caption{Correlation of subregions of the region \textbf{01}.}
  \label{fig:synt00Region}
\end{figure}

Over this dataset the STB-meter method was parameterized using windows divided into 10 counting periods where each period contains 2,400 events, i.e. $n_c = 10$ and $n_i = 2,400$, and uses a tree with deep equal to 21, i.e., $R = 21$.
Results are illustrated in Figure \ref{fig:D2_all.png} where it is possible to identify the different behavior of each region and how each region differently adds information regarding the entire dataset.
The fractal dimension correlation calculated by the STB-meter method corresponds to the expected correlation for each region of the synthetic data set as presented in table \ref{tab:SynData}.

\begin{figure} [ht]
  \centering
  \includegraphics[width=1\textwidth]{fig/D2_all.png}
  \caption{Fractal dimension of synthetic data regions.}
  \label{fig:D2_all.png}
\end{figure}

Similarly, region \textbf{01} can be divided into four subregions, as shown in Figure \ref{fig:synt00Region}.
In this subset with fractal dimension $D_2 = 2$, the same analysis was performed using the STB-meter and the results are shown in Figure \ref{fig:D2_00.png}.
We can verify that the behavior of the subregions of the region \textbf{01} is according to the expected fractal dimension as shown in Figure \ref{fig:synt00Region}.

\begin{figure} [ht]
  \centering
  \includegraphics[width=1\textwidth]{fig/D2_00.png}
  \caption{Fractal dimension of region \textbf{00}.}
  \label{fig:D2_00.png}
\end{figure}

In order to evaluate the STB-meter method with real data, we conducted an experimental study using data streams composed of climatological time series obtained from a network of weather stations with 24 meteorological stations located in the state of S\~ao Paulo, Brazil \footnote{Provided by Agritempo - www.agritempo.br}. Data streams are composed of daily measurements of average temperature and precipitation from 1961 to 1990, and the latitude and longitude of each station.

The method was parameterized to use a three-month sliding window, i.e., $n_c = 3$ and the parameter refresh rate was defined as monthly ($n_i = 30$). 
In order to compute the fractal dimension of the subsets indexed in the STB-tree, we defined queries reaching until the third level. 

The STB-tree indexes data for the recent 3 months of the stream; the fractal dimension is then computed at each month using the counting trees of the leaf nodes and aggregating them until the fractal dimension of the highest levels is calculated.

Figure \ref{fig:quadtree} presents a hierarchical data structure (quadtree like) built on the spatial information from 24 meteorological stations in the state of S\~ao Paulo. 

\begin{figure} [!ht]
  \centering
  \includegraphics[width=0.5\textwidth]{fig/quad_maps.png}
  \caption{Quadtree built on the latitudes and longitudes of the 24 meteorological stations of the state of S\~ao Paulo.}
  \label{fig:quadtree}
\end{figure}

\begin{figure} [!ht]
  \centering
  \includegraphics[width=0.8\textwidth]{fig/niveis_all.png}
  \caption{Fractal dimension for all subsets.}
  \label{fig:all}
\end{figure}

Thus, results obtained are series of $D_2$ varying from local behavior of each data subset until the global behavior of the data set.
These results may be visualized in Figure \ref{fig:all} where all the graphs of the variation of the fractal dimension for all 3 levels of query on the quadtree are presented.

Figures \ref{fig:NO}, \ref{fig:SE} and \ref{fig:SO} show respectively the fractal dimension of the data sets of quadtree for Northwest, Southeast and Southwest regions. 
The Northeast region was not considered because it contains only one point, having no representation in the general behavior of the data set.

\begin{figure} [!ht]
  \centering
  \includegraphics[width=0.8\textwidth]{fig/ROOT_ROOT-NO.png}
  \caption{Both fractal dimension from the Northwest and the state of S\~ao Paulo.}
  \label{fig:NO}
\end{figure}

\begin{figure} [!ht]
  \centering
  \includegraphics[width=0.8\textwidth]{fig/ROOT_ROOT-SE.png}
  \caption{Both fractal dimension from the Southeast and the state of S\~ao Paulo.}
  \label{fig:SE}
\end{figure}

\begin{figure} [!ht]
  \centering
  \includegraphics[width=0.8\textwidth]{fig/ROOT_ROOT-SO.png}
  \caption{Both fractal dimension from the Southwest and the state of S\~ao Paulo.}
  \label{fig:SO}
\end{figure}

The resulting series of fractal dimension suggest that the Southeast is less influenced by extreme events than other regions of the state of S\~ao Paulo.
The highlighted regions in the figures are periods of low correlation between the variables that compose the data set, i.e., low correlation between precipitation and temperature. According to specialists, those periods are related to extreme climate events resulting from El Ni\~no \cite{DBLP:journals/jidm/NunesRATST11}. It is possible to see that this extreme occurs differently in each subregion.

In these analyses we observed that although precipitation shows more variation than temperature, the algorithm also detected important difference in temperature average, showing that this methodology can detect from small to extreme events of climatic variation. Nowadays, this is relevant, especially in climate change analyses and detection. In addition, this result is also very useful in agrometeorology science. Agricultural production is highly vulnerable to climate variations, and can be considered as the most weather-dependent of all human activities. %(Oram 1989; Hansen 2002). 
Small variations in temperature (witch normally is difficult to observe in most of analyses) can cause significant losses in yield.  In this context, detection of climate variation and extreme climate events is vital to predict and monitor yield. 

Analyzing the variation of fractal dimension for different subregions of the data set, it is possible to evaluate the behavior of climate variables over time, for different regions of the state of S\~ao Paulo.
That analysis allows the specialist to understand how each subregion of the dataset behaves, helping to identify patterns of behavior spatial and temporal climate, as well as understand how each subregion reacts to a specific event.

\section{Conclusions}\label{sec:conclusions}

In this article we present the \textit{STB-meter}, a new method for spatio-temporal analysis of multidimensional data streams. Our approach combines fractal-based analysis to monitor temporal behavior with a multi-resolution, hierarchical structure to deal with spatial properties. Moreover, \textit{STB-meter} handles multidimensional data streams with a single pass on data and feasible computational cost.
  
Experimental results on synthetic data and real climate data show that our solution is able to spot spatio-temporal behavior patterns, especially anomalies such as  extreme climate events. Furthermore, it supports a multi-resolution analysis of temporal and spatial properties as well. 

Results show that STB-meter can identify important patterns and extreme events in climate data.
This framework is very useful in applied sciences, as agrometeorology and climatology, especially climate change applied to agriculture. Temperature and precipitation are important variables in agricultural analyses, but the huge volume of available data makes the work of specialists very difficult. 
Once the climate patterns can be identified quickly and easily, specialists have an important tool to monitor and predict yield, in present and future climate conditions.

As future work, we intend to apply the method to other application domains, performing experiments with other data sets. Another relevant point to be explored is to use other hierarchical (spatial) data structures according to the characteristics of the data to be analyzed.
	
% INCLUDE BIBLIOGRAPHY WHICH MUST FOLLOW jidm.bst TEMPLATE
\bibliographystyle{jidm}
\bibliography{refs}
% For information on how to write bibliography entries, 
% see file jidmb.bib

\begin{received}
\end{received}

\end{document}
