Processamento distribuído da junção espacial de múltiplas bases de dados: multi-way spatial join

A junção espacial (Spatial Join) é uma das operações espaciais de maior custo computacional. Sua complexidade aumenta significativamente quando envolve múltiplas bases de dados (multi-way spatial join). Estratégias tradicionais de processamento do multi-way spatial join aplicam combinações de algoritmos de junção binária sobre ambientes computacionais centralizados. Em consultas complexas, esse tipo de abordagem exige grande capacidade computacional muitas vezes inviável em ambientes centralizados. Neste trabalho é proposto o algoritmo Distributed Synchronous Traversal (DST), cujo objetivo é tornar viável a execução distribuída do multi-way spatial join em um cluster de computadores. O DST se baseia no algoritmo Synchronous Traversal e processa o multiway spatial join em uma única descida síncrona sobre os níveis das R-Trees das bases de dados de entrada. O resultado final é construído incrementalmente, sem a consolidação de dados intermediários. Até onde conhecemos, não há outras propostas na literatura para multi-way spatial join distribuído sobre uma arquitetura peer-to-peer. Muitos desafios tiveram que ser superados, como a definição de estruturas de dados que possibilitassem o mapeamento da semântica das consultas de multi-way spatial join e a coordenação do processamento distribuído das mesmas. O DST se mostrou satisfatoriamente paralelizável e escalável ao processar bases de dados reais em clusters de até 8 servidores.Spatial join is one of the spatial operations of higher computational cost. Its complexity increases significantly when it involves multiple databases (multi-way spatial join). Traditional processing strategies of multi-way spatial join apply combinations of binary join algorithms on centralized computing environments. For complex queries, this approach requires much computational power, making it often unfeasible in centralized environments. This work proposes the Distributed Synchronous Traversal algorithm (DST), whose goal is to enable the distributed processing of multi-way spatial joins on a cluster of computers. The DST algorithm is based on Synchronous Traversal algorithm and processes the multiway spatial join in a single synchronous descent upon R-Trees levels of the database entries (the final outcome is built incrementally, without creating temporary databases). To the best of our knowledge, there are no other proposals in the literature that deal with this problem in a distributed fashion and on a peer-to-peer architecture. Many challenges had to be overcome, such as the definition of data structures that enabled the mapping of the semantics of queries of multi-way spatial join and coordination of the required distributed processing. DST proved to be satisfactorily parallelizable and scalable process real datasets in experiments performed in clusters of 1, 2, 4 and 8 servers