Processamento de Dados Massivos/Projeto e implementação de aplicações Big Data/R-tree

Em um mundo cada vez mais digitalizado é natural que as referências espaciais, que fazem parte do nosso dia-a-dia, ocupando um grande espaço em nossas vidas, ocupem muito espaço na web. Há uma inifinidade de aplicações que requerem dados espaciais, tais como mapas, serviços de recomendação de lugares, redes sociais, etc. O mundo não-digital consiste em uma quantidade muito grande de informações e essas aplicações só fazem sentido se forem capazes de manipular grande parte dos dados desse mundo. É preciso então pensar em estruturas de processamento capazes de lidar com um grande volume de dados, transformando-os em uma estrutura que permita uma manipulação eficiente. O exemplo mais simples e direto desse tipo de problema e aplicação consiste em pontos, com coordenadas geográficas (lat/long, por exemplo), representando entidades (localização de restaurantes, hotéis, cidades, pessoas, pessoas em lugares, etc.). Embora o cenário pareça corriqueiro há uma dificuldade nesse tipo de situação ao se lidar com a quantidade de informação codificada dessa forma. Uma vez que se tem uma base com milhões dessas entidades, uma busca espacial linear simples torna-se proibitiva, ainda mais se as consultas forem frequentes (como geralmente o são: “quantos restaurantes há perto de mim?”, “quantas pessoas visitaram cidades em um raio de 50 quilômetros do ponto X?”). É preciso construir uma estrutura de dados capaz de atender a essas consultas de forma eficiente. Uma estrutura apta a lidar com consultas a dados espaciais com eficiência é a R-tree. Como o próprio nome indica trata-se de uma árvore de busca, que evita que a busca seja feita em todos os dados.

R-tree

A ideia principal por trás da R-tree é organizar os objetos próximos em retângulos envolventes mínimos (MBR - minimum bounding retangle). Nas folhas da árvore o MBR envolve um grupo de objetos, nos níveis superiores o MBR envolve os MBRs que formam os seus filhos. A pesquisa envolve checar se o objeto da pesquisa tem intersecção com os retângulo envolventes, se não há intersecção com determinado MBR, não é preciso checar nos nós filhos. Quanto há intersecção com um nó folha é preciso checar todos os objetos que o compõe. A R-tree é uma árvore balanceada. De forma semelhante ao que acontece em uma B-tree, esse balanceamento é conseguido ao limitar o número de filhos que cada nó possui a M. Quando a inserção dos objetos faz com que um nó exceda esse número de filhos, acontece um rebalanceamento que consiste, basicamente, em dividir o nó que excedeu o número de filhos. Do ponto de vista da busca de um determinado objeto a R-tree é bastante eficiente, pois não é necessário pesquisar por todos os objetos. Isso significa que ela pode ser utilizada mesmo para situações nas quais a R-tree não pode ser completamente carregada em memória principal. Nesse tipo de cenário os nós podem ser mapeados para páginas de disco, permitindo acessos eficientes mesmo em uma memória mais lenta. A maior dificuldade na R-tree é sua construção, que precisa garantir que a árvore estará balanceada e ao mesmo tempo que os retângulos mínimos cobrirão a menor área possível, no total. Isso porque quanto maior essa área, maior o número de retẫngulos que terão intersecção com o objeto pesquisado, não importando o tamanho do objeto. Isso levará a um número maior de comparações desnecessárias. R-trees podem armazenar vários tipos de dados espaciais, desde pontos multidimensionais a polígonos. O presente trabalho abordará o caso em que se deseja trabalhar com pontos com coordenadas geográficas em duas dimensões. No entanto, é fácil perceber que as técnicas apresentadas não seriam muito diferentes se aplicadas a outro tipo de objetos.

Busca

Cada nó é formado por um identificador e um conjunto de MBRs representando os filhos. A busca inicia-se no nó-raiz. Para cada nó pesquisado verifica-se a intersecção da MBR dos filhos com o objeto da busca, se ocorre a intersecção o nó interseccionado é adicionado ao conjunto dos nós que precisam ser pesquisados. Quando um nó-folha é atingido todos os objetos que o constituem, e que em muitos casos, como no caso de pontos bidimensionais, compõe a página do próprio nó-folha, são checados contra o objeto da pesquisa.

