R-Trees Temporais para Sistemas de Informações Geográficas

Prévia do material em texto

1
RESUMO
Projeto e Avaliação de R-Trees Temporais
Victor Teixeira de Almeida
Renata Chaomey Wo
Orientadores: Geraldo Zimbrão da Silva
Jano Moreira de Souza
É um fato conhecido que as novas aplicações de Sistemas de Informações Geográficas
(SIG) necessitam armazenar informações temporais. Entretando, a estrutura de índices
espaciais mais conhecida, a R-Tree e suas variantes, não preserva a evolução dos MBRs
(Minimum Bounding Rectangles – Menores Retângulos Envolventes). Uma primeira
abordagem seria adicionar mais uma dimensão ao espaço de dados para lidar com o tempo,
porém este método é ineficiente. Neste trabalho, nós propomos um método alternativo: uma
nova estrutura de índice chamada de R-Tree Temporal que tem a capacidade de tratar de
dados espaço-temporais. A R-Tree Temporal, ou TR-Tree, permite a recuperação de estados
presentes e passados dos dados. Há duplicação de dados, mas essa duplicação é mantida
pequena graças ao mecanismo de cópia de blocos (block copying). O tempo de busca para
consultas por instante de tempo é comparável ao da R-Tree original e o tempo de busca para
consultas por intervalo de tempo supera em muito as abordagens existentes.
2
ABSTRACT
Design and Evaluation of Temporal R-Trees
Victor Teixeira de Almeida
Renata Chaomey Wo
Orientadores: Geraldo Zimbrão da Silva
Jano Moreira de Souza
It's a well-known fact that the new GIS (Geographic Information System) applications
need to keep track of temporal information. However, the best known spatial index structure,
the R-Tree and its variants, does not preserve the MBRs (Minimum Bounding Rectangles)
evolution. A first approach would be to add one more dimension to data space to store time
information, but this method is inefficient. In this work, we propose an alternative approach:
a new index structure called Temporal R-Tree that deals with spatiotemporal data. The
Temporal R-Tree, or TR-Tree, allows the retrieval of present and past states of data. There is
data duplication, but this duplication is kept small because of the block copying mechanism.
The retrieval time of the point query is comparable to the original R-Tree and the retrieval
time of the interval range query is better than that of the existing approaches.
3
Índice
1. Introdução.......................................................................................................................... 4
2. Trabalhos Relacionados..................................................................................................... 6
2.1. R-Tree............................................................................................................................. 6
2.2. Métodos de Acesso Temporais....................................................................................... 7
2.3. Estruturas de Índice Espaço-Temporais ......................................................................... 8
3. Estrutura de Índice da TR-Tree ....................................................................................... 11
4. Algoritmos de Busca, Remoção e Inserção ......................................................................... 14
4.1. Busca em instante de tempo ......................................................................................... 15
4.2. Inserção......................................................................................................................... 15
4.3. Remoção ....................................................................................................................... 18
4.4. Consulta por intervalo de tempo................................................................................... 18
4.5. Operações em bloco...................................................................................................... 19
5. Exemplo............................................................................................................................... 20
6. Resultados Experimentais ................................................................................................... 26
6.1. Dados de Teste.............................................................................................................. 26
6.2. Testes............................................................................................................................ 28
7. Conclusões........................................................................................................................... 32
8. Bibliografia.......................................................................................................................... 33
4
1. Introdução
Neste trabalho descreveremos um método para tornar a família de estruturas de
índices das R-Trees parcialmente persistente, bem como seus detalhes de implementação e
faremos uma análise de desempenho da estrutura proposta. Segundo [BROD94], uma
estrutura de dados parcialmente persistente é uma estrutura em que versões antigas se mantém
armazenadas e podem sempre ser consultadas. Entretanto apenas a última versão ou versão
corrente da estrutura de dados pode ser modificada. Uma interessante aplicação de uma R-
Tree parcialmente persistente é a indexação de um Sistema de Informações Geográficas
Temporal (SIGT).
Um SIG típico modela objetos geográficos como pontos individuais, linhas ou
polígonos. Segundo [LANG92], no campo de desenvolvimento de SIG existe uma crescente
necessidade de se descrever mudanças espaciais durante o tempo, isto é, projetar-se um SIG
Temporal (SIGT). Um SIGT é um SIG com funcionalidades adicionais, capaz de modelar e
tratar o armazenamento e consultas de informações temporais. Um SIG Temporal modela
objetos geográficos como pontos individuais, linhas ou polígonos que possuem um tempo de
vida específico. Nestes sistemas, cada alteração nos dados cria uma nova versão com os
dados alterados. O sistema nunca remove um objeto, apenas armazena seu tempo de morte.
Assim, a quantidade de dados sempre cresce. A necessidade de se indexar um SIGT é óbvia:
quanto maior a base de dados mais explícito se torna o ganho de desempenho por usar-se
técnicas sofisticadas de indexação. Entretanto, isto demanda novas técnicas para indexar os
dados espaciais e temporais, um campo onde pouca pesquisa foi realizada.
R-Trees [G84] e suas variantes são as estruturas mais populares para a indexação de
dados espaciais devido à sua simplicidade e eficiência. Logo, as R-Trees são candidatas
bastante apropriadas para servir como base para uma nova estrutura de índices espaço-
temporal. Neste trabalho iremos apresentar e testar a R-Tree Temporal (TR-Tree) que
mantém versões antigas dos dados utilizando-se dos mesmos métodos de acesso da R-Tree.
A TR-Tree é uma R-Tree capaz de indexar informações espaciais e temporais dentro da
mesma estrutura de índices de forma eficiente. Os algoritmos apresentados aqui foram
inspirados em uma idéia apresentada em [OHLE94] e [BGO+96]. Sendo assim, a TR-Tree é
nossa versão espacial da Multiversion B+-Tree (MVBT).
5
Nós assumimos que a TR-Tree irá armazenar o tempo de transação para seus MBRs.
No contexto de bancos de dados temporais, o tempo de transação de um fato em um banco de
dados é o intervalo de tempo em que o fato existe no banco de dados ([JCG+94]). Tempos de
transação são consistentes com a ordem de serialização das transações. Valores de tempo de
transação não podem ser maiores que o tempo de transação corrente, usualmente conhecido
como “agora”. Como consequencia, por ser impossível alterar informações no passado,
tempos de transação não podem ser alterados. Logo, estruturas de dados parcialmente
persistentes parecem ser uma boa escolha para indexar bancos de dados baseados em tempo
de transação.
A TR-Tree armazena de forma eficiente uma coleção de R-Trees, cada qual cobrindo
uma sequência disjunta de intervalos de tempo representando todo o tempo de vida do
conjunto de dados. Por construção, consultas na versão correnteda TR-Tree possuem a
mesma eficiência assintótica que as mesmas na R-Tree correspondente. Qualquer alteração
na R-Tree corrente irá transformá-la em uma nova R-Tree, e ambas estarão armazenadas na
TR-Tree. Logo, em qualquer tempo i, consultas na TR-Tree podem ser comparadas a
consultas na R-Tree correspondente ao tempo i. O único overhead neste tipo de consulta será
o tempo gasto para encontrar o nó raiz da R-Tree correspondente na TR-Tree. A boa
utilização de espaço será garantida pela utilização de um mecanismo chamado divsão de
versão (version split) que pode ser comparado à operação de cópia de blocos (block copy) em
[DSST89].
Este trabalho está organizado da seguinte forma: a seção dois apresenta uma breve
discussão sobre trabalhos relacionados ao tema aqui discutido. A seção três descreve a
estrutura da TR-Tree e suas idéias básicas. A seção quatro apresenta os algoritmos para
busca, inseção e remoção com uma descrição detalhada de cada um. A seção cinco apresenta
um exemplo simples da utilização da estrutura para facilitar o entendimento dos algoritmos.
A seção seis apresenta a análise de desempenho da TR-Tree comparada a outras abordagens.
A seção sete apresenta nossas conclusões.
6
2. Trabalhos Relacionados
Como foi dito no capítulo anterior, o nosso trabalho é uma implementação de uma
estrutura de índices capaz de tratar informações espaço-temporais. A estrutura proposta neste
trabalho foi totalmente baseada nas características de uma estrutura de índices espaciais já
consolidada na literatura, a R-Tree. Adicionamos à R-Tree algumas funcionalidades para
torná-la uma estrutura parcialmente persistente. Nesta seção iremos dar uma breve descrição
de trabalhos que influenciaram direta ou indiretamente a estrutura da TR-Tree.
2.1. R-Tree
A R-Tree foi proposta por Guttman em [G84] e foi um marco no desenvolvimento
de estruturas de índice espaciais. Esta estrutura é uma árvore balanceada similar a B-Tree
com os registros de índice nos nós folha contendo ponteiros para os objetos de dados
espaciais. Seja então M o número máximo de entradas em um nó e m ≤ M / 2 um parâmetro
identificando o número mínimo de entradas em um nó, seis propriedades são propostas como
descrito a seguir:
R1. Cada nó folha contém entre m e M registros de índice ao menos que seja um nó
raiz;
R2. Para cada registro de índice < MBR, tuple-identifier > em um nó folha, MBR é o
menor retângulo que espacialmente contém os objetos de dados n-dimensionais
representados pela tupla indicada;
R3. Cada nó interno contém entre m e M filhos ao menos que seja um nó raiz;
R4. Para cada entrada < MBR, child-pointer > em um nó interno, MBR é o menor
retângulo que espacialmente contém todos os retângulos do nó filho;
R5. O nó raiz tem pelo menos dois filhos ao menos que seja uma folha;
R6. Todas as folhas aparecem no mesmo nível da árvore.
É mostrado em [G84] que uma árvore contendo N registros de índice com essas
características acima descritas possui altura de no máximo |logmN|-1, o que mantém uma boa
eficiência assintótica de tempo e utilização de espaço.
7
Após o surgimento da R-Tree, muitas estruturas foram propostas baseadas nos
princípios propostos na R-Tree. Dentre elas podemos citar a R+-Tree [SRF87], a R*-Tree
[BKSS90] e a Hilbert R-Tree [KF94].
2.2. Métodos de Acesso Temporais
Uma variedade de métodos de acesso temporal tem sido proposta nos últimos anos.
Uma comparação detalhada entre os diversos médodos de acesso temporal pode ser
encontrada em [ST94]. A maioria das técnicas propostas assume que as mudanças ocorrem
em ordem crescente de tempo, consequentemente são apropriadas para manter a evolução do
tempo de transação. Alguns destes métodos de acesso temporal podem ser, com algum
esforço, adaptáveis ao domínio espacial.
Nosso trabalho está calcado em uma estrutura de índices temporal proposta em
[OHLE94] e [BGO+96], a Árvore B Multiversão (Multiversion B-Tree - MVBT), que torna
uma B+-Tree temporal. A estrutura proposta nesse trabalho é uma espécie de versão espacial
da MVBT. Para cada registro de índice < key, in_version, del_version, info > em um nó
folha, key é a chave única que identifica o registro em uma determinada versão, in_version é o
tempo de inserção deste registro, del_version é o tempo de remoção do mesmo e info é um
ponteiro para as informações do registros que ficam fora da estrutura. Registros internos <
router, in_version, del_version > possuem ponteiros router para seus nós filhos na árvore.
Existem, portanto, entradas em diferentes versões dentro dos mesmos nós nesta
estrutura. Quando ocorre um overflow ou underflow de um nó, uma operação de split de
versão é efetuada: todas as entradas vivas do nó são copiadas para um novo nó. O número de
entradas neste novo nó deve estar entre (1 + ε) × d e (k – ε) × d, e isto é chamado de condição
forte de versão (strong version condition), onde ε é uma constante tal que ε ≤ 1–1/d. Desta
forma garante-se que o número de acessos a disco em uma consulta é O(logd |Vi|), onde Vi
representa o número de registros de índice presentes na versão i. Isto significa que esta
estrutura, para uma dada versão i, possui as mesmas propriedades de uma B-Tree.
A R-Tree Bitemporal proposta em [KTF95], [KTF97], no contexto de bancos de
dados bitemporais, é uma implementação de uma R-Tree parcialmente persistente. A R-Tree
Bitemporal é utilizada para indexar chaves não espaciais, seus tempos de validade e de
transação. O tempo de transação é tratado aplicando-se um método parcialmente persistente a
8
uma R-Tree que indexa valores de chaves e de tempo de validade. Os intervalos de tempo de
validade são também mapeados por pontos em duas dimensões. Dadas essas suposições,
existem alguns detalhes de implementação que fazem com que não se consiga indexar dados
espaço-temporais diretamente, alguns ajustes devem ser feitos.
2.3. Estruturas de Índice Espaço-Temporais
Até o presente momento apenas 5 estruturas de acesso espaço-temporal foram
propostas na literatura: MR-Tree e RT-Trees em [XHL90], 3D R-Trees em [TVS96], HR-
Trees em [NS98], e Overlapping Linear Quadtrees (OLQT) em [TVM98]. É interessante
notar que todos os métodos citados acima podem ser enquadrados em três categorias como
feito em [TSPM98]:
1. métodos que incorporam a informação temporal nos nós da estrutura de índice.
É o caso da RT-Tree que armazena as informações temporais na tupla da estrutura de
índice, ou seja, no escopo da R-Tree, cada tupla passaria a ser representada da seguinte forma
< MBR, tuple-identifier, birth-time, deadh-time >. A informação temporal encontra-se
armazenada nos nós da árvore mas a busca leva apenas em conta a informação espacial,
tornando consultas temporais altamente ineficientes.
2. métodos que tratam o tempo como uma dimensão adicional utilizando uma
estrutura de índice espacial já conhecida, como a R-Tree ou uma de suas
variantes.
Assumir o tempo como uma nova dimensão é uma idéia bastante simples tendo-se
em vista que a estrutura de índices utilizada já se encontra implementada. A 3D R-Tree
implementada em [TVS96] considera o tempo como uma dimensão extra no espaço bi-
dimensional original e transforma regiões bi-dimensionais em MBRs tri-dimensionais. A
figura 1 retirada de [TSPM98] mostra um conjunto de objetos espaciais com seus respectivos
tempos de vida (a) e a 3D R-Tree correspondente (b). Uma busca do tipo “encontre todos os
objetos que interceptam uma determinada área D ambos em espaço e tempo” pode ser vista
também na figura e é implementada como uma simples busca tri-dimensional na R-Tree.
Esta estrutura é muito boa para o tipo de dados para o qual ela foi proposta (objetos de som e
imagem para aplicações multimedia) quando o tempo de vida dos objetos é conhecido. O
9
problema encontra-se quando não se sabe a priori o tempo final dos objetos, ou seja, objetos
são criados e permanecem na estrutura até o tempo atual. Uma discussão mais detalhadasobre o problema do tempo “agora” pode ser encontrada em [C+97].
Figura 1: MBRs tri-dimensionais armazenados na 3D R-Tree
Uma forma de resolver este problema do tempo atual é utilizar duas R-Trees
[NST98], uma para pontos em duas dimensões e outra para linhas em três dimensões (de onde
vem o nome 2+3 R-Tree). Uma idéia similar a essa foi proposta em [KTF95] e [KTF97] para
o contexto de bancos de dados bitemporais e dados não espaciais. Na primeira R-Tree ficam
armazenados os objetos que estão vivos no tempo atual, armazenando-se na tupla também o
tempo de nascimento, e a segunda funciona como uma 3D R-Tree para os objetos mortos, ou
seja, que já possuem tempo de vida determinado. Desta forma elimina-se o problema de uma
R-Tree armazenar objetos com tempo de vida indeterminado. Um problema adicional criado
por esse tipo de estrutura é o de que as buscas por tempo pontual (que não o tempo “agora” )
e por intervalo de tempo devem prosseguir pelas duas R-Trees, o que pode prejudicar o
desempenho. Ainda no contexto de estruturas de índices bitemporais, é proposta em
[BJSS98] uma estrutura que resolve o problema anterior sem a utilização de duas árvores.
10
3. métodos que utilizam estruturas de índice que se sobrepõem para representar
estados sucessivos no tempo.
Nesta terceira categoria encontram-se as MR-Trees, HR-Trees e OLQTs, ambos
trabalhos baseados no conceito de árvores sobrepostas [BKMK90]. A OLQT basea-se na
estrutura da Quadtree não se encaixando no contexto desse trabalho. A MR-Tree e HR-Tree
possuem a mesma estrutura de árvores se sobrepondo, só que a MR-Tree é baseada na R-Tree
original e a HR-Tree é baseada em uma Hilbert R-Tree. A idéia básica destes dois métodos é
a de que, dadas duas árvores onde a primeira é uma evolução da segunda, a segunda é
representada de forma incremental. Apenas os braços da árvore que foram modificados são
duplicados, sendo mantidos intactos aqueles que não sofreram modificação. A figura 2
retirada de [NS98] mostra um exemplo com duas alterações feitas em nós de uma HR-Tree:
no tempo T1, é feita uma alteração no objeto 3 gerando o objeto3a, no tempo T2, o objeto 8
dá lugar ao objeto 8a.
Figura 2: Visões física (a) e lógica (b) de uma HR-Tree
11
A grande vantagem destas estruturas é a sua simplicidade. As principais
desvantagens são a utilização inadequada de espaço e o tempo gasto para se copiar os nós
modificados em cada alteração. E ainda, para se responder a uma consulta que especifica um
intervalo de tempo, muitos nós irão ser visitados mais de uma vez sendo que muitos dos quais
irão diferir em apenas uma entrada. Portanto, estas estruturas não representam uma boa
escolha para a indexação de dados espaciais que possuem um alto índice de alterações ou
consultas por intervalo de tempo.
Uma comparação detalhada sobre os diversos métodos descritos acima pode ser
encontrada em [NST98] e em [TSPM98]. A estrutura apresentada neste trabalho poderia ser
caracterizada como uma estrutura que combina a primeira e a última categoria, de forma que
a informação de tempo encontra-se armazenada nos nós e existe, de uma forma um pouco
mais eficiente, a sobreposição de árvores sucessivas de forma incremental.
3. Estrutura de Índice da TR-Tree
Nesta seção iremos descrever com maiores detalhes a estrutura de índice proposta
em termos de modificacões na R-Tree original, como foi apresentada em [G84]. A estrutura
de índice da TR-Tree é bastante similar à da R-Tree com algumas alterações para que possa
tratar de informações temporais. Os nós folha irão armazenar entradas para registros de
índice da forma < MBR, tuple-identifier, birth-time, death-time > e nós internos contém
entradas da forma < MBR, child-pointer, birth-time, death-time >. O identificador da tupla é
um substituto à representação do polígono e será omitido nos nossos algoritmos e exemplos.
Outra importante modificação na TR-Tree é que esta estrutura pode possuir mais de
um nó raiz apontando para mais de uma R-Tree, isto é, existe mais de uma árvore dentro da
estrutura da TR-Tree. Entretanto, dado um determinado tempo, haverá um e apenas um nó
raiz associado à ele. Como consequência, a TR-Tree não deve ser vista como uma árvore,
mas como um grafo acíclico direcionado. Existe então um vetor ou uma estrutura de hash
indexando os nós raiz da TR-Tree e seus respectivos tempos de vida. Chamaremos esta
estrutura de vetor de nós raíz (root index structure).
A eficiência de tempo e espaço da R-Tree é baseada nas propriedades propostas por
Guttman [G84], especialmente a suposição R1 e R3. Para manter essa eficiência, as
12
propriedades da R-Tree devem ser generalizadas para tratar da existência de entradas em
diferentes versões em um mesmo nó da árvore. Seja M o número máximo de entradas em um
nó e m = M / k um parâmetro especificando o número mínimo de entradas vivas em um nó,
onde k é uma constante, k ≥ 2. As seis propriedades da R-Tree devem ser modificadas como
se seque:
R1. Cada nó folha contém no mínimo m registros de índice vivos e no máximo M ao
menos que seja um nó raiz;
R2. Para cada registro de índice < MBR, tuple-identifier, birth-time, death-time > em
um nó folha, MBR é o menor retângulo que espacialmente contém os objetos de
dados n-dimensionais representados pela tupla indicada;
R3. Cada nó interno contém no mínimo m entradas vivas para nós filhos e no
máximo M ao menos que seja um nó raiz;
R4. Para cada entrada < MBR, child-pointer, birth-time, death-time > em um nó
interno, MBR é o menor retângulo que espacialmente contém todos os
retângulos do nó filho no intervalo de tempo [birth-time, death-time);
R5. O nó raiz tem pelo menos dois filhos vivos ao menos que seja uma folha;
R6. Todas as folhas de um mesmo nó raiz aparecem no mesmo nível da árvore.
Note que as propriedades R1 e R3 são praticamente as mesmas (também o são R2 e
R4) diferindo apenas se estamos falando de nós folha ou nós internos. Iremos tratar, sem
perda de generalidade, destes dois tipos de nós da mesma forma, ou seja, quando tratarmos de
registros de índices em nós folha, também os chamaremos de entradas. É importante notar
que as alterações que foram feitas nas características originais da R-Tree encontram-se em
negrito para uma melhor visualização.
Nós chamamos o conjunto das propriedades R1, R3 e R5 de condicão de versão
fraca (weak version condition). Note que uma entrada viva significa que ela está viva durante
seu tempo de vida. Agora nós podemos definir as mudanças estruturais que afetam a TR-
Tree:
13
• Um overflow de nó (node overflow) ocorre como resultado de uma inserção de
uma entrada em um nó já cheio, isto é um nó que já possui M entradas.
• Um underflow de versão fraco (weak version underflow) ocorre quando o
número de entradas vivas em um nó se torna menor que m (ou dois para nós raiz).
• Um underflow de nó (node underflow) nunca ocorre, já que entradas nunca são
efetivamente removidas mas apenas marcadas como mortas.
Uma mudança estrutural para tratar um overflow de nó ou para restaurar a
propriedade a condição fraca de versão é executada baseada na operação de cópia de blocos ,
isto é, o nó é marcado como morto e todas as suas entradas vivas são copiadas para um novo
nó. Nós chamamos essa operação de divisão de versão.
Considerando um overflow de nó, na maioria dos casos o nó vivo criado pelo split de
versão deverá ser um nó praticamente cheio ou até mesmo um nó cheio. Para evitar este caso
e o fenômeno similar de um nó praticamente vazio, iremos definir duas nova propriedade R7
e R8 que devem ser satisfeitas após uma mudança estrutural, e chamaremos o conjunto destas
novas propriedades de condição de versão forte (strong version condition).
R7 O número de registros de índice vivos em um nó folha após uma mudança
estrutural deve estar entre (1 + ε) × m e (k – ε) × m, onde ε é uma constante, ε > 0,
da mesma forma como em [OHLE94];
R8 O número de entradas vivas em um nó internoapós uma mudança estrutural deve
estar entre (1 + ε) × m e (k – ε) × m.
Após uma divisão de versão de um nó, se o mesmo viola a condição forte de versão,
ocorre então uma mudança estrutural do tipo da R-Tree: overflow gera um split de nó e
underflow gera uma remoção física do nó seguida da reinserção de todas as suas entradas.
Este é o único caso onde uma remoção física pode ocorrer. É importante notar que este tipo
de remoção de nó é resultado de uma única operação de inserção ou alteração, de forma que
os nós removidos pertencem a estados intermediários da TR-Tree que não precisam ser
manter armazenados.
Como m = M / k, nós garantimos que após uma mudança estrutural em um nó pelo
14
menos ε×m+1 inserções ou remoções de entradas ainda podem ser executadas naquele nó
antes que a próxima mudança estrutural se torne necessária. A escolha de ε pode ser feita da
mesma forma como em [OHLE94], mas sem restrições ao merge da B+-Tree. Logo, k≥
1/α+(1+1/α)×ε−1/m, onde α é o coeficiente de mínima utilização para a R-Tree original (no
máximo 0.5). Em nossos testes, utilizamos α = 0.5, k = 3 e ε = 0.3. Assim, para a capacidade
de um nó de 90 entradas, os parâmetros da TR-Tree ficam como mostrado na tabela 1.
Condição fraca de versão Max. entradas/nó 90
Min. entradas vivas/nó 30
Condição forte de versão Max. entradas/nó 81
Min. entradas vivas/nó 39
Tabela 1 – Parâmetros da TR-Tree
Desta forma, após um split de versão pode-se efetuar pelo menos mais 9 alterações
naquele nó antes que ocorra um overflow ou underflow fraco de versão. Isto garante que a
maioria das alterações na TR-Tree não irá disparar novas mudanças estruturais, o que é
indesejado.
Com essas modificações na R-Tree, a TR-Tree torna-se uma estrutura de índice
capaz de manipular informações temporais e ainda manter as boas eficiências de tempo e
espaço da R-Tree original. Nós assumimos que o nó raiz associado à um tempo t pode ser
encontrado em O( 1 ) acessos. A busca então procede como se fosse em uma R-Tree original.
Como, devido à condição fraca de versão, cada nó da TR-Tree armazena pelo menos m
entradas na versão t, uma árvore apontada por um nó raiz associado à um tempo t funciona
como uma R-Tree com m como número mínimo de entradas.
4. Algoritmos de Busca, Remoção e Inserção
Nesta seção iremos apresentar os algoritmos da TR-Tree para busca em tempo
pontual, inserção e remoção. Essas operações são correspondentes na TR-Tree às operações
básicas da R-Tree. Além dessas, a TR-Tree tem uma operação própria chamada de time-
range query.
15
4.1. Busca em instante de tempo
No contexto das R-Trees a operação de busca é normalmente chamada de consulta
por janela, e retorna todos os MBRs que interceptam um determinado retângulo R. A
operação correspondente na TR-Tree consulta todos os MBRs que interceptam R em um dado
tempo t, ou seja, todos os MBRs que interceptam R e estão vivos no tempo t.
O algoritmo de busca em instante de tempo recebe como argumentos um retângulo R
e um tempo de busca t. É basicamente o mesmo algoritmo de busca da R-Tree original, mas
com um passo inicial que busca o nó raiz apropriado, isto é, o nó raiz cujo intervalo de tempo
de vida contém o tempo t. Como o vetor de nós raiz é uma estrutura de memória ordenada
por birth-time e não existem intervalos com interseção, uma busca binária pode aqui ser
realizada. Uma vez encontrado o nó raiz a busca prosegue da mesma forma que na R-Tree
original, apenas ignorando as entradas em que o intervalo de tempo de vida não contém t.
Algorithm Search
Description: Given an TR-Tree, find all index records whose MBRs overlap a search
 rectangle S and their lifespan includes the search time t.
