%---------------------------------------PROPOSED STRATEGIES-----------------------------------------------
\vspace{-0.2cm}
\section{PROPOSED STRATEGIES}

In this article we propose two strategies for mining user contextual preferences in the stream setting: the \textit{Greedy Strategy} and the \textit{Heuristic Strategy}. %In these strategies, we adapted the \textit{Bayesian Preference Network} \cite{ictai2012} concept to the stream setting, as explained in Section \ref{sec:problemformalization}. %All strategies will utilize the concept of \textit{degree of dependence between a pair of attributes} defined in \cite{ictai2012} to build the graph of network preferences.

%Com o intuito de economizar memória e tempo de processamento, esta estratégia mantém apenas \textit{estatísticas suficientes} do stream de preferências $S$ que recebe como entrada. Dessa forma, o treinamento do modelo consiste em atualizar suas estatísticas suficientes a cada novo elemento que chega no stream. O modelo induzido por esta estratégia mantém estatísticas suficientes para cada atributo do esquema relacional $R$ referente a $S$. O conteúdo das estatísticas está principalmente relacionado com o domínio do atributo ao qual as mesmas pertencem. A cada bitupla temporal $l = (u_1,u_2,t)$ utilizada no treinamento do modelo, primeiramente é computado $\Delta (u_1,u_2)$, que é o conjunto de atributos onde $u_1$ e $u_2$ diferem. Apenas os atributos deste conjunto terão suas estatísticas atualizadas de acordo com $l$. A atualização basicamente consiste na computação dos possíveis contextos em $l$ referentes a preferência particular de cada atributo em $\Delta$.

In order to save processing time and memory, in both strategies we do not store the elements of the preference stream processed so far,
we just collect \textit{sufficient statistics} from it.
%in a online way.
% The sufficient statistics reflect the minimum information required to represent the preference stream. With updated statistics, all further processing of our strategies will be made on them, and not on the elements of the stream.
  Thus, the training of the model is made by online updating its sufficient statistics for every new element that comes in the stream. %The model maintain statistics for each attribute of the preference stream $S$. 
  Example \ref{ex:sufstatis} illustrates the sufficient statistics collected from a preference stream $S$.


 %The model induced by these strategies maintain statistics for each attribute of the relational schema $R$ related to $S$. The contents of the statistics is mainly related to the domain of the attribute to which they belong. Aiming to update the statistics, on every temporal bituple $l = (u_1,u_2,t)$ used for model training is first computed $\Delta (u_1,u_2)$, which is the set of attributes where $u_1$ and $u_2$ differ. Only the attributes of this set will have their statistics online updated according to $l$. The update basically consists in computing the possible contexts in $l$ regarding a particular preference of each attribute in $\Delta$. For lack of space, we do not provide here the rigorous definition of the sufficient statistics and how they are updated, but only describe it by means of an example.

\vspace{-0.2cm}
\begin{example}[Sufficient Statistics]
\label{ex:sufstatis}
Let $R(A,B,C)$ be a relational schema with $a_1$, $a_2 \in$ dom($A$), $b_3$, $b_5$, $b_6 \in$ dom($B$) and $c_1$, $c_2$, $c_4$, $c_5 \in$ dom($C$). Let $S$ be a preference stream over $R$ as shown in Fig. \ref{fig:sufficientStatistics}(c), where $T$ column shows the timestamp that the temporal bituple was generated, and $u_1>_{t_i}u_2$ for every temporal bituple ($u_1,u_2,t_i$) in the preference stream, with $1 \leq i \leq 10$. Consider the sufficient statistics for attribute $C$ shown in the Fig. \ref{fig:sufficientStatistics}(a) collected from the preference stream $S$ until time instant $t_9$. Table on top of the Fig. \ref{fig:sufficientStatistics}(a) shows the \textit{context counters} regarding the preferences over the attribute $C$, and table on the bottom  shows the \textit{general counters} over $C$. Context counters account for the possible causes for a particular preference over an attribute, and general counters stores the number of times that a particular preference over an attribute appeared in the stream. With the arrival of a temporal bituple at the time instant $t_{10}$ - call it $h$, the sufficient statistics are updating as follows (see Fig. \ref{fig:sufficientStatistics}(b)): (1) Compute $\Delta (u_1,u_2)$, which is the set of attributes where $u_1$ and $u_2$ differ in $h$. In this example, $\Delta (u_1,u_2)$ = $\{C\}$, then only the attribute $C$ will have their statistics updated according to $h$; (2) Increment context counters $a_1$ and $b_6$ regarding the preference $c_2$>$c_1$ (table on top of the  Fig. \ref{fig:sufficientStatistics}(b)). Notice that in the temporal bituple $h$ the values $a_1$ and $b_6$ are possible contexts (causes) for the preference $c_2$>$c_1$, just because they are equal in both tuples, i.e., $u_1[A] = u_2[A]$ and $u_1[B] = u_2[B]$. As until now we had no context $b_6$, it is inserted in the statistics; (3) Increment general counter of the preference $c_2$>$c_1$ (table on the bottom of the Fig. \ref{fig:sufficientStatistics}(b)).
\end{example}

