Submitted by Franciele Moreira (francielemoreyra@gmail.com) on 2017-12-12T16:13:05Z
No. of bitstreams: 2
Tese - Thiago Borges de Oliveira - 2017.pdf: 1684209 bytes, checksum: f64b32084ca6b13a58109e4d2cffe541 (MD5)
license_rdf: 0 bytes, checksum: d41d8cd98f00b204e9800998ecf8427e (MD5) / Approved for entry into archive by Luciana Ferreira (lucgeral@gmail.com) on 2017-12-13T09:33:57Z (GMT) No. of bitstreams: 2
Tese - Thiago Borges de Oliveira - 2017.pdf: 1684209 bytes, checksum: f64b32084ca6b13a58109e4d2cffe541 (MD5)
license_rdf: 0 bytes, checksum: d41d8cd98f00b204e9800998ecf8427e (MD5) / Made available in DSpace on 2017-12-13T09:33:57Z (GMT). No. of bitstreams: 2
Tese - Thiago Borges de Oliveira - 2017.pdf: 1684209 bytes, checksum: f64b32084ca6b13a58109e4d2cffe541 (MD5)
license_rdf: 0 bytes, checksum: d41d8cd98f00b204e9800998ecf8427e (MD5)
Previous issue date: 2017-11-29 / Multiway spatial join is an important type of query in spatial data processing, and its
efficient execution is a requirement to move spatial data analysis to scalable platforms
as has already happened with relational and unstructured data. In this thesis, we provide
a set of comprehensive models and methods to efficiently execute multiway spatial join
queries in distributed systems. We introduce a cost-based optimizer that is able to select a
good execution plan for processing such queries in distributed systems taking into account:
the partitioning of data based on the spatial attributes of datasets; the intra-operator level
of parallelism, which enables high scalability; and the economy of cluster resources by
appropriately scheduling the queries before execution. We propose a cost model based on
relevant metadata about the spatial datasets and the data distribution, which identifies the
pattern of costs incurred when processing a query in this environment. We formalized the
distributed multiway spatial join plan scheduling problem as a bi-objective linear integer
model, considering the minimization of both the makespan and the communication cost
as objectives. Three methods are proposed to compute schedules based on this model
that significantly reduce the resource consumption required to process a query. Although
targeting multiway spatial join query scheduling, these methods can be applied to other
kinds of problems in distributed systems, notably problems that require both the alignment
of data partitions and the assignment of jobs to machines. Additionally, we propose a
method to control the usage of resources and increase system throughput in the presence
of constraints on the network or processing capacity. The proposed cost-based optimizer
was able to select good execution plans for all queries in our experiments, using public
datasets with a significant range of sizes and complex spatial objects. We also present an
execution engine that is capable of performing the queries with near-linear scalability with
respect to execution time. / A multi-junção espacial é um tipo importante de consulta usada no processamento de
dados espaciais e sua execução eficiente é um requisito para mover a análise de dados
espaciais para plataformas escaláveis, assim como aconteceu com dados relacionais e não
estruturados. Nesta tese, propomos um conjunto de modelos e métodos para executar eficientemente
consultas de multi-junção espacial em sistemas distribuídos. Apresentamos um
otimizador baseado em custos que seleciona um bom plano de execução levando em consideração:
o particionamento de dados com base nos atributos espaciais dos datasets; o nível
de paralelismo intra-operador que proporciona alta escalabilidade; e o escalonamento das
consultas antes da execução que resulta em economia de recursos computacionais. Propomos
um modelo de custo baseado em metadados dos datasets e da distribuição de dados,
que identifica o padrão de custos incorridos no processamento de uma consulta neste ambiente.
Formalizamos o problema de escalonamento de planos de execução da multi-junção
espacial distribuída como um modelo linear inteiro bi-objetivo, que minimiza tanto o custo
de processamento quanto o custo de comunicação. Propomos três métodos para gerar escalonamentos
a partir deste modelo, os quais reduzem significativamente o consumo de
recursos no processamento das consultas. Embora projetados para o escalonamento da
multi-junção espacial, esses métodos podem também ser aplicados a outros tipos de problemas
em sistemas distribuídos, que necessitam do alinhamento de partições de dados
e da distribuição de tarefas a máquinas de forma balanceada. Além disso, propomos um
método para controlar o uso de recursos e aumentar a vazão do sistema na presença de
restrições nas capacidades da rede ou de processamento. O otimizador proposto foi capaz
de selecionar bons planos de execução para todas as consultas em nossos experimentos, as
quais usaram datasets públicos com uma variedade significativa de tamanhos e de objetos
espaciais complexos. Apresentamos também uma máquina de execução, capaz de executar
as consultas com escalabilidade próxima de linear em relação ao tempo de execução.
| Identifer | oai:union.ndltd.org:IBICT/oai:repositorio.bc.ufg.br:tede/8033 |
| Date | 29 November 2017 |
| Creators | Oliveira, Thiago Borges de |
| Contributors | Costa, Fábio Moreira, Foulds, Leslie Richard, Rodrigues, Vagner José do Sacramento, Costa, Fábio Moreira, Foulds, Leslie Richard, Rodrigues, Vagner José do Sacramento, Braghetto, Kelly Rosa, Meneses, Cláudio Nogueira de |
| Publisher | Universidade Federal de Goiás, Programa de Pós-graduação em Ciência da Computação em Rede UFG/UFMS (INF), UFG, Brasil, Instituto de Informática - INF (RG) |
| Source Sets | IBICT Brazilian ETDs |
| Language | Portuguese |
| Detected Language | English |
| Type | info:eu-repo/semantics/publishedVersion, info:eu-repo/semantics/doctoralThesis |
| Format | application/pdf |
| Source | reponame:Biblioteca Digital de Teses e Dissertações da UFG, instname:Universidade Federal de Goiás, instacron:UFG |
| Rights | http://creativecommons.org/licenses/by-nc-nd/4.0/, info:eu-repo/semantics/openAccess |
| Relation | -3303550325223384799, 600, 600, 600, -7712266734633644768, 3671711205811204509 |
Page generated in 0.003 seconds