Efficient processing of multiway spatial join queries in distributed systems

Página do item simplificado
dc.contributor.advisor-co1Foulds, Leslie Richard
dc.contributor.advisor-co1Latteshttp://lattes.cnpq.br/3737395828552021eng
dc.contributor.advisor-co2Rodrigues, Vagner José do Sacramento
dc.contributor.advisor-co2Latteshttp://lattes.cnpq.br/4148896613580056eng
dc.contributor.advisor1Costa, Fábio Moreira
dc.contributor.advisor1Latteshttp://lattes.cnpq.br/0925150626762308eng
dc.contributor.referee1Costa, Fábio Moreira
dc.contributor.referee2Foulds, Leslie Richard
dc.contributor.referee3Rodrigues, Vagner José do Sacramento
dc.contributor.referee4Braghetto, Kelly Rosa
dc.contributor.referee5Meneses, Cláudio Nogueira de
dc.creatorOliveira, Thiago Borges de
dc.creator.Latteshttp://lattes.cnpq.br/5108431745414375eng
dc.date.accessioned2017-12-13T09:33:57Z
dc.date.issued2017-11-29
dc.description.abstractMultiway 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.eng
dc.description.provenanceSubmitted 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)eng
dc.description.provenanceApproved 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)eng
dc.description.provenanceMade 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-29eng
dc.description.resumoA 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.eng
dc.formatapplication/pdf*
dc.identifier.citationOLIVEIRA, Thiago Borges de. Efficient processing of multiway spatial join queries in distributed systems. 2017. 156 f. Tese (Doutorado em Ciência da Computação em Rede) - Universidade Federal de Goiás, Goiânia, 2017.eng
dc.identifier.urihttp://repositorio.bc.ufg.br/tede/handle/tede/8033
dc.languageporeng
dc.publisherUniversidade Federal de Goiáseng
dc.publisher.countryBrasileng
dc.publisher.departmentInstituto de Informática - INF (RG)eng
dc.publisher.initialsUFGeng
dc.publisher.programPrograma de Pós-graduação em Ciência da Computação em Rede UFG/UFMS (INF)eng
dc.rightsAcesso Aberto
dc.rights.urihttp://creativecommons.org/licenses/by-nc-nd/4.0/
dc.subjectDistributed multiway spatial joineng
dc.subjectCost-based optimizereng
dc.subjectJob schedulingeng
dc.subjectHistogramseng
dc.subjectMulti-junção espacial distribuídapor
dc.subjectOtimizador baseado em custospor
dc.subjectEscalonamento de tarefaspor
dc.subjectHistogramaspor
dc.subject.cnpqCIENCIAS EXATAS E DA TERRA::CIENCIA DA COMPUTACAOeng
dc.titleEfficient processing of multiway spatial join queries in distributed systemseng
dc.title.alternativeProcessamento eficiente de consultas de multi-junção espacial em sistemas distribuídospor
dc.typeTeseeng

Arquivos

Pacote Original
Agora exibindo 1 - 1 de 1
Nenhuma Miniatura disponível
Nome:
Tese - Thiago Borges de Oliveira - 2017.pdf
Tamanho:
1.61 MB
Formato:
Adobe Portable Document Format
Baixar
Licença do Pacote
Agora exibindo 1 - 1 de 1
Nenhuma Miniatura disponível
Nome:
license.txt
Tamanho:
2.11 KB
Formato:
Item-specific license agreed upon to submission
Descrição:
Baixar

Coleções

Doutorado em Ciência da Computação em Rede - UFMS/UFG (INF)