\vspace{-0.2cm}
\noindent \textbf{Memory Management.} In order to limit the growth of the sufficient statistics, both strategies perform a simple memory management procedure described as follows. We can abstract our statistics as a tree, where the leaves are represented by general counters and context counters. For each leaf, we store the time of its last update. Periodically, in order to reduce runtime overhead, the strategies perform the memory management of their statistics, which in short consists in eliminating leaves that have not been visited since a long time (i.e., the time of its last update differs from the current time by an amount greater than a threshold). When a leaf is removed, we verify if the nodes traversed to reach this leaf recursively need to be removed as well, in the case of these nodes do not have other children. This means discarding information that is very old and is no longer relevant to the current scenario. According to tests carried out on real data this mechanism proved to be effective.

\begin{figure}[t]
%	\centering
%\begin{center} 	
%\begin{table}[t]% TABLES SHOULD BE AT THE TOP [t] OR BOTTOM [b} OF PAGES
%\scalefont{0.8}
\scriptsize
%\sffamily % CHANGES THE FONT WITHIN THE TABLE TO sans serif

\begin{tabular}{lll}
\hspace{-0.3cm}
%------------------Tabela 1-------------------
\begin{tabular}{|p{0.05cm}|p{0.15cm}||c|c|c|}
%	\cline{3-5}  % DRAWS HORIZONTAL LINE FROM 2nd to 13th COLUMNS
\hline
	\multicolumn{2}{|c||}{} & $c_1$>$c_2$ &	$c_2$>$c_1$ &	$c_4$>$c_5$
\\ \hline
	\multirow{2}{*}{$A$} & $a_1$ & 3 & 1 & -	
\\\cline{2-5}
	& $a_2$ & - & - & 2
\\ \hline
	\multirow{2}{*}{$B$} & $b_3$ & 1 & - & 1	
\\\cline{2-5}
	& $b_5$ & 1 & - & 1
\\ \hline
	\multicolumn{5}{c}{}
\\

\multicolumn{5}{c}{
\begin{tabular}{|c||c|}
\hline
	$c_1$>$c_2$ & 4 	
\\ \hline
	$c_2$>$c_1$ & 2
\\ \hline
	$c_4$>$c_5$ & 3
\\ \hline
\end{tabular}
}

\\
\multicolumn{5}{c}{(a)}
\end{tabular}
%------------------Tabela 1-------------------
&
%------------------Tabela 2-------------------
\begin{tabular}{|p{0.05cm}|p{0.15cm}||c|c|c|}
%	\cline{3-5}  % DRAWS HORIZONTAL LINE FROM 2nd to 13th COLUMNS
\hline
	\multicolumn{2}{|c||}{} & $c_1$>$c_2$ &	$c_2$>$c_1$ &	$c_4$>$c_5$
\\ \hline
	\multirow{2}{*}{$A$} & $a_1$ & 3 & 2 & -	
\\\cline{2-5}
	& $a_2$ & - & - & 2
\\ \hline
	\multirow{2}{*}{$B$} & $b_3$ & 1 & - & 1	
\\\cline{2-5}
	& $b_5$ & 1 & - & 1
\\\cline{2-5}
	& $b_6$ & - & 1 & -
\\ \hline
	\multicolumn{5}{c}{}
