Submitted by Erika Demachki (erikademachki@gmail.com) on 2014-12-29T15:33:04Z
No. of bitstreams: 2
license_rdf: 23148 bytes, checksum: 9da0b6dfac957114c6a7714714b86306 (MD5)
Dissertação - Anderson Rogério Cunha - 2014.pdf: 4853685 bytes, checksum: d50cf557f1a067a91c2034443ee62df2 (MD5) / Approved for entry into archive by Erika Demachki (erikademachki@gmail.com) on 2014-12-29T15:39:23Z (GMT) No. of bitstreams: 2
license_rdf: 23148 bytes, checksum: 9da0b6dfac957114c6a7714714b86306 (MD5)
Dissertação - Anderson Rogério Cunha - 2014.pdf: 4853685 bytes, checksum: d50cf557f1a067a91c2034443ee62df2 (MD5) / Made available in DSpace on 2014-12-29T15:39:23Z (GMT). No. of bitstreams: 2
license_rdf: 23148 bytes, checksum: 9da0b6dfac957114c6a7714714b86306 (MD5)
Dissertação - Anderson Rogério Cunha - 2014.pdf: 4853685 bytes, checksum: d50cf557f1a067a91c2034443ee62df2 (MD5)
Previous issue date: 2014-02-19 / Coordenação de Aperfeiçoamento de Pessoal de Nível Superior - CAPES / 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. / 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.
| Identifer | oai:union.ndltd.org:IBICT/oai:repositorio.bc.ufg.br:tede/3836 |
| Date | 19 February 2014 |
| Creators | Cunha, Anderson Rogério |
| Contributors | Rodrigues, Vagner José do Sacramento, Rodrigues, Vagner José do Sacramento, Davis Júnior, Clodoveu Augusto, Cardoso, Kleber Vieira |
| Publisher | Universidade Federal de Goiás, Programa de Pós-graduação em Ciência da Computação (INF), UFG, Brasil, Instituto de Informática - INF (RG) |
| Source Sets | IBICT Brazilian ETDs |
| Language | Portuguese |
| Detected Language | Portuguese |
| Type | info:eu-repo/semantics/publishedVersion, info:eu-repo/semantics/masterThesis |
| Format | application/pdf |
| Source | reponame:Biblioteca Digital de Teses e Dissertações da UFG, instname:Universidade Federal de Goiás, instacron:UFG |
| Rights | info:eu-repo/semantics/openAccess |
| Relation | -3303550325223384799, 600, 600, 600, 600, -7712266734633644768, 8930092515683771531, 2075167498588264571 |
Page generated in 0.0027 seconds