Begin
 Find the root node R of the tree corresponding to time t in the root index structure
 Invoke RootSearch at root node R, passing the search rectangle S and the search time t
End
Algorithm RootSearch
Description: Given a root node R, find all index records whose MBRs overlap a search
 rectangle S and their lifespan includes the search time t.
Begin
 if R is a leaf node then
 Check all entries E to determine whether E.birth-time ≤ t ≤ E.death-time and
 E.MBR overlaps S. If so, E is a qualifying record
 else
 Check all entries E to determine whether E.birth-time ≤ t ≤ E.death-time and
 E.MBR overlaps S. For all overlapping entries, invoke RootSearch
 recursivelly on the node pointed by E.child-pointer
End
4.2. Inserção
A inserção na TR-Tree recebe como argumentos um MBR e um identificador da
tupla. Inserções podem ser feitas apenas nos nós folha da R-Tree corrente da TR-Tree. Após
uma inserção, o tempo corrente da TR-Tree pode ser incrementado ou não.
Inicialmente, uma busca é executada para encontrar o nó folha ótimo onde a entrada
para o MBR dado será inserida. Esta busca é feita apenas no último nó raiz da TR-Tree, e
deve considerar apenas entradas e nós vivos. A entrada é inserida no nó eleito anteriormente
e isto dispara todas as mudanças estruturais necessárias caso ocorra a violação das condições
16
fraca ou forte de versão, desde o nó folha até o nó raiz da árvore. Os estágios intermediários
gerados pela operação de inserção não precisam ser armazenados e sim apenas a versão final
da estrutura. Como na R-Tree original, uma lista de entradas é utilizada para armazenar
entradas temporariamente removidas da estrutura que devem ser reinseridas.
Algorithm Insert
Description: Insert a new index record E in a TR-Tree.
Begin
 Let R be the current root node of the TR-Tree
 Invoke ChooseNode to select a leaf node L in which to place E
 If L is the current root node of the TR-Tree R then
 Invoke InsertRootNode to insert the entry E into the root node R
 Else
 Invoke InsertNode to insert the entry E into the leaf node L
 If the ReinsertList is not empty then
 Invoke ReinsertEntries to reinsert the entries removed from the structure at
 their given levels