\\

\multicolumn{5}{c}{
\begin{tabular}{|c||c|}
\hline
	$c_1$>$c_2$ & 4 	
\\ \hline
	$c_2$>$c_1$ & 3
\\ \hline
	$c_4$>$c_5$ & 3
\\ \hline
\end{tabular}
}

\\
\multicolumn{5}{c}{(b)}
\end{tabular}
%------------------Tabela 2-------------------
&
%------------------Tabela 3-------------------
\begin{tabular}{|c||c|c|c||c|c|c|}
\hline
& \multicolumn{3}{c||}{$u_1$} & \multicolumn{3}{c|}{$u_2$}
\\ \hline
$T$ & $A$ & $B$ & $C$ & $A$ & $B$ & $C$
\\ \hline
$t_1$ & $a_1$ & $b_3$ & $c_1$ & $a_1$ & $b_3$ & $c_2$
\\ \hline
$t_2$ & $a_1$ & $b_3$ & $c_2$ & $a_1$ & $b_5$ & $c_1$
\\ \hline
$t_3$ & $a_2$ & $b_5$ & $c_2$ & $a_1$ & $b_3$ & $c_1$
\\ \hline
$t_4$ & $a_2$ & $b_3$ & $c_4$ & $a_2$ & $b_6$ & $c_5$
\\ \hline
$t_5$ & $a_1$ & $b_5$ & $c_1$ & $a_1$ & $b_5$ & $c_2$
\\ \hline
$t_6$ & $a_2$ & $b_3$ & $c_4$ & $a_2$ & $b_3$ & $c_5$
\\ \hline
$t_7$ & $a_1$ & $b_3$ & $c_1$ & $a_1$ & $b_5$ & $c_2$
\\ \hline
$t_8$ & $a_2$ & $b_5$ & $c_1$ & $a_1$ & $b_6$ & $c_2$
\\ \hline
$t_9$ & $a_1$ & $b_5$ & $c_4$ & $a_2$ & $b_5$ & $c_5$
\\ \hline \hline
$t_{10}$ & $a_1$ & $b_6$ & $c_2$ & $a_1$ & $b_6$ & $c_1$
\\ \hline
\multicolumn{7}{c}{(c)}
\end{tabular}
%------------------Tabela 3-------------------

\end{tabular}
\rmfamily % RESTORES TO TIMES, SO THAT CAPTION IS WRITTEN PROPERLY
%\end{table}
%\end{center}
	\vspace{-0.4cm}
	\caption{(a) Sufficient statistics for attribute $C$ at the time instant $t_9$. (b) Sufficient statistics for attribute $C$ at the time instant $t_{10}$. (c) Preference stream $S$ until time instant $t_{10}$.}
	\label{fig:sufficientStatistics}
\end{figure}

%\normalsize

%\begin{figure}[htb]
%\centering
%	\caption{(a) Sufficient statistics for attribute $C$ at the time instant $t_9$. (b) Sufficient statistics for attribute $C$ at the time instant $t_{10}$. (c) Preference stream $S$ until time instant $t_{10}$.}
%	\label{fig:sufficientStatistics}
%\begin{minipage}[c]{0.49\linewidth}
%\centering
%------------------Tabela 1-------------------
%------------------Tabela 1-------------------
%\end{minipage}
%\hfill
%\begin{minipage}[c]{0.49\linewidth}
%\centering
%------------------Tabela 2-------------------
%------------------Tabela 2-------------------
%\end{minipage}
%\hfill
%\begin{minipage}[c]{0.49\linewidth}
%\centering
%------------------Tabela 3-------------------
%------------------Tabela 3-------------------
%\end{minipage}
%\end{figure}

\vspace{-0.2cm}
\subsection{Greedy Strategy}

