Arvore GRID

Prévia do material em texto

ESTRUTURA 
ESPACIAL
GRID
2
PROFESSOR:
Dr. Guilherme Tavares de Assis
DISCIPLINA:
Estrutura de Dados II
Estrutura de Dados Espaciais
3
▰ Os dados espaciais representam informações sobre o local físico e a forma 
de objetos geométricos
▰ Uma operação comum com dados espaciais é a busca por objetos em uma 
determinada área.
▰ Ex: Deseja-se determinar quantos restaurantes estão localizados em um 
raio de 50km.
▰ Uma estrutura proposta para lidar com dados espaciais é a Grid.
GRID
4
1
5
▰ Na figura ao lado é possível 
perceber a divisão do plano 
em células.
▰ Pontos próximos uns dos 
outros ficam em uma mesma 
célula (8 e 9, por exemplo).
O tamanho ideal do bucket é dependente de 2 condições:
▰ Quanto maior o número total de pontos, maior o número de 
células requeridas
▰ O tamanho da célula é dependente na magnitude da faixa 
média das range query suportadas pelo sistema
6
▰ A população de células com ponto variam, em alguns casos 
existem células vazias
▰ Se os pontos forem menos uniformemente distribuídos este 
problema piora
Solução: Usar Grid files
DESVANTAGEM DE GRID
7
GRID FILES
8
2
É uma extensão de grid que permite as linhas de divisão das células terem 
tamanhos arbitrários.
O método de indexação Grid Files estende o conceito de Hashing para duas 
dimensões. Assim, ao invés de n buckets, teremos uma grade que cobre 
todo o espaço de pesquisa.
9
▰ Leva em consideração a distribuição dos pontos;
▰ Um novo nível de indireção é criado: o grid directory;
▰ Células no grid podem ter dados compartilhados apenas se sua união forma 
um retângulo;
▰ Uma célula pode expandir ou ser contraída à medida que novos dados são 
inseridos/removidos;
▰ Um retângulo pode ser dividido se ele se torna muito cheio e células podem 
ser juntas num único retângulo se estas se tornam muito vazias;
▰ No exemplo do slide seguinte as 16 células na estrutura anterior foram 
reduzidas para 8 células.
10
11
Inserção
Localizar onde o ponto deve ser 
inserido. 
Se o bucket apontado pela 
célula ainda tem espaço, insere 
o ponto.
12
Inserção
Caso o bucket apontado pela 
célula não tem espaço.
13
Inserção
Divide o bucket e tenta a 
inserção novamente.
14
Remoção
Localiza o ponto e retira o ponto 
da célula.
15
Remoção
16
Vantagens:
▰ Pode ser utilizado para pesquisa de uma única chave.
▰ Retorna somente os resultados corretos.
▰ Melhora significativa no tempo de processamento de consulta de 
múltiplas chaves.
CONSIDERAÇÕES FINAIS
17
Desvantagem:
▰ A principal limitação do método Grid, é o fato de somente poder 
lidar com pontos, ou com objetos que caiba inteiramente em um 
quadrado. Não é um método adequado para lidar com linhas ou 
polígonos, mas é bastante eficiente e simples de implementar para 
o tratamento de dados pontuais.
18
▰ http://www.dsc.ufcg.edu.br/~baptista/cursos/SIG/Unidade31.ppt
▰ https://prezi.com/1wfvudsxrein/grid
▰ http://webserver2.tecgraf.puc-rio.br/eda/referencias/R-Trees-BDG-
cap6.pdf
▰ http://www.cs.ucr.edu/~tsotras/cs236/W15/grid-file.pdf
19
REFERÊNCIAS
20
THANKS!
Perguntas?
Frederico Sousa, Hugo Ziviani, Suzan Gomes, Philipe Lemos, 
Letícia Rezende, Felipe Augusto.