View
0
Download
0
Category
Preview:
Citation preview
Indexação de dados espaciais
R-Tree
CCO229 – Bancos de dados Espaciais e Biológicos
Prof. Ricardo Rodrigues Ciferri
Debora Marrach
Indexação de dados espaciais
R-TreeIntrodução
R-Tree
É o método de acesso espacial mais referenciado na
literatura
É o mais importante dentre os métodos que aplicam o
conceito de MBR (Minimum Bounding Rectangle, ou
retângulo limítrofe mínimo)
Indexação de dados espaciais
R-TreeEstrutura de dados
R-Tree
A R-Tree é uma estrutura em árvore balanceada em função da
altura
As folhas contém ponteiros para os atributos não espaciais dos
objetos.
Os nós correspondem as páginas de disco
Indexação de dados espaciais
R-TreeEstrutura de dados
Folhas
Cada folha contém entradas do tipo (I, Tid)
Tid se refere (pode ser um ponteiro) a uma tupla na base de
dados, contendo os atributos não espaciais do objeto
I corresponde ao MBR do objeto descrito por Tid
Indexação de dados espaciais
R-TreeEstrutura de dados
Nós
Cada nó interno contém entradas do tipo (I, Cid)
Cid é um ponteiro para algum filho
I corresponde ao MBR que cobre todas as regiões descritas
pelos MBR dos nós inferiores
Sendo M o número máximo de entradas em um nó, m ≤ M/2 especifica
o número mínimo de entradas em um nó
Indexação de dados espaciais
R-TreeEstrutura de dados
Indexação de dados espaciais
R-TreeEstrutura de dados
Indexação de dados espaciais
R-TreeEstrutura de dados
Propriedades
Toda folha contém entre m e M entradas, exceto a raiz
Todo nó interno tem entre m e M filhos, a menos que seja a raiz
A raiz tem no mínimo dois filhos, a menos que seja uma folha
Todas as folhas aparecem no mesmo nível
Indexação de dados espaciais
R-TreeEstrutura de dados
Propriedades
A altura de uma R-Tree com N registros é no máximo
|logmN|-1, porque o número mínimo de entradas por nó é m
O número máximo de nós é [N/m] + [N/m2]+...+1
A pior taxa de ocupação para todos os nós, exceto para raiz, é
m/M
Os nós tendem a ter mais do que m entradas, o que irá diminuir
a altura da árvore e melhorar a taxa de ocupação
Indexação de dados espaciais
R-Tree
Algorítmos
Para os algoritmos a serem demonstrados:
Considere E.I como sendo o MBR referente à entrada E
Considere E.p como sendo um Tid (identificador da tupla) ou
Cid (identificador de um ponteiro para o nó abaixo)
Indexação de dados espaciais
R-Tree
Algorítmos
Consulta
A consulta na R-Tree é similar à feita na B-Tree. Pode ser
necessário percorrer mais do que uma sub-árvore de um
determinado nó aumentando o custo da consulta
Os algoritmos de inserção e particionamento devem ser
projetados de forma a minimizar este aumento do custo
Indexação de dados espaciais
R-Tree
Algorítmos
Consulta
Encontrar todas as entradas cujos MBRs coincidem com a janela de
consulta S, a partir da R-Tree cuja raiz é indicada por T
1. Se T é um nó interno, percorra todas as suas entradas E para
verificar se E.I faz interseção com S. Para todas as entradas que
fazem interseção, execute este passo novamente, considerando T
como sendo a sub-árvore apontada por E.p
2. Se T é uma folha, percorra todas as entradas E para verificar se E.I
faz interseção com S. Se as entradas fazem interseção, então
compõem o conjunto resposta
Indexação de dados espaciais
R-Tree
Algorítmos
Inserção
Inserção na R-Tree é similar à feita na B-Tree, sendo que
novas entradas são acrescentadas nas folhas, e os nós que
ultrapassam a capacidade máxima de entradas (M) são
particionados
O particionamento é, então, propagado para os pais
Indexação de dados espaciais
R-Tree
Algorítmos
Inserção
Os algoritmos de inserção e particionamento devem ser
projetados de forma a minimizar este aumento do custo nos
algorítmos de consulta
Indexação de dados espaciais
R-Tree
Algorítmos
Inserção
A ramificação do percurso inicial pode ser aumentada caso a
JC intersecte o MBB de um grande número de entradas de
um nó interno
Isso pode acontecer em três condições:
a. Sobreposição entre MBBs das entradas de um nó interno
b. Armazenamento de MBBs grandes
c. Escolha de uma JC abrangente
Indexação de dados espaciais
R-Tree
Algorítmos
InserçãoRamificação do percurso pela sobreposição de
MBB das entradas de um nó interno
E1
E2
E3
janela de consulta
Indexação de dados espaciais
R-Tree
Algorítmos
Inserção
Ramificação do percurso pelo armazenamento de MBB grandes
E3E1
E2
Entradas (MBB)
Extent
Janela de
ConsultaJC
Indexação de dados espaciais
R-Tree
Algorítmos
InserçãoRamificação do percurso pela escolha de uma JC abrangente
E3E1
E2
Entradas (MBB)
Extent
Janela de
Consulta
JC
Indexação de dados espaciais
R-Tree
Algorítmos
InserçãoInsere uma nova entrada E em uma R-Tree
1. Use EscolheFolha para obter a folha L onde E deve ser incluído
2. Se L tem espaço para mais uma entrada, insira E. Caso contrário, use ParticionaNo para obter L e LL contendo E e as antigas entradas de L
3. Use AjustarÁrvore passando L como parâmetro para propagar as mudanças necessárias árvore acima. Se L foi particionado, passe LL também
4. Se a propagação do particionamento ao longo da árvore provocou o particionamento da raiz, crie uma nova raiz tendo os dois nós gerados como filhos
Indexação de dados espaciais
R-Tree
Algorítmos
EscolheFolha
Seleciona a folha em que E será inserida
1. Faça N corresponder à raiz
2. Se N é uma folha, retorne N
3. Senão, faça F corresponder à entrada de N cujo MBR F.I
necessita de menor expansão para englobar E.I. No caso de
empate, escolha a entrada com MBR de menor área
4. Faça N corresponder ao filho de F referenciado por F.p.
Retorne ao passo 2
Indexação de dados espaciais
R-Tree
Algorítmos
AjustaArvorePercorre a árvore acima, ajustando os MBRs e propagando os
particionamentos
1. Faça N = L. Se L foi particionado anteriormente, faça NN corresponder ao nó resultante do particionamento
2. Se N é a raiz, encerre
3. Considere P como sendo o pai de N e En como sendo a entrada de P referente a N. Ajuste En.I para englobar todos os MBRs de N
4. Se NN foi gerado, crie uma nova entrada Enn, com Enn.p referenciando NN e Enn.I englobando todos os MBRs de NN. Se houver espaço em P, insira Enn. Caso contrário, use ParticionaNopara obter P e PP contendo Enn e as antigas entradas de P
5. Faça N = P. Se N foi particionado, faça NN = PP. Retorne ao passo 2
Indexação de dados espaciais
R-Tree
Algorítmos
Remoção
Remove uma entrada E de uma R-Tree
1. Use EncontraFolha para obter a folha L que contém E. Se a
entrada E não foi encontrada, encerre
2. Remova E de L
3. Execute CondensaArvore, passando L como parâmetro
4. Se a raiz ficou com apenas um filho após o passo anterior,
transforme este filho na nova raiz
Indexação de dados espaciais
R-Tree
Algorítmos
EncontraFolha
Encontra a folha que contém a entrada E, a partir da R-Tree cuja raiz é
indicada por T
1. Se T é um nó interno, percorra todas as suas entradas F para
verificar se F.I faz interseção com E.I. Para cada entrada que
faz interseção, execute este passo novamente considerando
T como sendo a sub-árvore apontada por F.p, até que E seja
encontrado ou que todas as sub-árvores tenham sido
checadas
2. Se T é uma folha, percorra cada entrada para verificar se
corresponde à entrada E. Se E for encontrado, retorne T
Indexação de dados espaciais
R-Tree
Algorítmos
CondensaArvore
Dada uma folha L, da qual uma entrada foi removida:
Eliminar esta folha caso tenha um número de entradas menor
do que o mínimo m, e re-inserir suas entradas
Propagar a eliminação desta folha, se necessário
Ajustar todos os MBRs árvore acima
Indexação de dados espaciais
R-Tree
Algorítmos
CondensaArvore
1. Faça N = L. Considere Q como sendo um conjunto que irá conter os nós eliminados, inicialmente vazio
2. Se N é a raiz, vá para o passo 6. Caso contrário, considere P como sendo o pai de N e En como sendo a entrada a entrada de P referente a N
3. Se N tem menos do que m entradas, elimine En de P e insira em Q
4. Se N não foi eliminado, ajuste En.I de forma a englobar todos os MBRs de N
5. Faça N = P. Retorne ao passo 2
Indexação de dados espaciais
R-Tree
Algorítmos
CondensaArvore
6. Re-insira todas as entradas existentes em Q.
As entradas que faziam parte de folhas, são re-inseridas em
folhas, da mesma forma que no Algoritmo 5 (Inserção).
Mas, entradas que faziam parte de nós internos têm que ser
re-inseridas no mesmo nível em que se encontravam, de
forma que as folhas das sub-árvores referentes às suas
entradas fiquem no mesmo nível que as outras folhas da
árvore principal
Indexação de dados espaciais
R-Tree
Algorítmos
Particionamento
O particionamento deve ser feito de forma a evitar que os dois nós gerados tenham sempre de ser percorridos na execução de uma consulta
Um nó deve ou não ser percorrido, conforme o seu MBR total faça ou não interseção com o intervalo de consulta
Para tanto, a área total dos MBRs de cada um dos nós gerados a partir do particionamento, deve ser a menor possível
Indexação de dados espaciais
R-Tree
Algorítmos
Particionamento
Algoritmo Exaustivo
A forma mais direta de se encontrar os dois nós de áreas
mínimas é testar todas as possibilidades de agrupamento das
M+1 entradas e escolher a melhor
O número de possibilidades é aproximadamente 2M-1
Um valor razoável para M é 50, e assim o número de
agrupamentos possíveis é consideravelmente grande
Indexação de dados espaciais
R-Tree
Algorítmos
Particionamento
Algoritmo Quadrático
Encontrar uma combinação de entradas com área pequena
Não se garante, que seja esta a melhor combinação possível
O custo é quadrático em relação a M e linear em relação ao
número de dimensões
Indexação de dados espaciais
R-Tree
Algorítmos
ParticionamentoAlgoritmo Quadrático
Obter duas entradas (dentre as M+1) como sementes
(primeira entrada) para compor os dois grupos que serão
gerados após o particionamento
Calcula-se a ineficiência de agrupamento para todos os pares
de entrada, o qual consiste na área de dead space no MBB
gerado por ambas entradas quando alocadas conjuntamente
Escolhe-se o par com o maior desperdício de área
As entradas restantes são escolhidas e inseridas como
descrito a seguir
Indexação de dados espaciais
R-Tree
Algorítmos
Particionamento
Algoritmo Quadrático
Dividir um grupo de M+1 entradas em dois grupos:
1. Execute ObtémSementes para escolher as duas primeiras
entradas e inclua uma em cada grupo
2. Se todas as entradas já foram inseridas, encerre.
Popule os grupos que não possuam o número mínimo de
entradas. Caso já se tenha inserido todas as entradas
encerre.
Indexação de dados espaciais
R-Tree
Algorítmos
ParticionamentoAlgoritmo Quadrático
3. Execute ObtémPróximaEntrada para obter a próxima entrada a ser inserida. Insira conforme a prioridade abaixo:I. Grupo cujo MBR total terá que ser menos expandido após a
inserção.
II. Na ocorrência de empate, a inserção é feita naquele de menor área total.
III. Naquele com menor número de entradas
IV. No que apresenta os dois casos.
4. Retorne ao passo 2.
Indexação de dados espaciais
R-Tree
Algorítmos
Particionamento - ObtémSementes
Algoritmo Quadrático
Seleciona duas entradas para serem as primeiras de cada
grupo:
1. Para cada par de entradas, E1 e E2, componha um MBR J
que engloba E1.I e E2.I. Calcule: d = área(J) - área(E1.I) -
área(E2.I)
2. Escolha o nó que apresenta o maior valor de d
Indexação de dados espaciais
R-Tree
Algorítmos
Particionamento - ObtémPróximaEntradaAlgoritmo Quadrático
Escolhe uma entrada, dentre as que restam, para ser testada em um grupo:
1. Para cada entrada E que ainda não foi inserida em um dos grupos, calcule d1 = aumento necessário à área do MBR total do primeiro grupo para incluir E.I. Para o segundo grupo, calcule d2 da mesma forma
2. Escolha qualquer entrada que apresente a máxima diferença entre d1 e d2
Indexação de dados espaciais
R-Tree
Algorítmos
Particionamento
Algoritmo Linear
Este algoritmo apresenta custo linear em relação a M e ao
número de dimensões. É basicamente idêntico ao anterior,
mas usa uma versão diferente do Algoritmo
ObtémSementes
Além disto, o Algoritmo ObtémPróximaEntrada, escolhe
qualquer entrada dentre as que ainda restam
Indexação de dados espaciais
R-Tree
Algorítmos
Particionamento – ObtémSementesLinear
Algoritmo Linear
Seleciona duas entradas para serem as primeiras de cada grupo
1. Ao longo de cada dimensão, encontre a entrada cujo MBR
tem o lado inferior mais alto e a que tem o lado superior mais
baixo. Armazene a distância entre eles
2. Normalize as distâncias dividindo pelo tamanho de todo o
conjunto ao longo da dimensão correspondente
3. Escolha o par com a maior distância normalizada, dentre
todas as dimensões
Indexação de dados espaciais
R-Tree
Algorítmos
Particionamento – ObtémSementesLinear
Algoritmo Linear
Cálculo da distância com relação á dimensão x
x
y
mais alto lado inferiormais baixo lado
superior
Recommended