Inserção

Para inserir também parte-se do nó-raiz. Para cada nó, se o objeto a ser inserido está contido em um dos filhos, basta tentar inseri-lo nesse nó. Caso não esteja completamente contido em um dos filhos é preciso utilizar uma heurística para definir em qual nó inseri-lo. A heurística utilizada pela R-tree original, como proposta por Guttman, consiste em escolher o nó cujo MBR será menos expandido para acomodar o novo dado. A R*-tree também considera que no caso de empate nesse critério será escolhida a subárvore representada pelo MBR de menor área. Ao chegar ao nó-folha o objeto é inserido no próprio nó. Como há um limite de ocupação para cada nó pode acontecer de isso levar a um número de objetos que excede o máximo permitido. Nesse caso é preciso dividir o nó que excede o número de elementos permitidos. Então será preciso definir como dividir os objetos contidos no nó excedido (S) entre os novos nós (A e B). Como o número de possibilidades é exponencial será preciso utilizar uma heurística. A heurística utilizada geralmente consiste em escolher inicialmente dois objetos ou nós (dentro do nó cujo tamanho foi excedido) que tenham a maior distância entre si. Esses dois elementos serão colocados em em A e B. Então para cada objeto, ou nó, desse grupo excedido calcula-se o acréscimo no MBR se adicionado a A ou B e o atribui ao nó cuja inserção desse elemento representa o menor acréscimo de área para o MBR. Como são criados dois novos nós, e esses dois novos nós terão o mesmo pai do antigo nó, pode acontecer de ser excedido o número de filhos do pai desses nós. Nesse caso serão aplicados os mesmos algoritmos a esse pai, e assim por diante até chegar à raiz se for necessário, o que pode levar à criação de uma nova raiz, aumentando o tamanho da árvore.

Abordagem paralela

O processo de busca de uma R-tree estável pode ser completamente paralelizado, pois trata-se apenas de leituras dos dados. Isso aliado ao fato de que uma busca consiste em uma série de operações simples e que a R-tree é uma árvore balanceada significa que não há um gargalo de processamento das buscas devido ao desenho da R-tree. No entanto, o processo de criação de uma R-tree é custoso, pois embora muitas inserções necessitem apenas uma busca seguida de uma inserção em um nó folha, as etapas de checagem da melhor subárvore, no caso em que há mais de um nó-filho para inserir determinado objeto, e principalmente a divisão de um nó que excedeu o número máximo de filhos, são operações caras e que envolvem alterações significativas na estrutura da árvore, que impossibilitariam uma paralelização ingênua. Essa dificuldade de paralelização esbarra em uma exigência de se trabalhar com esse tipo de estrutura em um ambiente de big-data. E como vivemos em um mundo que possui, e precisa trabalhar, com um número cada vez maior de dados, é preciso desenvolver uma abordagem capaz de lidar com uma R-tree nesse tipo de contexto.

Abordagem MapReduce para construção da R-tree

Ariel Carry et al. apresentam uma abordagem para construção da R-tree em um ambiente de big-data utilizando o modelo de programação conhecido como MapReduce. O modelo MapReduce procura abstrair as dificuldades de se trabalhar com uma estrutura de clusters, com dados distribuídos e processamento paralelo. Para conseguir essa abstração o modelo trabalha apenas com duas funções básicas de controle de fluxo. A função map, que é responsável por definir um processamento individual para cada partição dos dados, e uma função reduce, que é capaz de organizar os dados vindos da função map executada anteriormente, aglutinando os dados processados. Por essa descrição superficial do modelo já é possível perceber que a implementação da R-tree nesse ambiente não pode ser feita diretamente. Para resolver essa situação será preciso utilizar três passos. São esses passos:

1. Computação da função de particionamento;
2. Construção das R-trees;
3. Consolidação das R-trees em uma R-tree final.

A ideia por trás das três fases é permitir a construção de R-trees, separadamente, sobre diferentes partições dos pontos e consolidar essas R-trees em uma única R-tree. As duas primeiras fases são paralelas, sendo a segunda a fase de maior computação. A terceira e última fase deve ser feita de forma sequencial, mas sua computação é bem menor. As três fases serão agora vistas em detalhes.

