7/21/2019 Apresentao r Star-trees

1/18

TABD 2011/2012

*

The R*tree: AnEfficientandRobustAccess

MethodforPoints and Rectangles

SusanaJoo 070316067

rvoresR*Joo

Graa

080316115

7/21/2019 Apresentao r Star-trees

2/18

TABD 2011/2012

SPATIAL DATABASES

BD otimizada para armazenar e consultar dadosque esto relacionados com objetos no espao,incluindo ontos linhas e ol onos.

Enquanto as BD tpicas podem compreender, ,

nas BD espaciais so precisas funcionalidadesa c ona s para processar pos e a osespaciais.

rvoresR*

7/21/2019 Apresentao r Star-trees

3/18

TABD 2011/2012

Funcionalidades Spatial DB

Distance(geometry,geometry) :

number

Equals(geometry,geometry) :boolean

Intersects eometr eometr : boolean

,

rvoresR*

7/21/2019 Apresentao r Star-trees

4/18

TABD 2011/2012

ALGUNS TIPOS DE SPATIAL DB

Zorder Mapeia

pontos

multidimensionais

numas imens o. Quadtree Todososnstmexatamente4

filhos. OctreeTodos os ns tm exatamente 8 filhos. UBtree MisturadeB+trees ezorder trees.

Rtree

rvoresR*

tree

7/21/2019 Apresentao r Star-trees

5/18

TABD 2011/2012

RVORES R

Sovores

de

estruturas

de

dados

que

so

usa asparaM to os eAcessoEspacia ,ouseja,paraindexarinformaomultidimensional

(comocoordenadas

geogrficas,

retngulos

e

ol onos Ex.deuso:Encontrartodososmuseusqueesto

rvoresR*

7/21/2019 Apresentao r Star-trees

6/18

TABD 2011/2012

RVORES R

Cadachave

corresponde

auma

caixa,

ou

coleo

einterva os,comuminterva opor imens o; Divideoespaohierarquicamente,sobrepondo

retngulosde

limite

mnimos

minimum boundin rectan le

rvoresR*

7/21/2019 Apresentao r Star-trees

7/18

TABD 2011/2012

RVORESRrvoreR

rvoresR*

7/21/2019 Apresentao r Star-trees

8/18

TABD 2011/2012

RVORES R

Dificuldades: :

sejaequilibrada(osnsfolhafiquemna

mesmaaltura);

osretngulosnocobrammuitoespaovazioenosesobreponhammuito(para

deserprocessadas);

rvoresR*

7/21/2019 Apresentao r Star-trees

9/18

TABD 2011/2012

RVORES R*

Variante

da

rvore

R

usada

para

indexar

; Suportaeficiententementepontosedados

espaciaisao

mesmo

tempo

Oseucustodeimplementaoapenasligeiramente maiordoqueadeoutras

rvoresR*

7/21/2019 Apresentao r Star-trees

10/18

TABD 2011/2012

*

RVORESR*

rvoresR*

7/21/2019 Apresentao r Star-trees

11/18

TABD 2011/2012

Diferenas entre R* e R

Principaldiferena:

R*

usa

inseres

foradas

emvezdesplitting;A minimiza o da cobertura e da sobre osi o

crucial

para

odesempenho

das

R

trees.

* .

rvoresR*

7/21/2019 Apresentao r Star-trees

12/18

TABD 2011/2012

Diferenas entre R* e R

R*reduz

sobreposies

(

procurado

oretngulomaisfavorvelinsero)

uando um retn ulo fica cheio uma or o

dasentradas

so

removidas

desse

retngulo

e

,bounding boxes

rvoresR*

7/21/2019 Apresentao r Star-trees

13/18

TABD 2011/2012

rvoreR*rvore

R

rvoresR*

7/21/2019 Apresentao r Star-trees

14/18

TABD 2011/2012

CRITRIOS DE OTIMIZAO

1.Areacobertaporretngulo

.

diretrios

deve

ser

minimizada

rvoresR*

7/21/2019 Apresentao r Star-trees

15/18

TABD 2011/2012

ONDE SE OTIMIZA R R*

Naescolhadasubrvore

Nadiviso

de

retngulos

Na

insero

e

Reinsero

de

ns

rvoresR*

7/21/2019 Apresentao r Star-trees

16/18

TABD 2011/2012

Exemplo

Nsobrelotado Diviso

R Diviso

R*

rvoresR*

7/21/2019 Apresentao r Star-trees

17/18

TABD 2011/2012

CONCLUSES

Reinseresdiminuem

sobreposies

Utilizaodeespaomelhorado

Aforma

dos

retngulos

mais

quadrtica

inseroAsqueriessomuitomaisr pi as

rvoresR*

7/21/2019 Apresentao r Star-trees

18/18

TABD 2011/2012

B I AD PELAB I AD PELAATEN O!ATEN O!

rvoresR*