USANDO R-TREE PARA QUERIES ESPACIAIS MAIS RÁPIDAS
Escrito por Lucas Travi & Raul Wagner — 05/08/2020
Usar dados geoespaciais está cada vez comum em diversos segmentos da ciência e análise de dados, além de servir de insumo para tornar várias análises mais completas. Porém, trabalhar com dados geoespaciais pode ser um grande desafio quando falamos em realizar operações envolvendo geometrias, seja uma simples contagem de pontos ou o cálculo proporcional (que já foi debatido aqui no blog) para o estudo de uma determinada área de influência. O desafio torna-se cada vez maior (exponencialmente maior!) à medida que aumentamos a quantidade de dados geoespaciais sendo analisados, podendo ser desde a quantidade de pontos, quantidade de geometrias analisadas ou até mesmo a quantidade de variáveis da análise.
Uma das maneiras de tornar uma query espacial mais rápida é através da indexação das geometrias na estrutura de árvore. Dados em estrutura de árvores não são novidades para quem conhece alguns algoritmos de machine learning, quem nunca ouviu falar do Random Forest e do Decision Tree?
Aqui na Geo adotamos o R-Tree em nossos projetos, tornando nossas soluções mais robustas e fazendo com que sejam mais rápidas e eficientes, seja de maneira local ou distribuída no cluster (esta parte será assunto em outra postagem aqui do blog!)
O repositório com os scripts em Python apresentados nesse artigo estão no git público da Geo!
Estado da Arte
O R-Tree é uma estrutura de dados para organizar dados geoespaciais, particularmente útil para otimizar a pesquisa de geometrias que se interseccionam com outras geometrias, além de várias outras aplicações.
O conceito por trás do R-Tree se assemelha bastante a uma B-Tree clássica, porém adaptado para a realidade dos dados geoespaciais, ou se visto de outra forma, quaisquer dados multidimensionais.
Em sua organização, cada nó contém um ou mais retângulos no espaço em que está indexando. Os maiores retângulos, ou seja, os nós mais próximos do nó raiz, contém todos os retângulos de seus nós filhos, e os nós-folha (os menores retângulos nesta hierarquia) são os objetos indexados.
Um dos maiores desafios do R-Tree é construir a árvore de tal forma que os nós-folha estejam balanceados (ou seja, estejam na mesma “altura”) e, ao mesmo tempo, garantir que os nós da árvore não englobem muitos espaços vazios e não se intersectem com frequência.
Deve-se ter em mente que ao se inserir novas geometrias, o R-Tree tenta minimizar as mudanças em sua estrutura, ou seja, nos retângulos que são usados para indexar as áreas de busca. Essa estratégia permite uma melhora no tempo de inserção, porém pode levar a um aumento no número de intersecções entre os retângulos da árvore.
Para deixar mais claro como um index do R-Tree é organizado, vamos analisar um exemplo visual.
Nessa imagem, é possível observar retângulos de diferentes cores, onde cada cor está relacionada com um nível diferente da árvore. Os maiores retângulos da estrutura são os retângulos pertencentes ao nó preto, que é o nó-raiz e, por isso, engloba todos os outros nós da árvore. No exemplo acima, o retângulo R1 engloba os retângulos R3, R4 e R5. Já estes, englobam os retângulos abaixo na hierarquia e assim sucessivamente.
Como dissemos anteriormente, a ideia por trás do R-Tree é ser uma estrutura de dados para recuperação eficiente de geometrias. Isso só é possível graças a estratégia que ele adota, de buscar as geometrias de interesse apenas nos subespaços em que elas pertencem.
Por exemplo, imagine que quiséssemos recuperar uma geometria dentro do retângulo R15, da imagem acima. Inicialmente, o R-Tree iria identificar que essa geometria está contida no retângulo R2, em seguida entraria no retângulo R6 e, por fim, chegaria no retângulo R15 que engloba a geometria desejada.
Perceba que o R-Tree direciona quais retângulos contêm as geometrias em que ocorre essa intersecção, ao invés de comparar a geometria procurada com todas as outras geometrias da base de dados, melhorando significativamente o tempo de busca. Em termos de complexidade computacional, a execução de uma busca por intersecções entre n geometrias, deixa de ser O(n²) e passa a ser O(n*log(n)).
Metodologia & Resultados
Nesse artigo, vamos mostrar um exemplo de como o R-Tree pode ser usar para executar uma simples operação em dados geoespaciais. Mas antes, vamos introduzir alguns conceitos que serão usados, começando pelo conceito de setores censitários.
Segundo o IBGE, “O setor censitário é a unidade territorial estabelecida para fins de controle cadastral, formado por área contínua, situada em um único quadro urbano ou rural, com dimensão e número de domicílios que permitam o levantamento por um recenseador”. Ou seja, é uma divisão geográfica baseada no número de domicílios, em média 300.
O problema que queremos resolver é dado um tipo de segmentação geográfica, qual a quantidade de determinados tipos de estabelecimentos em cada segmento. Nesse artigo iremos usar farmácias e restaurantes na contagem de estabelecimentos e setores censitários para realizar a segmentação geográfica. A ideia é mostrar um ganho de performance associado ao aumento da quantidade de buscas, demonstrando que soluções que usam a indexação do R-Tree podem tornar nossas aplicações muito mais escaláveis.
Vale ressaltar que os dados utilizados neste estudo não serão disponibilizados, mas é possível encontrar as geometrias de setor censitário de toda a malha municipal do Brasil no repositório de metadados do IBGE.
A biblioteca que utilizamos é a rtree do Python, que por baixo dos panos usa a libspatialindex, biblioteca em C++.
O script que usamos para fazer a contagem dos pontos de interesse (farmácias e restaurantes) recebe dois dataframes como input, um contendo os pontos, suas respectivas latitude e longitude, e o seu tipo (farmácia ou restaurante). O outro input é um dataframe contendo as geometrias nas quais desejamos realizar a contagem dos pontos de interesse que neste caso será um dataframe com setores censitários.
Começamos criando um index vazio, que irá receber os POI’s (pontos de interesse) indexados. O parâmetro intervealed está relacionado com a maneira com que os pontos serão inseridos. Uma explicação mais completa sobre este assunto encontra-se na documentação oficial da biblioteca. Depois disso, cada um dos pontos do dataframe de polos será inserido em pois_index.
Como pode ser observado, no parâmetro obj passamos tanto a geometria do ponto quanto o seu tipo, isso permitirá com que a contagem seja feita para cada tipo de estabelecimento.
Depois de indexar todos os pontos de interesse, para cada geometria de setor censitário, será criada uma lista com os pontos que intersectam o bounding box da geometria do setor censitário. Essa lista é retornada de maneira muito rápida por causa da estrutura de árvore com a qual os pontos foram organizados.
Após criarmos list_objs teremos uma lista de todos os pontos que intersectam o bounding box da geometria do setor censitário, mas não necessariamente estão contidas dentro dela. Após verificar se os pontos realmente estão contidos na geometria do setor censitário, atribuímos quantos restaurantes e/ou farmácias estão contidos naquele setor censitário.
Para confirmar que o algoritmo R-Tree realmente ajuda a melhorar a performance da nossa aplicação. Foram simulados alguns cenários para ver o ganho de tempo comparado a uma busca randômica com nested loop (que será o método Default) e uma busca que cria uma máscara (Mask), realizando um filtro em função do bounding box da geometria do setor censitário.
Os cenários para análise de performance foram os seguintes: cidade de São Paulo (18953 setores censitários e 2412 pontos), estado de São Paulo (68296 setores censitários e 4982 pontos) e Brasil inteiro (316573 setores censitários e 13537 pontos).
Através das figuras 4 e 5 podemos ver que o aumento no tempo do processo conforme a quantidade de buscas (iterações) aumenta, fazendo com que o método Default chegue a 18 mil segundos, enquanto uma busca otimizada usando R-Tree sequer chega a um minuto (aproximadamente 45 segundos).
Na primeira impressão pode parecer que o R-Tree não apresentou uma grande melhora quando comparado com a máscara feita a partir do bounding box da geometria dos setores censitários, contudo, através das figuras 6 e 7, onde compararmos apenas os dois métodos, pode-se perceber que o tempo para realizar a mesma tarefa é 16 vezes menor do que quando usamos a máscara (que demora 12 minutos). Fazendo esta análise também podemos notar que para uma quantidade maior de geometrias (na ordem de milhões, por exemplo) esse ganho seria maior ainda em relação aos outros dois métodos.
Conclusão
Por fim, podemos ver um grande ganho de tempo ao usar o R-Tree na realização de queries espaciais, tornando nossa solução muito mais escalável quando pensamos em uma grande massa de dados.
Neste artigo foi visto:
1 — Introdução teórica sobre o algoritmo R-Tree;
2 — Estudo de caso comparando diferentes cenários e vendo um ganho exponencial de tempo.
Mais sobre árvores:
Referências
- R-Tree: https://en.wikipedia.org/wiki/R-tree
- Biblioteca R-Tree: https://toblerity.org/rtree/index.html
- B-Tree: https://en.wikipedia.org/wiki/B-tree
- Bouding Box: https://en.wikipedia.org/wiki/Minimum_bounding_box