End
Algorithm ChooseNode
Description: Search for a node L at height h in a tree with root node R in which to place
 a new entry E. This algorithm is similar as Guttman’s ChooseLeaf. If the
 height is not given, the algorithm searches for leaf nodes.
Begin
 Let N be the root node R
 If h is not given then
 Let h be the height of the TR-Tree with root node R
 while the height of the node N is not equal to h do
 Let F be the live entry in N whose rectangle F.MBR needs least enlargement to
 include E.MBR. Resolve ties by choosing the entry with the rectangle of
 smallest area.
 Let N to be the child node pointed to by F.child-pointer
 Return N
End
Algorithm InsertNode
Description: Insert the entry E and possibly another entry EE in a node A of the TR-Tree.
 It also receives another argument forceVersionSplit that forces version splits.
Begin
 If forcedVersionSplit = F and there is space for one(two) more entry(ies) in node A then
 Enter E(EE) into A
 Invoke UpdateMBR on A to adjust the upwards bounding boxes
 Else
 Invoke VersionSplit on A creating node B with only current version entries
 Let P be the live parent entry of A and Q the entry in P for A
 Kill the entry Q in P. This also may lead to a weak version underflow
 condition in P that will be handled in next steps
 Enter E(EE) into B. { This may momentarily lead to a block overflow in B, such an
 overflow is eliminated immediately }
 If strong version overflow condition occurs at node B then
 Invoke SplitNode of Guttman’s R-Tree with one of the three algorithms, the
 exhaustive algorithm, the quadratic-cost algorithm and the linear-cost
 algorithm. This algorithm returns two nodes B and BB
 Let E and EE be the entries referring to B andBB to be inserted in the
 parent node P of B and BB
 If P is the current root node of the TR-Tree then
 Invoke InsertRootNode to insert the entries E and EE into the node P
 Else
 Invoke InsertNode to insert the entries E and EE into the node P
 Else if strong version underflow condition occurs at node B then
 Insert all live entries of B in the ReinsertList to be reinserted later
 While P is not the rooot node and a weak version underflow occurs in P do
 Insert all live entries of P in the ReinsertList to be reinserted later
 Let Q be the entry for P in his parent and P be this parent node
 Kill the entry Q in P.
 Else
 Invoke UpdateMBR on B to adjust the upwards bounding boxes
