Bdesp

Introducción

Índices Espaciales

Las búsquedas espaciales requieren índices para mejorar su eficiencia.




Existen dos tipos básicos de consultas – – Point Query: encontrar todoslos objetos que contienen un punto dado Region Query: encontrar todos los objetos que se superponen a una región dada

1

Introducción


Introducción


Consultas

Historia de losmétodos de acceso multidimensionales

1966

1995

Introducción


Índices espaciales


Para representar los polígonos, normalmente se utilizan Centroides o Rectángulos Mínimos(MBB: Minimun Bounding Box o MBR: Minimun Bounding Rectangle)

K-D-Tree




 

 

Árbol binario de búsqueda para un espacio de K dimensiones Divisiones a través de hiperplanosisoorientados Orientado a “Point Query” En cada nivel se divide el hiperplano por una dimensiòn distinta, y en forma alternada Los nodos interiores poseen uno o dos hijos Se puede balancearÍndices espaciales



Índices espaciales
BSP-Tree (Binary Space Partition)
Árbol binario de búsqueda para un espacio de D dimensiones Las divisiones no son iso-orientadas En cada nivel sedivide el hiperplano por una dimensiòn distinta, y en forma alternada Se subdivide hasta un tamaño de bucket No son balanceados

 

 

Índices espaciales



Índices espacialesQuadtree
Existen varios tipos: Point Quadtree, Region Quadtree, y otros. En el plano (2 dimensiones), divide el espacio en cuadrantes (NW, NE, SW, SE) Los cuadrantes tienen una capacidadmáxima. Cuando se alcanza dicha capacidad, se subdivide Las divisiones son independientes de los datos.







Índices espaciales


Índices espaciales
R-Tree






Árbolbalanceado de rectángulos donde cada raíz de subárbol contiene espacialmente a todos sus hijos Se define un parámetro M que indica la cantidad máxima de hijos por nodo (similar al B-Tree) Sea...