Community based adaptation to livelihood outcomes

As melhorias descritas anteriormente aplicam-se a ambas as versões da Onion-tree, ou seja, à V-Onion-tree e à F-Onion-tree. Entretanto, a V-Onion-tree introduzida em [Carélo et al., 2009] possui uma limitação relacionada ao seu modo de particionamento que possibilita melhorias diretamente relacionadas a essa versão sejam feitas no algoritmo de bulk-loading. A seguir é descrita a limitação da V-Onion-tree (seção 4.2.4.1), e introduzidas as melhorias propostas (seção 4.2.4.2).

4.2.4.1 Limitação do particionamento da V-Onion-tree

O modo de particionamento da V-Onion-tree utiliza como método para determinar a quantidade do número de partições de um nó a razão entre o raio do nó pai e o raio do nó filho. No entanto, existem situações em que a quantidade de expansões é elevada, inclusive gerando um número de expansões tal que a quantidade de elementos que podem ser armazenados nesse único nó é maior do que a quantidade de elementos da árvore toda.

Suponha que exista um nó pai cujo raio seja 1 e que exista um nó filho cujo raio tenha valor 0,001. Em se tratando de uma V-Onion-tree, existe a necessidade de expansão desse nó, visto que o critério para realizar uma expansão na V-Onion-tree é analisar que o raio do nó filho é menor que a metade do raio do nó pai. A quantidade de expansões a ser aplicada é a divisão do raio do nó pai pelo raio do nó filho, o que resulta em 1000 expansões, e equivale a 3004 regiões a serem definidas para esse nó (o número de regiões é determinado pela fórmula 3xNúmero de Expansões + 4). Um nó com 3004 regiões armazena, portanto, 6008 elementos. Por exemplo, suponha que está sendo criada uma Onion-tree para o conjunto de dados real Brazilian Cities, usado nos experimentos do capítulo 5, o qual possui 5507 elementos. No pior caso, o conjunto todo de dados poderia ser armazenado em um único nó e ainda haveriam regiões não ocupadas.

A situação descrita anteriormente ilustra como o procedimento de expansão da V-Onion-tree, introduzido em [Carélo et al., 2009], pode gerar quantidades de expansões desnecessárias em relação à quantidade de dados a ser inserida. No pior caso, ou seja, caso um único nó armazene todos os elementos a serem inseridos, a estrutura gerada seria semelhante à uma lista ligada, fazendo com que qualquer consulta seja respondida no pior caso com complexidade O(n).

4.2.4.2 Melhorando o Método de Particionamento da V-Onion-tree

O algoritmo de bulk-loading para a V-Onion-tree possui duas vantagens em relação ao processo de expansão: conhecer com antecedência a quantidade e os elementos que serão inseridos na estrutura. Desse modo, são introduzidas nesta dissertação duas melhorias baseadas nessas vantagens: expansão baseada em quantidade e expansão baseada em média. O objetivo da expansão baseada em quantidade é manter um limite superior de expansões que cada nó pode apresentar. O limite é baseado na quantidade de elementos a serem inseridos naquele nível da árvore. Se em um dado nível da estrutura são inseridos n elementos, então o número de regiões que devem existir é NumeroRegioes = n/2. Desse modo, o número de expansões máximo, denominado ExpMax, que esse nó pode ter é dado pela Equação 4.4.

ExpMax= (NumeroRegioes − 4)/3 (4.4)

Outro fator a ser considerado no procedimento de expansão é que nem todos os elementos que são dados de entrada a um nó irão de fato ser armazenados nele. Muitos desses elementos serão novamente utilizados nas demais chamadas recursivas do algoritmo de bulk-loading. Desse modo, outra melhoria desenvolvida neste trabalho consiste em expandir a V-Onion-tree com o método denominado expansão baseada em média. O método funciona como explicado a seguir. Para o par de pivôs selecionado para o nó atual, calcula-se a distância média dos pivôs s1e s2aos demais elementos, denominadas como m1 e

