Resumo: Multijunções são consultas fundamentais para o processamento de dados espaciais. Este artigo apresenta modelos e algoritmos para escalonar esse tipo de consulta em sistemas de banco de dados distribuídos, buscando um equilíbrio entre o tempo de execução e a comunicação — tráfego de dados na rede. Propomos três algoritmos baseados em métodos de otimização combinatória: a conhecida técnica de relaxamento linear que arredonda uma solução gerada por programação linear (LP), um método mais sofisticado usando Relaxamento Lagrangiano (LR), e uma heurística gulosa (GR) como baseline de comparação. Nossa avaliação mostrou que um escalonamento construído utilizando o método GR consome, em média, 22% mais recursos de processamento e comunicação do que um escalonamento mais elaborado construído com o método LR, para uma consulta usando 64 computadores. O escalonamento gerado pelo método LR também é, em média, uma ordem de grandeza mais próximo de um escalonamento ótimo, comparado ao método GR. Mostramos que o escalonamento de consultas com muitos dados — da ordem de Gigabytes, antes de sua execução, pode reduzir seu tempo de processamento em uma ordem de grandeza, comparado a outros sistemas de última geração para processamento de dados espaciais que não possuem o recurso de agendamento, além de reduzir significativamente a quantidade de dados trafegados na rede.

Palavras-chave: Multijunção Espacial; Escalonamento de Consultas Distribuídas; Relaxação Lagrangiana.

Artigo completo

Citação: Thiago Borges de Oliveira; Fábio M. Costa; Les R. Foulds; Humberto J. Longo. Escalonamento de consultas distribuídas de multijunção espacial: modelos de otimização e algoritmos. International Journal of Geographical Information Science, 37(3), 1--33, 2023. DOI: 10.1080/13658816.2023.2170380

Copiar citação no formato bibtex.