Transcript Document

Spatial Information Systems (SIS)
COMP 30110
Spatial access methods:
Indexing (part 2)
Quadtree-based indexes
•
Adaptation of original quadtree structure defined for
images
•
Represented by a quaternary tree
•
Different types of quadtree-based indexes:
•
For 2D polygonal data: based on MBRs
•
For straight-line data and 1D map data (PMquadtrees and PMR-quadtrees)
•
For point data
Quadtree-based indexes (cont.d)
•
Space-based hierarchical structures
•
Based on a recursive subdivision of the space into 4
quadrants
•
The subdivision can be into either equal sized or
unequal sized quadtrants
Quadtrees for polygonal data
•
Used to index the MBRs of objects and not the actual
geometries (like R-trees)
•
The space is recursively subdivided until the number of
rectangles overlapping each quadrant is less than the disk
page capacity
•
Each leaf is associated with a disk page that stores the
entries
•
A rectangle appears in all leaf quadrants that it overlaps
(difference wrt R-trees)
Example
B C
A
D
E
F
J
G
[D,E,J] [G,H,I,L]
[H,J,K]
H
I
L
K
[A,B,F] [B,C,F] [F,G] [F]
Pointers to object geometries
Quadree with disk page capacity of 4 entries
Example: point query
B C
A
D
E
F
P
G
[H,J,K]
H
I
L
[D,E,J] [G,H,I,L]
J
K
[A,B,F] [B,C,F] [F,G] [F]
• Follow a single path from root to leaf
• At each level choose among the four quadrants the one containing the point
• Once the MBR containing P is found, check for inclusion in actual geometry
Linear data: PM-quadtrees
Vertex-based structures that recursively decompose the space
such that at most one vertex lies in a quadtree leaf node
Such a decomposition results in splitting lines into segments
called q-edges
A node in a PM-quadtree contains the following information:
- Pointers to the 4 subquadrants of the node (NW, NE, SW, SE)
- List of q-edges crossing the region of space corresponding to the node
- Pointers to the lines that each q-edge is part of
PM-quadtrees (cont.d)
Several different variation of PM-quadtrees
Examples:
1. PM1-quadtree imposes the following restrictions:
- If a leaf node contains a vertex, all segments contained in
the node must be incident on that vertex
- If a leaf node does not contain a vertex, it cannot contain
more than one segment
2. PM2-quadtree relaxes the second condition
3. PM3-quadtree: no restriction
Examples: PM1-quadtree
Examples: PM2-quadtree
A leaf node that does not contain a vertex can contain more than one edge
Examples: PM3-quadtree
Leaf nodes containing one vertex can contain edges that are not incident
at that vertex
Point data
Two main indexing methods:
-
Fixed Grid (and Grid file)
-
Quadtree
Space is subdivided into equal sized or unequal sized
cells each corresponding to a disk page
Example: fixed grid
disk page capacity = 3 entries
Grid file
Improvement of the grid structure
Cells of different size to avoid too many empty cells
Depends on the order in which the points are inserted
Example: quadtree
disk page capacity = 3 entries
Point quadtree
The final structure depends on the order in which the
points are inserted
Point quadtree (cont.d)
Same dataset but points inserted in a different order
Summary
Space-driven
vs.
Data-driven indexing
Based on partitioning of the
embedding 2D space into
rectangular cells, independently
of the object distribution.
Objects are mapped to cells
according to some pre-defined
criterion.
Based on subdivision of the set of
objects and not the embedding
space. The subdivision adapts to
the object distribution in the
space.
Example: Quadtrees
Example: R-trees
Next week
Sample of the exam paper
Research issues in GIS
Question time