distâncias necessárias para o processo já foram calculadas e o processo não demanda cálculos de distância adicionais. O próximo passo é calcular o valor médio das distâncias, dado por (m1+m2)/2. Finalmente, o número de expansões é determinado como sendo tal que o raio da maior bola determinada pelos pivôs s1 e s2 consiga ser maior do que o valor dado pelo valor médio das distâncias. Com isso, espera-se

que o número de expansões seja o suficiente para cobrir parte dos elementos que foram recursivamente destinados a esse nó, além de também respeitar a quantidade máxima de expansões determinada por ExpMax.

Enquanto a expansão baseada em quantidade determina a quantidade máxima possível de expansões que um nó pode possuir, a expansão baseada em média assume que a grande parte dos elementos destinados ao nó é recursivamente encaminhada aos nós dos níveis inferiores. Assim, ela normalmente diminui o número de expansões calculadas pelo algoritmo original da V-Onion-tree, que não considera a quantidade de dados a ser inserida. A expansão baseada em média normalmente gera menos expansões do que a expansão baseada em quantidade.

Nas melhorias propostas nesta dissertação, as expansões baseada em quantidade e baseada em média são combinadas, de forma que a expansão baseada em média atue como limite inferior para o número de expansões (definido no algoritmo como a variável nroMaxRegioes), enquanto que a expansão baseada em quantidade atue como limite superior para esse valor (definido no algoritmo como a variável nroMinRegioes).

O Algoritmo 6 detalha o algoritmo de particionamento da V-Onion-tree, que pode ser utilizado por qualquer algoritmo de bulk-loading proposto nesta dissertação de mestrado. O algoritmo possui como parâmetros de entrada os dois representantes do nó, o raio do nó pai, raio do nó atual e também a forma de construção a ser aplicada para a V-Onion-tree: tradicional ou baseada em expansões. Enquanto a construção tradicional contrói a V-Onion-tree sem as melhorias propostas nesta dissertação, a construção baseada em expansões contrói a V-Onion-tree usando as expansões baseada em quantidade e em média. Inicialmente, há o cálculo da quantidade máxima de expansões que um nó pode possuir com base na quantidade de elementos que a ele é associada (linhas 1 a 3), ou seja, é feito o uso da expansão baseada em quantidade. Se a forma de construção da V-Onion-tree é a tradicional, o número de expansões calculado é dado pela razão entre o raio do nó pai e o raio do nó filho (linhas 4 a 6). Se a forma de construção é a baseada em expansões, então as distâncias médias de cada um dos elementos do nó aos demais elementos são calculadas (linhas 8 a 10). Finalmente, um procedimento iterativo se inicia incrementando o número de expansões até que o raio máximo da bola gerada seja maior do que o valor da média da distâncias determinado anteriormente. Isso é feito de forma que as expansões nunca tenham um valor maior do que o número máximo de expansões atribuído ao nó (linhas 12 a 15).

Algorithm 6: Paticioning Method (Elementos,S1,S2,RaioPai,RaioNo,TipoExpansao) Input : Elementos {elementos do conjunto de dados},

S1 {representante um do nó}, S2 {representante dois do nó}, RaioPai{valor do raio do no pai}, RaioNo{valor do raio do no atual} ,

TipoExpansao{determina qual o modo de expansao da V-Onion: tradicional ou baseado em quantidade e media combinados}

Output: Expansoes {numero de expansoes calculado para o no}

1 size← tamanho(Elementos);

2 nroMaxRegioes← size/2;

3 nroMaxExpansoes← (nroMaxRegioes - 4)/3;

4 if TipoExpansao = tradicional then 5 Expansoes← RaioPai/RaioNo;

6 end

7 else if TipoExpansao = baseadoEmExpansoes then 8 m1 ← mediaDistancias(S1,Elementos);

9 m2 ← mediaDistancias(S2,Elementos); 10 med← (m1 + m2)/2;

11 Expansoes← 0;

12 while raioTotal(Expansoes,RaioNo) < med AND Expansoes < nroMaxExpansoes do 13 Expansoes++;

14 end

15 return Expansoes; 16 end