\vspace{-0.2cm}
The main idea of the Greedy Strategy is to create a preference relation from the most promising dependencies between attributes of a preference stream. In order to measure the dependence between a pair of attributes, we use the concept of \textit{degree of dependence}. The degree of dependence of a pair of attributes  $(X,Y)$ is a real number that estimates how preferences on values for the attribute $Y$ are influenced by values for the attribute $X$. We adapted the concept of \textit{degree of dependence} defined in \cite{ictai2012} to work with sufficient statistics. Its computation is carried out as  described in  Alg. \ref{alg1}.
In order to facilitate the description of Alg. \ref{alg1} we introduce some notations as follows: (1) We denote by $T_{yy'}^{time}$  the finite subset of temporal bituples $(u_1,u_2,t) \in$ $S$, such that $t \leq time$, $(u_1[Y] = y \wedge u_2[Y] = y')$ or $(u_1[Y] = y' \wedge u_2[Y] = y)$; 
(2) We denote by $S_{x|(y,y')}^{time}$  the subset of $T_{yy'}^{time}$ containing the temporal bituples $(u_1,u_2,t)$ such that $u_1[X] = u_2[X] = x$. 
Example \ref{ex:degreepref} illustrates the computation of the degree of dependence on the statistics.

%In order to facilitate the description of Alg. \ref{alg1} we introduce some notations as follows: (1) For each $y,y' \in$ \textbf{general counters} over $Y$ from $Q$, $y \neq y'$ we denote by $T_{yy'}^{time}$  the finite subset of temporal bituples $(u_1,u_2,t) \in$ $S$, such that $t \leq time$, $(u_1[Y] = y \wedge u_2[Y] = y')$ or $(u_1[Y] = y' \wedge u_2[Y] = y)$; (2) We define support(($y,y'$),$Q$) = $\frac{|T_{yy'}^{time}|}{n}$, where $n$ is the number of elements of the preference stream processed until the time instant $time$ and $|T_{yy'}^{time}|$ is obtained by the sum of the values of two general counters of $Y$ from $Q$: referent to $y$>$y'$ and $y'$>$y$. We say that the pair $(y,y') \in$ general counters over $Y$ is \textit{comparable} if support(($y,y'$),$Q$) $\geq \alpha_1$, for a given threshold $\alpha_1$, $0 \leq \alpha_1 \leq 1$; (3) For each $x \in$ \textbf{dom}$(X)$, we denote by $S_{x|(y,y')}^{time}$  the subset of $T_{yy'}^{time}$ containing the temporal bituples $(u_1,u_2,t)$ such that $u_1[X] = u_2[X] = x$; (4) We define support($S_{x|(y,y')}^{time}$,$Q$)  = $\frac{|S_{x|(y,y')}^{time}|}{|\bigcup_{x' \in \textbf{dom}(X)} S_{x'|(y,y')}^{time}|}$, where $|S_{x|(y,y')}^{time}|$ is obtained by the sum of the values of two context counters of $Y$ from $Q$: fixing the line for $X=x$, and sum the column values $y$>$y'$ and $y'$>$y$; (5) We say that $x$ is a \textit{cause for  $(y,y')$ being comparable} if support($S_{x|(y,y')}^{time}$,$Q$)  $\geq \alpha_2$, for a given threshold $\alpha_2$, $0 \leq \alpha_2 \leq 1$. Although the notation looks a little complicated, the process of calculating the degree of dependence on the statistics is very simple and can be easily understood by the Example 4.2.

\input{tex/algo}

\vspace{-0.2cm}

\begin{example}[Degree of Dependence on the Statistics]
\label{ex:degreepref}
Let us consider the preference stream in the Fig. \ref{fig:sufficientStatistics}(c) until the time instant $t_{10}$ and the snapshot (picture) $Q$ of their sufficient statistics for attribute $C$ shown in Fig. \ref{fig:sufficientStatistics}(b). In order to compute the degree of dependence of the pair $(A,C)$ with respect to $Q$, we first identify the context counters related to $A$ in the Fig. \ref{fig:sufficientStatistics}(b). The thresholds we consider are $\alpha_1 = 0.1$ and $\alpha_2 = 0.2$. The support of $(c_1,c_2)$ and $(c_4,c_5)$ are $(4+3)/10=0.70$ and $3/10=0.30$, respectively. Therefore, we do not discard any of them.  Entering the inner loop for $(c_1,c_2)$ we have only one set namely  $S_{a_1|(c_1,c_2)}$. The support of $S_{a_1|(c_1,c_2)}$ is $5/5=1.0$ and  $N = 3/5$. Hence, $f_1(S_{a_1|(c_1,c_2)}) = 3/5$ and $f_2(T_{c_1c_2}) = 3/5$. In the same way, for $(c_4,c_5)$ we have $S_{a_2|(c_4,c_5)}$ with support $2/2=1.0$ and $N=2/2=1.0$. Therefore, $f_1(S_{a_2|(c_4,c_5)}) = 1.0$ and $f_2(T_{c_4c_5}) = 1.0$. Thus, the degree  of dependence of $(A,C)$ is $f_3((A,C),Q) = \max\{3/5,1.0\} = 1.0$. Besides, the degree of dependence of $(B,C)$ is $f_3((B,C),Q) = 1.0$.
\end{example}

%Esta estratégia constrói uma $RBP_t$ da forma como se segue: (1) Tire um snapshot $T$ das estatísticas suficientes no instante de tempo $t$; (2) Calcule os graus de dependência entre cada par de atributos de $R$ de acordo com $T$. Seja $\Omega$ o conjunto resultante destes cálculos, com elementos do tipo $(A_i,A_j,dd)$, onde $A_i$ e $A_j$ são atributos de $R$ e $dd$ é o grau de dependência entre $(A_i,A_j)$; (3) Elimine de $\Omega$ todos os elementos cujo $dd < 0.5$ (indica  a dependência negativa entre um par de atributos); (4) Ordene os elementos de $\Omega$ de forma decrescente de acordo com seu $dd$; (5) Dentro de um laço, pegue cada um dos elementos $(A_i,A_j,dd)$ do conjunto ordenado $\Omega$ e insira a aresta $(A_i, A_j)$ no grafo $G_t$ da $BPN_t$, se a mesma for consistente. A inserção de uma aresta é consistente se a mesma não forma ciclos em $G_t$. Dessa forma, é criado o grafo $G_t$ da $BPN_t$; (6) Para cada nó de $G_t$, crie sua correspondente tabela de probabilidade condicional utilizando o \textit{Maximum Likelihood Principle} \cite{Jensen:2007:BND:1535531} sobre $T$, que é baseado na ideia de frequência.

\vspace{-0.2cm}

Given this, our strategy is straightforward and builds a $BPN_t$ from sufficient statistics as follows: (1) Let $S$ be a preference stream over the relational schema $R$. Take a snapshot $Q$ of the sufficient statistics from $S$ at the time instant $t$; %This is necessary because the statistics are constantly updated with each new element of $S$ and we need a version of the statistics updated only until time instant $t$; 
(2) Calculate the degree of dependence (Alg. \ref{alg1}) between each possible pair of attributes of $R$ according to $Q$. Let $\Omega$ be the resulting set of these calculations, with elements of the form $(A_i,A_j,dd)$, where $A_i$ and $A_j$ are attributes of $R$ and $dd$ is the degree of dependence between $(A_i,A_j)$; (3) Eliminate from $\Omega$ all elements whose $dd < 0.5$ (such $dd$ indicates weak dependence); (4) Order the elements $(A_i,A_j,dd)$ in $\Omega$ in decreasing order according to their $dd$; (5) Consider that the graph $G_t$ of the $BPN_t$ starts with a node for each attribute of $R$. Within a loop, take each  $(A_i,A_j,dd)$ $\in$ $\Omega$ and insert the edge $(A_i, A_j)$ in the graph $G_t$ only if the insertion does not form cycles in $G_t$. Thus, graph $G_t$ of the $BPN_t$ is created; (6) Once we have $G_t$, we are now seeking for estimates of the conditional probabilities tables $\theta_t$ of the $BPN_t$. Since we have $Q$, we can estimate such parameters using the Maximum Likelihood Principle (see \cite{ictai2012} for details).

%\cite{Jensen:2007:BND:1535531}, in which we calculate the maximum likelihood estimates for each conditional probability distribution of our model. The underlying intuition of this principle uses frequencies as estimates; for instance, if we want to estimate $P(C=c_1 >_t C=c_2 | A=a_1)$ we need to calculate
%$\frac{N(A=a_1,C=c_1)}{N(A=a_1,C=c_1) + N(A=a_1,C=c_2)}$, where $N(A=a_1,C=c_1)$ is the number of cases where $(A=a_1,C=c_1)$ is preferred over $(A=a_1,C=c_2)$ according to $Q$, and so on. Thus, $\theta_t$ of $BPN_t$ is created, and the $BPN_t$ is ready for use.


%Esta estratégia é caracterizada como gulosa, pois na tentativa de construir um grafo sem ciclos são eliminadas arestas que poderiam ser úteis. Porém, este método é extremamente eficiente em termos de tempo e memória, e tende a produzir bons resultados em streams com distribuição estacionária.

This strategy is characterized as greedy, once in the attempt to construct a graph with no cycles it disposes edges that could be useful. However, this method is extremely efficient in terms of time and memory, and tends to produce good results, as  shown in Section \ref{sec:results}.

\vspace{-0.2cm}
\subsection{Heuristic Strategy}

\vspace{-0.1cm}
%Esta estratégia utiliza um método heurístico baseado em um algoritmo genético (GA) incremental para realizar a fase de aprendizado da estrutura de grafo da Rede Bayesiana de Preferência.

This strategy uses a heuristic method based on an incremental genetic algorithm (IGA) over a preference stream to perform the learning phase of the graph structure $G_t$ of the $BPN_t$.
%In a traditional genetic algorithm, the same set of fixed samples are used as a whole for the fitness calculation after every generation. But this way of fitness calculation is not possible for streams since they cannot be stored fully. Thus,

The main idea consists in  evaluating the population of the IGA, not on a static database, but on the data coming from a stream.
%that are dynamic and evolve over time.
However, unlike the IGA proposed by \cite{Vivekanandan:2011:MDS:2036659.2036682}, which evaluates the population over a window of the stream, we evaluated the population over the statistics collected from the preference stream $S$. This implies a low memory usage besides a higher processing speed. The fitness function used is the same proposed by \cite{ictai2012} (\textit{score function}), based in concept of \textit{degree of dependence} between a pair of attributes (Alg. \ref{alg1}). However, in our strategy, the application of this function will be on a snapshot $Q$ of the statistics. The snapshot is only for the evaluation process to be fair, so that individuals in a same population are not evaluated on different data. The score function assigns a real number in [-1, 1] for a candidate structure $G_t$, aiming to estimate how good it captures the dependencies between attributes in $S$. In this sense, each edge of the graph is ``punished'' or ``rewarded'', according to the matching between each edge ($X$, $Y$) in $G_t$ and the corresponding degree of dependence of the pair ($X$, $Y$) with respect to $Q$.

In this strategy, the model  learning process consists of two phases running in parallel: (1) Online updating of the sufficient statistics for every new temporal bituple that comes in the preference stream, just as the Greedy Strategy; (2) Running the IGA, where its population is always evaluated taking into account new data from the stream. In each generation of the IGA, the best individual ($G_t$) of the population is kept in a variable called $BEST$ along with its conditional probability tables ($\theta_t$), built in the same way as in the Greedy Strategy. Thus, whenever the model is tested over time, the $BPN_t$ used will be the one stored in $BEST$.


This strategy builds a $BPN_t$ as follows: (1) Let $S$ be a preference stream over the relational schema $R$. Randomly generate an initial population $P_0$ of graphs without cycles over $R$; %In this step, each attribute in $R$ will be a node of the graph, and the edges are placed randomly;
(2) Take a snapshot $Q_0$ of the statistics from $S$; (3) Evaluate the individuals in the population $P_0$ over $Q_0$ according to the \textit{score function} \cite{ictai2012}; (4) For each generation $i$, until there are data in the stream, do the following: (4.1) Select pairs of individuals for the crossover in $P_i$; (4.2) Apply crossover for each pair, generating an offspring population $F_i$; (4.3) Apply mutation over some individuals from $F_i$; (4.4) Take a snapshot $Q_i$ of the statistics from $S$; (4.5) Evaluate the individuals of the population $F_i$ over $Q_i$; (4.6) From $P_i \cup F_i$, select the $|P_i|$ fittest individuals according to their score in order to build the next population $P_{i+1}$; (4.7) Set in the variable $BEST$ the best individual of the population $P_i$, along with its set of conditional probability tables. %Thus, when the model is tested over time, the $BPN_t$ used is the one stored in $BEST$.



\vspace{-0.2cm}
\subsection{Complexity Analysis of Both Strategies}

\vspace{-0.1cm}

%The optimization problem of determining the Bayesien Network structure which maximizes the score function is untractable. In fact, as shown in \cite{Robinson1977} the number of possible structures which contains $l$ nodes grows exponentially with $l$. Thus, heuristic methods  having polynomial time complexity are normally adopted  for accomplishing this task (\cite{cooper}). \\
We divided the complexity analysis of both strategies in three parts, as explained below.\\
%--\textit{The complexity of processing each element of the preference stream}: (i) The cost to scan a temporal bituple and save the $\Delta$ (the set of attributes that have different values in the two tuples) are $O(l)$, where $l$ is the number of attributes; (ii) The cost to scan the $\Delta$ and update the sufficient statistics for each attribute in $\Delta$ are $O(| \Delta |)$. Therefore, the complexity for processing each element of the preference stream in both strategies is $O(l)$.\\
--\textit{The complexity of processing each element of the stream and update the sufficient statistics}: (i) Scan a temporal bituple to save the $\Delta$ (set of attributes that have different values in the two tuples) and the $B$ (set of attributes that have equal values in the two tuples) are $O(l)$, where $l$ is the number of attributes; (ii) Update the statistics of an attribute is $O(|B|)$.
Thus, update the statistics for all attribute in $\Delta$ is $O(| \Delta | . |B|)$. Therefore, the complexity for processing each element in both strategies in the worst case is $O(| \Delta | . |B|)$, where $| \Delta | + |B| = l$, and in the best case is $O(l)$.\\
%
--\textit{The complexity of creating the preference model (BPN)}: 
(i) the computation of the  degree of dependence between the pairs of attributes is $O(l^2)$; 
(ii) for the Greedy Strategy the computation of the topology is $\mathbf{O(l^2.e)}$, where $e$ is the number of edges of the BPN. The sub-steps used in this calculation were: 
(a) the elimination of the pairs of attributes whose $dd<0.5$ is $O(l^2)$,
(b) the ordination of the pairs of attributes is $O(l^2.\log l)$ in the average case, and
(c) for each pair of attributes the acyclicity test of the insertion of its edge in the graph is $O(e)$, so the total complexity of this sub-step is $O(l^2.e)$.
For the Heuristic Strategy the computation of one iteration of the IGA is $\mathbf{O(l^2.q)}$, where $q$ is the population size. The sub-steps used in this calculation were: 
(a) the selection for the crossover is $O(q)$,
(b) the crossover operation is $O(l^2.q)$,
(c) the mutation operation is $O(q)$,
(d) the calculation of the fitness is $O(l^2.q)$, and
(e) the select of the fittest individuals through an elitism procedure is $O(q.\log q)$;
(iii) the computation of the conditional probability tables is $O(e.m)$, where $m$ is the number of training instances processed. Therefore, the total complexity for building the model in the Greedy Strategy is $O(e.(l^2 + m))$ and in the Heuristic Strategy is $O(l^2.q + e.m)$.
Notice that the difference of complexity between the two strategies is in the computation of the topology (in bold text), where the Greedy is dependent on the number of edges $e$ (satisfying $e\leq l.(l-1)/2$) and the Heuristic is dependent on population size $q$ of the IGA. Thus, for a small number of attributes ($e < q$), the Greedy Strategy tends to have better performance than the Heuristic Strategy. On the other hand, for large numbers of attributes and reasonable population sizes ($e > q$), the Heuristic Strategy tends to be more efficient.\\
%
--\textit{The complexity of using the model (BPN)} for ordering a temporal bituple in both strategies is $O(l+e)$, which can be reduced to $O(l)$  when the BPN is a sparse graph.
%Notice that the computational cost for building the model is quadratic on the number of attributes $l$ and the computational cost for using the model is linear on $l$. However, the number of attributes in streams tends to be small. \cite{citeulike:7359992}  discuss the typical learning scenario in streams, and according to them, the data is assumed to have a small and fixed number of attributes. This makes these costs quite low as can be seen in the tests presented in the Section \ref{sec:results}.


%---------------------------------------PROPOSED STRATEGIES-----------------------------------------------