End
17
Algorithm VersionSplit
Description: Copy current version entries of a node A into a new created node B
Begin
 Create a new node B
 For each entry E in A do
 If E is alive then
 Copy E into B
 Return B
End
Algorithm UpdateMBR
Description: Ascend from a node L to the root, adjusting covering MBRs.
Begin
 If L is not a root node then
 Let P be the live parent node of L and E the entry of P pointing to L
 Kill the entry E
 Invoke InsertNode to insert the entry E with E.MBR covering all MBRs of L.
 { the algorithm InsertNode will handle this recursively until the root }
 If the root node is not a leaf and has less than two children then
 Make this child the new root node creating a new entry for it in the root index
 structure and killing the old one
End
Algorithm ReinsertEntries
Description: Reinsert entries on the set ReinsertList at their given levels
Begin
 While ReinsertList is not empty do
 Remove the first element of the ReinsertList where E is the entry and H its level
 Invoke ChooseNode passing E and H receiving node L where to place E
 If L is the current root node of the TR-Tree then
 Invoke InsertRootNode to insert the entry E into the root node L
 Else
 Invoke InsertNode to insert the entries E into the node L
 If the root is not leaf and has only one live child then
 Let R be this child node which will be the new root node
 Insert the new root node R in the root index structure killing the old one