Computação da função de particionamento

Precisamos definir partições sobre as quais serão criadas as R-trees separadamente. Essas partições precisam ter o mesmo tamanho, ou um tamanho muito próximo. Devem também possuir uma proximidade entre os pontos que as compõe, ao mesmo tempo em que esses pontos devem estar o mais distante possível dos pontos nas outras partições. Essa exigência acontece porque se tivermos duas R-trees de partições diferentes tratando de pontos próximos, os MBRs dos nós que contêm esses pontos em uma partição terão muita sobreposição com os nós de outra partição, e como já vimos anteriormente isso torna a R-tree ineficiente. A forma utilizada para definir essas partições faz uso de uma estrutura conhecida como curva de preenchimento de espaço (space filling curve). Essas curvas consistem em caminhamentos que induzem uma ordem em espaços multidimensionais com dois objetivos básicos:

• Todo ponto do espaço faz parte da curva, logo todo ponto do espaço tem uma ordem definida por essa curva;
• Dois pontos próximos no espaço multidimensional também são próximos segundo a ordem definida pela curva e dois pontos distantes segundo a curva também são distantes no espaço multidimensional (essa relação varia dependendo dos pontos analisados, mas mantém-se suficientemente coerente para a maioria dos pontos).

Essas propriedades dessas curvas permitem que sejam utilizadas para definir mais facilmente as distâncias entre os pontos que compõem a base. No caso específico desse trabalho é utilizada a curva Z (z-curve), mas outras curvas poderiam ter sido escolhidas. Uma das vantadens da curva Z é sua facilidade para gerar a ordem segundo seu caminhamento. Basta concatenar as coordenadas do ponto que se deseja avaliar e ordenar os dígitos segundo a sua ordem nas coordenadas originais, de forma que os dígitos de mais alta ordem fiquem juntos. Por exemplo, se um ponto tem duas coordenadas 011 e 101, as coordenadas desse ponto na curva de ordem Z serão 011011. Uma vez que temos uma forma de definir uma ordem para todos os pontos da base, bastaria ordenar esses pontos e trabalhar sobre as partições segundo essa ordem. No entanto como trata-se de uma base muito grande esse processamento seria custoso demais. A solução então é definir apenas os pontos que estão nos limites dessas partições, definindo-a a partir desses pontos. A forma escolhida para definir esses pontos é tomar pontos aleatórios na base como amostra, e a partir desses pontos definir as partições. Serão tomadas L amostras da base de forma paralela. Cada mapper tomará L/M pontos aleatoriamente de sua base e calculará seu valor unidimesional segundo a curva Z. Esses valores serão emitidos para o reducer. O reducer ordenará os L valores recebidos. Caso o número de valores ainda seja muito grande para ordenamento em memória principal poder-se-ia utilizar mais uma fase, com uma algoritmo de ordenação map-reduce como o TeraSort. Uma vez ordenados, são tomados $R-1$ pontos dessa lista, em que $R$ é o número de partições desejados, começando no ponto ${\frac {L}{R}}$, depois ${\frac {2L}{R}}$, ${\frac {3L}{R}}$, etc. Esses pontos são utilizados para definir uma função de partição em que os limites das partições são definidos por esses pontos. Essa função pode ser formalmente definida como sendo:
$f(o.P)={\begin{cases}1,&U\left(o.P\right)\leq S'\left[1\right]\\j,&S'\left[j-1\right]<U\left(o.P\right)\leq S'\left[j\right],j=2,...,R-1\\R,&U\left(o.P\right)>S'\left[R-1\right]\end{cases}}$

Dessa forma essa fase produzirá uma lista de valores unidimensionais que serão utilizados para particionar todos os dados. Em termos de entradas e saídas temos:

Função	Input: (Key, Value)	Output: (Key, Value)
Map	(o.id, o.P)	(C, U(o.P))
Reduce	(C, list(ui, i=1, ..., L))	S'

em que o é um ponto, que possui um identificador o.id e suas coordenadas o.P, C é uma constante qualquer e S’ é a lista de valores unidimensionais.

Construção das R-trees