End
Algorithm InsertRootNode
Description: Insert the entry E in a root node R of the TR-Tree.
Begin
 If there is space for one more entry in the root node R then
 Enter E into R
 Else
 Invoke VersionSplit on R into a new node R’
 From this point we will call R this new root node R’
 Enter E into R { This may momentarily lead to a node overflow in R, such an
 overflow is eliminated immediately }
 If a strong version overflow occurs in R then
 Invoke SplitNode of Guttman’s R-Tree creating the nodes RR and RRR
 Clean the root node R
 Let E and EE be the entries referring to RR and RRR to be inserted in the new
 root node R
 Invoke InsertRootNode to insert the entries E and EE into the root node R
 // Here it will not occur any structural changes in R and therefore we can
 // simply enter E and EE into R.
 Else if the root is not leaf and has only one live child then
 Make this child the new root node R
 Insert the new root node R in the root index structure killing the old one
End
O argumento forcedVersionSplit do algoritmo InsertEntry funciona para o caso de
reinserção de entradas pelo algoritmo ReinsertEntries. Essas reinserções devem vir sempre
com um split de versão do nó para que a busca não obtenha resultados duplicados. Devemos
lembrar que a reinserção também gera estados intermediários.
18
4.3. Remoção
A remoção na TR-Tree recebe como argumentos um MBR e um identificador de
tupla para ser removido. Inicialmente uma busca é feita para encontrar o nó que contém uma
entrada para estes MBR e identificador de tupla. Se este nó não for encontrado, a remoção é
abortada. Como o algoritmo de inserção, esta busca é feita apenas no último nó raiz da TR-
Tree pois alterações são sempre feitas na versão atual da estrutura. Uma vez encontrado o nó
folha contendo a entrada a ser removida, o atributo death-time da entrada é alterado para o
tempo corrente da TR-Tree e os MBRs acima devem ser ajustados, bem como a condição
fraca de versão deve ser mantida. Novamente, estados intermediários da TR-Tree não serão
armazenados.
Algorithm Delete
Description: Remove index entry E from the TR-Tree.
Begin
 Let R be the current root node of the TR-Tree
 Invoke FindLeaf to locate the leaf node L containing E
 Kill the entry E in L
 If weak version underflow occurs in L then
 Invoke VersionSplit on L resulting in a node LL
 Insert all entries in LL into the ReinsertList
 Let P be the live parent entry of L and Q the entry in P for L
 Kill the entry Q in P
 While P is not the root node and a weak version underflow occurs in P do
 Insert all live entries of P in the ReinsertList to be reinserted later
 Let Q be the entry for P in his parent and P be this parent node
 Kill the entry Q in P
 Invoke ReinsertEntries to reinsert the entries removed from the structure at
 their given levels
End
Algorithm FindLeaf
Description: Given a root node R, Find the leaf node containing the index entry E.
Begin
 If R is not a leaf then
 Check each live entry F in R to determine if F.MBR contains E.MBR. For each such
 entry invoke FindLeaf on the tree whose root is pointed by F.child-pointer
 until E is found or all entries have been checked
 Else
 Check each live entry to see if it matches E. if E is found return R
End
4.4. Consulta por intervalo de tempo
A consulta por janela pode ser temporalmente estendida para permitir a obtenção de
todos os MBRs que interceptam um retângulo dentro de um intervalo de tempo [t1, t2). Esta
consulta é chamada de consulta por intervalo de tempo, e segundo [LANG92], esta é uma das
consultas mais importantes que um SIGT deve responder. Devido aos splits de versão que
duplicam entradas, esta consulta necessita de uma estratégia especial para que não haja
acessos a disco desnecessários e/ou repetições de resultados. Desta forma, iremos reformular
19
nossa consulta: encontrar todos os MBRs que interceptam o retângulo R e foram mortos no
intervalo de tempo [t1, t2) ou estão vivos no tempo t2. Embora esta consulta produza o
mesmo resultado, não irá encontrar entradas duplicadas já que:
1) entradas mortas não são copiadas após um split de versão, logo, não são duplicadas;
2) no tempo t2 existe apenas uma entrada viva para cada MBR.
Desta forma, nosso algoritmo, para a consulta por intervalo de tempo não irá
produzir entradas duplicadas nem irá visitar o mesmo nó duas vezes.
Algorithm TimeIntervalSearch
Description: Given an TR-Tree, find all index records whose MBRs overlap a search
 rectangle S and their lifespan includes the search time interval [t1,t2).
Begin
 For all root nodes in the root index structure except the last one do
 Invoke RootSearchKilledEntries passing the root node R, the search rectangle S and the
 time interval [t1,t2)
 Invoke RootSearchKilledOrLiveEntries passing the root node R, the search rectangle S and
 the time interval [t1,t2)
End
Algorithm RootSearchKilledEntries
Description: Given a root node R, find all index records whose MBRs overlap a search
 rectangle S and was killed between the time interval [t1, t2).
Begin
 If R is a leaf node then
 Check all entries E to determine whether E is killed, E.MBR overlaps S and
 E.death-time ∈ [t1, t2). If so, E isa qualifying record
 Else
 Check all entries E to determine whether E.MBR overlaps S and E.death-time ∈ [t1, t2).
 For all entries checked, invoke RootSearchKilledEntries recursivelly on the node
 pointed by E.child-pointer
End
O procidimento “RootSearchLiveOrKilledEntries” não está descrito
acima por ser similar ao “RootSearchKilledEntries” com diferença principal na
condição IF permitindo a saída de entradas vivas.
4.5. Operações em bloco
Nós podemos modificar os algoritmos da TR-Tree e permitir um bloco de operações
ser feito antes que uma nova versão seja criada. As mudanças necessárias são bastante
simples como pudemos verificar, e os ganhos são ainda maiores quando o número de
operações torna-se maior. A principal mudança na implementação é a de não armazenar
nenhum nó ou entrada que possui intervalo de tempo de vida igual a [a,a) já que este intervalo
corresponde a um intervalo nulo. Atualmente, nós já implementamos estas mudanças quando
executamos o procedimento de reinserção.
20
Desta forma, podemos fazer com que a TR-Tree funcione como uma R-Tree
original, apenas não incrementando os tempos após qualquer operação de alteração. Só existe
portanto um nó raiz e portanto uma árvore que corresponde a uma R-Tree original.
5. Exemplo
Iremos ilustrar as idéias dos algoritmos utilizando um exemplo. Neste exemplo
iremos inserir em ordem alfabética todos os retângulos da tabela 2 representados
graficamente pela figura 3 e depois remover alguns deles. Os parâmetros da TR-Tree
utilizados para este exemplo foram: M = 6, m = 2 ( k = 3 ) e ε = 0.5. Desta forma, a condição
fraca de versão garante que cada nó na TR-Tree contém no mínimo duas entradas vivas e no
máximo seis entradas a menos que seja o nó raiz. A condição forte de versão, por sua vez,
garante que após uma mudança estrutural, novos nós contêm no mínimo três e no máximo
cinco entradas vivas. Consideraremos o tempo, neste exemplo, como uma sequência de
números inteiros, onde inicialmente a TR-Tree possui tempo atual 1 e, a cada operação de
inserção ou remoção, o tempo vai sendo incrementado.
Retângulo x1 Y1 x2 y2
A 15 37 54 250
B 219 6 320 37
C 306 30 344 143
D 204 106 352 137
E 37 244 187 288
F 258 181 297 206
G 187 219 320 237
H 195 30 234 112
I 226 175 305 213
J 132 250 171 281
K 38 119 219 150
Tabela 2 – Retângulos que serão inseridos na TR-Tree
21
Figura 3 – Retângulos que serão inseridos na TR-Tree
Inicialmente, a TR-Tree está vazia. A inserção do retângulo A cria o primeiro nó (
folha ) raiz R1 que será inserido no vetor de nós raiz. As inserções dos retângulos B, C, D, E
e F enchem o nó raiz R1. Esta situação é mostrada na figura 4 abaixo:
Figura 4 – Situação no tempo 6
A inserção do retângulo G então gera um overflow de nó em R1 no tempo 7. Um
split de versão é executado neste nó com todas as entradas vivas (o que neste caso
corresponde a todas as entradas) sendo copiadas para um novo nó raiz (também folha) R2. O
antigo nó raiz da árvore atual R1 é marcado como morto no tempo 7. Um overflow de
condição forte ocorre no nó R2 e suas entradas são divididas em dois novos nós folha N1 e N2
através de um split de nó. O nó R2 torna-se então um nó raiz (agora nó interno) possuindo
dois filhos N1 e N2. Dois retângulos I1 e I2 contendo todos os retângulos de N1 e N2
respectivamente são criados em R2. Este caso é um exemplo de como a altura da árvore da
versão atual cresce. A situação após a mudança estrutural é mostrada nas figuras 5 e 6
abaixo:
HA
B
C
D
E
F
G
I
J
K
R1
A, [1,*)
B, [2,*)
C, [3,*)
D, [4,*)
E, [5,*)
F, [6,*)
R1, [1,*)
22
Figura 5 – Situação no tempo 7
Figura 6 – Retângulos no tempo 7
O retângulo H é inserido no nó N1 tornando-o cheio. A inserção do retângulo I
dispara um novo split de versão seguido de um split de nó devido à um overflow de condição
forte gerada após a mudança estrutural do split de versão. São criados então, no tempo 10, os
nós internos N3 e N4 e o nó N2 é marcado como morto neste mesmo tempo em seu nó pai
vivo R2. A situação da estrutura neste ponto é mostrada na figura 7.
R2
N1, I1, [7,*)
N2, I2, [7,*)
N1
A, [1,*)
E, [5,*)
N2
B, [2,*)
C, [3,*)
D, [4,*)
F, [6,*)
G, [7,*)
R1
A, [1,*)
B, [2,*)
C, [3,*)
D, [4,*)
E, [5,*)
F, [6,*)
F [6 *)
R1, [1,7) R2, [7,*)
A
B
C
D
E
F
G
I1
I2
23
Figura 7 – Situação no tempo 9
O retângulo J é inserido no nó N1. Na inserção do nó K acontece um outro tipo de
caso interessante, que é o de aumento de MBR. O retângulo K seria inserido no nó N1, mas K
não está estritamente contido em I1, logo haverá um aumento do MBR I1 gerando o MBR I1’.
Inicialmente os algoritmos tratavam o aumento de MBR marcando a entrada antiga como
morta e criando uma nova entrada para o novo MBR. Por motivos de desempenho,
resolvemos permitir o aumento de MBRs apenas alterando diretamente o valor do MBR.
Este aumento pode ser visto na figura 8 e a nova estrutura na figura 9.
Figura 8 – Aumento de MBR após inserção do retângulo K
R2
N1, I1, [7,*)
N2, I2, [7,9)
N3, I3, [9,*)
N4, I4, [9,*)
R1
A, [1,*)
B, [2,*)
C, [3,*)
D, [4,*)
E, [5,*)
F, [6,*)
R1, [1,7) R2, [7,*)
N1
A, [1,*)
E, [5,*)
N2
B, [2,*)
C, [3,*)
D, [4,*)
F, [6,*)
G, [7,*)
H, [8,*)
N3
F, [6,*)
G, [7,*)
I, [9,*)
N4
B, [2,*)
C, [3,*)
D, [4,*)
H, [8,*)
A
E
J
K
I1 I1’
24
Figura 9 – Situação no tempo 11
Após todas essas inserções iremos remover dois retângulos, o I e o F. A remoção do
retângulo I é simplesmente feita marcando-se a entrada para ele como morta no tempo 12. A
remoção do retângulo F gera um underflow de condição fraca no nó N3, pois agora só resta a
entrada G como viva, pois I já foi marcada como morta. Isto é resolvido marcando-se a
entrada para N3 em seu pai vivo R2 como morta neste tempo e reinserindo o retângulo G na
estrutura. O retângulo G será inserido no nó N4 o qual sofrerá um split de versão forcada
como foi explicado no algoritmo de inserção. Neste caso pode-se notar a importância do split
de versão forcada para o caso de reinserção pois se o nó N4 não fosse duplicado, uma
consulta por um retângulo que intercepte o retângulo G no tempo 10, por exemplo, retornaria
o nó G pelo nó N3 e pelo nó N4, o que com o split de versão forçado não acontece. A
estrutura final encontra-se da forma como mostrada na figura 10 abaixo.
R2
N1, I1’ , [7,*)
N2, I2, [7,9)
N3, I3, [9,*)
N4, I4, [9,*)
R1
A, [1,*)
B, [2,*)
C, [3,*)
D, [4,*)
E, [5,*)
F, [6,*)
R1, [1,7) R2, [7,*)
N1
A, [1,*)
E, [5,*)
J, [10.*)
K, [11,*]
N2
B, [2,*)
C, [3,*)
D, [4,*)
F, [6,*)
G, [7,*)
H, [8,*)
N3
F, [6,*)
G, [7,*)
I, [9,*)
N4
B, [2,*)
C, [3,*)
D, [4,*)
H, [8,*)
25
Figura 10 – Situação no tempo 13 (final)
Da forma com que foi criada a árvore, uma busca pelo retângulo R mostrado na
figura 11 procederia da seguinte forma: o nó raiz onde se inicia a busca é o nó raiz da árvore
corrente: R2. Os únicos nós vivos em R2 são N1 e N5 e apenas I5 intercepta o retângulo R. A
busca procede seguindo então pelo nó N5 e, como N5 é um nó folha, a busca retorna os nós
vivos em N5 que possuem interseção com o retângulo de busca R, que no caso corresponde
somente ao retângulo G.
Uma busca por intervalo de tempo utilizando o mesmo retângulo R e o intervalo de
tempo [1,14) deveria retornar todos os retângulos que algum dia existiram na TR-Tree e que
interceptam o retângulo de busca R. O algoritmo desce inicialmente em R1 procurando
entradas mortas dentro do intervalo de busca. Como R1 é folha e todas as suas entradas estão
vivas, o algoritmo não retorna nenhuma entrada neste passo e em seguida pega o próximo nó
raiz R2. Como este é o último nó raiz da TR-Tree, nesta parte da busca, a procura não é feita
apenas pelos nós mortos mas também nos nós que ainda estão vivos no tempo 14. O
algoritmo então vai descer pelos nós N1, N2, N3, N4 e N5, onde em N2, N3 e N4 ele vai
procurar apenas entradas mortas já que estes nós encontram-se mortos. Em N1, não existem
retângulos que interceptamR e em N2 e N4 não existem entradas mortas. Em N3, o
algoritmo vai retornar os retângulos F e I pois interceptam R e encontram-se mortos e em N5
o único retângulo que intercepta R é G.
R2
N1, I1’ , [7,*)
N2, I2, [7,9)
N3, I3, [9,13)
N4, I4, [9,13)
N5, I5, [13,*)
R1
A, [1,*)
B, [2,*)
C, [3,*)
D, [4,*)
E, [5,*)
F, [6,*)
R1, [1,7) R2, [7,*)
N1
A, [1,*)
E, [5,*)
J, [10.*)
K, [11,*]
N2
B, [2,*)
C, [3,*)
D, [4,*)
F, [6,*)
G, [7,*)
H, [8,*)
N3
F, [6,13)
G, [7,*)
I, [9,12)
N4
B, [2,*)
C, [3,*)
D, [4,*)
H, [8,*)
N5
B, [2,*)
C, [3,*)
D, [4,*)
G, [13,*)
H, [8,*)
26
A resposta a esse exemplo seria então F, I e G, o que seria de se esperar pelo
desenho da figura 11 abaixo. Repare que o algoritmo não percorreu nenhum nó mais de uma
vez e nem retornou resultados duplicados.
Figura 11 – Retângulo de busca R
Este exemplo então mostrou a funcionalidade dos algoritmos implementados para a
TR-Tree com seus principais problemas descritos de forma gráfica para um melhor
entendimento dos mesmos.
6. Resultados Experimentais
6.1. Dados de Teste
Nosso conjunto de dados é o mesmo que foi utilizado em [BKS93], e consiste de
128,971 MBRs for objetos lineares em uma área da California representando rios e linhas
ferroviárias. Nós inserimos de forma artificial algumas remoções de MBRs no conjunto de
dados para testar como a estrutura se comporta mediante inserções e remoções. Para executar
os testes, tentamos simular o ambiente de uma aplicação hipotética onde existe um número de
objetos vivos que se mantém relativamente constante por alterações balanceadas. As
alterações foram agrupadas em pequenos conjuntos de remoções e inserções. A tabela 3
resume o que foi dito. Os dados foram normalizados para estarem contidos no retângulo (0,0)
e (10,000,10,000). Todos os testes foram executados em uma máquina Pentium II 350MHz.
HA
B
C
D
E
F
G
I
J
K
R
27
Conjunto 1 Conjunto 2 Conjunto 3 Conjunto 4 Conjunto 5
Número de MBRs inseridos 128.971 128.971 128.971 128.971 128.971
Número de MBRs removidos 51.588 51.584 51.568 51.588 51.388
Número Total de Operações 180.559 180.555 180.539 180.559 180.359
Número final de MBRs 77.383 77.387 77.403 77.383 77.583
Tempo Atual 5 19 83 323 805
Granularidade média 3.611 3.392 2.175 559 224
Tabela 3 – Conjuntos de dados para os resultados experimentais
Neste conjunto de dados, efetuamos inicialmente 25,795 inserções, cerca de 20% do
total de objetos. Após isto, foi efetuado um número balanceado de inserções e remoções da
seguinte forma: um grupo de entradas era removido e outro grupo de entradas era inserido de
forma intercalada. Isto pode ser visto na figura 12 abaixo. Para mostrar a escalabilidade da
TR-Tree, efetuamos testes variando a granularidade do tempo, ou seja, o número médio de
operações de inserção ou remoção executadas antes da criação explícita de uma nova versão
de uma R-Tree dentro da TR-Tree, ou seja, incrementa-se o tempo corrente da TR-Tree,
como mostrado na seção 4.4. Uma glanuraridade de tempo de 1 significa que cada operação
cria uma nova versão de uma R-Tree dentro da TR-Tree, uma glanuraridade de tempo de 100
significa que terá uma média de umas 100 operações de inserção ou remoção antes da criação
de uma nova R-Tree (a cada tempo este valor é aleatoriamente escolhido por um gerador de
números aleatórios com média 100).
Figura 12 – Organização do conjunto de dados 2
Compararemos os nossos resultados obtidos com uma HR-Tree pois, segundo
[NST98], é a estrutura que apresenta os melhores resultados atualmente.
Inserções iniciais (20%)
Grupo de remoções com cardinalidade
dependendo do conjunto de dados
Grupo de inserções: idem. Cada grupo de
remoções é seguido por um grupo de
inserções
28
6.2. Testes
Iniciamos nossos testes comparando o tamanho, em bytes, das estruturas formadas
bem como o tempo levado para a criação dos índices. Não estaremos aqui medindo o tempo
de criação dos índices por acessos a disco porque alguns índices ficaram muito grandes e o
número de acessos a disco para a criação dos mesmos tornou-se incontável.
Conjunto 1 Conjunto 2 Conjunto 3
TR-Tree HR-Tree TR-Tree HR-Tree TR-Tree HR-Tree
Tempo 15’09” 15’08” 13’19” 14’36” 12’22” 16’12”
Tamanho
(Mbytes)
12.659 11.562 16.200 29.126 20.086 119.060
Conjunto 4 Conjunto 5
TR-Tree HR-Tree TR-Tree HR-Tree
Tempo 12’50” 17’55” 12’31” 19’30”
Tamanho
(Mbytes)
21.572 290.278 19.022 387.526
Tabela 4: Resultados comparativos de criação dos índices para as estruturas.
Os resultados da criação dos índices encontram-se na tabela 4 abaixo. Podemos
observar nessa tabela que o tempo de criação dos índices é bem menor para a TR-Tree do que
para a HR-Tree na medida que a granularidade de tempo diminui. O fato mais importante a
ressaltar nesta tabela porém, é a diferença entre tamanho das estruturas formadas. Enquanto o
tamanho da HR-Tree cresce bastante com o decréscimo da granularidade dos tempos, a TR-
Tree parece se manter bastante estável. As boas propriedades assintóticas quanto ao espaço
de utilização podem ser melhor vistas na figura 13. Esta figura mostra que a TR-Tree
permanece robusta com o aumento do número de versões existentes na estrutura de índices.
Outra característica marcante desta figura é o fato de que a TR-Tree ainda encolheu
ligeiramente de tamanho do conjunto de dados 4 para o conjunto de dados 5. Isto pode ser
explicado por diferenças na utilização média nos nós e por diferenças na estrutura da árvore
gerada pelo algoritmo que escolhe o nó onde será realizada uma inserção. Quando um nó
sofre divisão, o seu MBR é alterado afetando o algoritmo.
29
Figura 13: Utilização de espaço das estruturas.
O próximo teste efetuado foi a de uma busca em instante de tempo. O retângulo de
busca utilizado foi (2000,2000),(8000,8000) e o tempo, para todos os conjuntos de dados, foi
o tempo atual de cada estrutura. Os resultados encontram-se na tabela 5 e no gráfico da
figura 14. Na tabela, podemos inicialmente verificar que a quantidade de MBRs encontrados
é a mesma para as duas estruturas, ou seja, nenhuma das estruturas possui duplicação de
resultados para consultas por instante de tempo.
Conjunto 1 Conjunto 2 Conjunto 3
TR-Tree HR-Tree TR-Tree HR-Tree TR-Tree HR-Tree
PáginasLidas 1.210 1.321 1.091 1.141 1.073 1.067
MBRs
encontrados
43.509 43.509 44.027 44.027 44.325 44.325
Conjunto 4 Conjunto 5
TR-Tree HR-Tree TR-Tree HR-Tree
PáginasLidas 1.074 1.049 1.073 1.061
MBRs
encontrados
44.172 44.172 44.377 44.377
Tabela 5: Busca por instante de tempo no tempo atual e MBR de busca
(2000,2000),(8000,8000).
12,65911,562 16,200
29,126
20,086
119,060
21,572
290,278
19,022
387526
0
50,000
100,000
150,000
200,000
250,000
300,000
350,000
400,000
T
a
m
a
n
h
o
 