Uma vez que temos como particionar os dados, podemos construir R-trees diferentes para cada partição. Isso significa que a construção das R-trees pode ser feita paralelamente. Primeiramente, é preciso particionar os dados propriamente ditos, uma vez que eles estão distribuídos no cluster e só o que temos é como particioná-los, através da função de particionamento obtida na fase anterior. Para fazer esse particionamento cada mapper terá a função de particionamento e a utilizará para dividir os seus dados, emitindo para cada reducer, segundo a partição do dado, ou seja a chave emitida será a partição e o valor será o ponto. Cada reducer receberá os pontos de sua partição e construirá a R-tree normalmente, como se fosse uma R-tree sequencial normal, como abordado anteriomente. Dessa forma a saída dessa fase é tantas R-trees quantas forem as partições definidas inicialmente. O paralelismo dessa etapa está restringido pelo número de partições definidas a priori. Quanto maior o número de partições maior o número de reducers construindo r-trees paralelamente. No entanto um número muito grande de partições em relação ao número de pontos pode levar a uma degeneração das partições e uma consequente degeneração das r-trees criadas, que tenderão a ter maior sobreposição entre si.

Função	Input: (Key, Value)	Output: (Key, Value)
Map	(o.id, o.P)	(f(o.P), o)
Reduce	(f(o.P), list(oi, i=1, ..., A))	tree.root

Consolidação das R-trees

A última fase não é executada em uma ambiente map-reduce. Trata-se de um processamento sequencial, que processa as R-trees formadas na etapa anterior para produzir uma só R-tree. Como as partições tendem a ter o mesmo número de pontos, cada R-tree deve possuir o mesmo número de pontos, e provavelmente a mesma altura, embora possa haver uma pequena variação. Isso significa que para forma a nova R-tree basta tomar o MBR de cada raiz e inserir em um árvore inicialmente vazia. Essa abordagem significa que o custo dessa última fase é o custo de inserção de P objetos (P é o número de partições) em uma R-tree, o que é um custo muito menor do que a criação de uma R-tree com os pontos originais.

Toda a solução apresentada pode ser resumida no seguinte esquema:

Modelo esquemático da solução proposta

Abordagem de filtros (streams) para construção da R-tree

Se analisarmos a figura apresentada ao final da seção anterior, embora essa represente a solução apresentada, é difícil ver naturalmente três fases nesse esquema. Isso significa que esse abordagem é artificial ao problema. E de fato trata-se de uma abordagem que se deve muito mais ao modelo map-reduce do que ao problema em si. Mas podemos pensar em um modelo que represente melhor esse esquema, de fato, podemos mapear muitas dessas entidades desse esquema a filtros de processamento, conforme a seguinte figura, em que os filtros estão pintados:

Esquema da solução mostrando filtros

Os filtros fazem parte do modelo, naturalmente, servindo uns de entradas aos outros e resultando na R-tree dos pontos de entrada. Embora do ponto de vista da modelagem esse esquema faça mais sentido, o resultado final e o esforço computacional serão o mesmo da abordagem map-reduce apresentada anteriormente. No entanto, a abordagem utilizando streams é mais flexível, pois os filtros não processam sequencialmente, mas podem ser pensados como um processamento contínuo. Essa mudança de paradigma significa duas vantagens. Primeiramente, seria mais fácil pensar essa solução para uma situação em que esses pontos são processados de forma contínua, como em uma aplicação que seja alimentada com novos dados constantemente. A segunda vantagem é que esses filtros poderiam ser retroalimentados, aumentando o auto-conhecimento do processamento e assim possibilitando uma maior eficiência. Podemos adicionar os seguintes canais de comunicação entre os filtros, apresentados com linhas tracejadas:

Modelo de filtros com comunicação entre si

Essa comunicação permitiria, por exemplo, adicionar um comportamento que verificasse o tamanho das partições à medida em que os dados são lidos pelo filtro “particiona pontos”, e no caso em que a partição estiver muito desbalanceada o procedimento de definição da função de partição, que envolve três filtros, pode ser realizado novamente. Outro comportamento que poderia surgir com esse modelo seria o de analisar o comportamento dos filtros que calculam as r-trees de cada partição em comparação com o resto do processo que poderia definir se o número de partições escolhido é um bom compromisso em termos da quantidade de paralelismo.