e
m
 
K
B
y
t
e
s
Conjunto de Dados 1 Conjunto de Dados 2 Conjunto de Dados 3 Conjunto de Dados 4 Conjunto de Dados 5
TR-Tree
HR-Tree
30
Figura 14: Gráfico de consulta por instante de tempo no tempo atual e MBR
(2000,2000),(8000,8000)
Este gráfico na figura 14 mostra a boa eficiência da TR-Tree na busca por instante
de tempo tendo em vista que os resultados se assemelham bastante aos obtidos pela HR-Tree.
A HR-Tree possui os melhores resultados atualmente para o caso da busca por instante de
tempo, pois uma vez encontrado o nó raiz correspondente ao tempo de busca, e isso é feito
em O(1) com uma estrutura de hash, por exemplo, a busca na HR-Tree torna-se uma busca
em uma R-Tree que é ótima para o problema de busca espacial.
A última e principal análise de performance é a de uma busca por intervalo de
tempo. A estrutura da TR-Tree é muito boa para este tipo de consulta e, até onde se sabe, é a
única estrutura capaz de efetuar este tipo de consulta de forma eficiente. Para demonstrar este
fato, efetuamos uma busca com o intervalo de tempo equivalente ao tempo total da estrutura,
ou seja, [1,*) e para o MBR de busca (0,0),(10000,10000). Esta busca deveria retornar todos
os objetos da estrutura de índice. Note natabela 6 que a HR-Tree não consegue lidar com
esse tipo de consulta nem mesmo para altas granularidades de tempo, apenas no conjunto de
dados 1 a HR-Tree retornou resultdados satisfatórios. Esta estrutura (HR-Tree) retorna
muitos objetos repetidos e algum método de eliminação de duplicatas deveria ser efetuado
1210
1321
1091
1141
1073 1067 1074 1049
1073 1061
0
200
400
600
800
1000
1200
1400
A
ce
ss
o
s 
a 
d
is
co
 (
le
it
u
ra
)
Conjunto de Dados 1 Conjunto de Dados 2 Conjunto de Dados 3 Conjunto de Dados 4 Conjunto de Dados 5
TR-Tree
HR-Tree
31
para que não ocorra tal situação. Os acessos a disco nas consultas estão mostrados na figura
15 abaixo.
Figura 15: Gráfico das consultas por intervalo de tempo com MBR
(0,0),(10000,10000)
Conjunto 1 Conjunto 2 Conjunto 3
TR-Tree HR-Tree TR-Tree HR-Tree TR-Tree HR-Tree
PáginasLidas 4.477 4.148 5.731 13.776 7.107 59.610
MBRs
encontrados
128.971 270.839 128.971 954.410 128.971 4.333.885
Conjunto 4 Conjunto 5
TR-Tree HR-Tree TR-Tree HR-Tree
PáginasLidas 7.633 227.852 6.730 568.566
MBRs
encontrados
12.8971 16.703.565 128.971 41.636.611
Tabela 6: Busca por instante de tempo no tempo atual e MBR de busca (0,0),(10.000,10.000).
4477 4148 5731
13776 7107
59610
7633
227852
6730
568566
0
100000
200000
300000
400000
500000
600000
A
ce
ss
o
s 
a 
d
is
co
 (
le
it
u
ra
)
Conjunto de Dados 1 Conjunto de Dados 2 Conjunto de Dados 3 Conjunto de Dados 4 Conjunto de Dados 5
TR-Tree
HR-Tree
32
7. Conclusões
Neste trabalho, nós implementamos e testamos o desempenho de uma nova estrutura
de índices chamada Temporal R-Tree (TR-Tree) que lida com dados espaço-temporais:
pontos, linhas, regiões e tempo de transação. A TR-Tree permite a recuperação de estados
presentes e passados dos dados. A duplicação dos dados é baixa, o que é garantido pelos
mecanismos de split de versão e cópia de blocos. Uma boa utilização de espaço é garantida
pelo alto número de nós praticamente cheios. Apenas um pequeno overhead é requerido para
as operações de inserção e remoção quando comparadas às operações básicas da R-Tree
original. A performance da consulta por janela é semelhante à da R-Tree original, sendo
ainda possível a consulta em estados passados da estrutura, bem como eficientemente
responder a consulta por intervalo de tempo, uma operação típica de bancos de dados espaço-
temporais. A TR-Tree é atualmente a única estrutura de índices espaço-temporal capaz de
responder à este tipo de consulta de forma eficiente.
Nossos testes de performance mostraram que a TR-Tree é uma estrutura bastante
robusta no que diz respeito a altos índices de alterações nos dados, o que é um problema das
estruturas atualmente conhecidas. Para os conjuntos de dados em que as estruturas existentes
são eficientes a TR-Tree se mostrou também bastante eficiente, ou seja, esta estrutura não
surge para responder a um tipo de aplicação específica, mas sim como uma nova estrutura
mais robusta e ainda eficiente do que as estruturas de índice espaço-temporais existentes.
Trabalhos futuros são necessários em diversas direções, tais como: mais testes com
conjuntos de dados temporais reais e simulados; implementação dos algoritmos da R*-Tree e
outras variantes; definir-se uma versão paralela da TR-Tree; comparar resultados à outras
técnicas citadas neste trabalho que não foram utilizadas para a avaliação de performance e
investigar a execução de joins espaço-temporais usando a TR-Tree.
33
8. Bibliografia
[BGO+96] B. Becker, S. Gschwind, T. Ohler, B. Seeger, and P. Widmayer: “An
Asymptotically Optimal Multiversion B-tree”, The VLDB Journal, vol.5(4), pp.
264-275, December 1996.
[BJSS98] R. Bliujute, C. S. Jensen, S. Saltenis, G. Slivinskas: “R-Tree Based Indexing of
Now-Relative Bitemporal Data”. Proceedings of 24rd International Conference on
Very Large Data Bases, New York City, New York, USA, August 24-27, 1998.
[BKMK90]F. Burton, John G. Kollias, D. G. Matsakis, V. G. Kollias:. “Implementation of
overlapping B-trees for time and space efficient representation of collection of
similar files”. The Computer Journal 33, 3, 279 - 280, 1990.
[BKS93] T. Brinkhoff, H. P. Kriegel, and B. Seeger: “Efficient processing of Spatial Joins
Using R-Trees”. In Proceedings of the 1993 ACM-SIGMOD Conference,
Washington, DC, USA,May 1993.
[BKSS90] N. Beckmann, H.-P. Kriegel, R. Schneider, B. Seeger, “The R*-tree: An Efficient
and Robust Access Method for Points and Rectangles”, Proceedings of ACM
SIGMOD Conference, 1990.
[BROD94] G. S. Brodal: “Partially Persistent Data Structures of Bounded Degree with
Constant Update Time”. In Nordic Journal of Computing, volume 3(3), pages
238-255, 1996.
[C+97] J. Clifford et al., “On the semantics of “NOW” in temporal databases”, ACM
Transcaction on Database Systems, 22(2):171-214, June 1997.
[DSST89] J. R. Driscoll, N. Sarnak, D.D. Sleator, and R.E. Tarjan: “Making data structures
persistent”. Journal of Comp. and System Science. 38:86-124, 1989.
[G84] A. Guttman: “R-Trees: A Dynamic Index Structure for Spatial Searching”. In
Proceedings of the ACM SIGMOD Intl. Conf on Management of Data, Boston,
MA, 1984.
[JCG+94] Jensen, C., Clifford, J., Gadia, S., Segev, A., and Snodgrass, R. “A consensus
glossary of temporal database concepts”. ACM SIGMOD Record 23, 1 (Jan
1994), 52--64.
[KF94] I. Kamel and C. Faloutsos, “Hilbert R-Tree: An improved R-Tree using fractals”,
In Proceedings of the 20th Very Large Databases Conference, pages 500-509,
September 1994.
[KTF95] A. Kumar, V. J. Tsotras, and C. Faloutsos: “Access Methods for Bitemporal
Databases”. In Recent Advances in Temporal Databases, J. Clifford, and A.
Tuzhilin (eds), pp. 235--254, Springer Verlag, 1995.
[KTF97] A. Kumar, V. J. Tsotras, and C. Faloutsos: “Designing Access Methods for
Bitemporal Databases”. TR3764, Dept. of Comp. Sci. University of Maryland,
1997.
[LANG92] Langran, G.: “Time in Geographical Information Systems”. Taylor & Francis,
London, 1992.
[NS98] M. A. Nascimento, J. R. O. Silva, “Towards Historical R-trees”, Proceedings of
ACM Symposium on Applied Computing (ACM-SAC), 1998.
34
[NST98] M. A. Nascimento, J. R. O. Silva and Y. Theodoridis: “Access Structures for
Moving Points”. Time Center Technical Report TR-33, September/98.
[OHLE94] Thomas Bernhard George Ohler, “On the integration of Non-Geometric Aspects
into Access Structures for GIS”, PhD dissertation submitted to the Swiss Federal
Institute of Technology, 1994.
[ST94] Salzberg, B., and Tsotras, V.: “A comparison of access methods for time evolving
data”. Tech. Rep. NU-CCS-94-21, College of Computer Science, Northeastern
University, Boston, USA, 1994. (To appear in ACM Computing Surveys).
[SRF87] T. Sellis, N. Roussopoulos, C. Faloutsos, “The R+-Tree: A Dynamic Index for
Multi-Dimensional Objects”, Preceedings of the 13th International Conference on
Very Large Data Bases (VLDB), 1987.
[TSPM98] Yannis Theodoridis, Timos Sellis, Apostolos N. Papadopoulos, and Yannis
Manolopoulos: “Specifications for Efficient Indexing in Spatiotemporal
Databases”, Proceedings of SSDBM’98, Capri, Italy, July 1-3 1998.
[TVM98] T. Tzouramanis, M. Vassilakopoulos, Y. Manolopoulos: “Overlapping Linear
Quadtrees: A Spatio-Temporal Access Method”. Proceedings of the 6th
international symposium on Advances in Geographic Information Systems,
Washington DC, USA, November 6-7, 1998.
[TVS96] Y. Theodoridis, M. Vazirgiannis, and T. Sellis: “Spatio-Temporal Indexing for
Large Multimedia Applications” Proceedings of the 3rd IEEE Conference on
Multimedia Computing and Systems (ICMCS), 1996.
[XHL90] X. Xu, J. Han, W. Lu: “RT-tree: An Improved R-tree Index Structure for
Spatiotemporal Databases”, Proceedings of the 4th International Symposium on
Spatial Data Handling (SDH), 1990.