Recurse if overlap( MOBR(child), query point/MOBR)
Traverse multiple paths! (DFS)
Q? Will the algo. work for all OGIS operators?
Copyright: S. Shekhar, C. S. Dept.,
University of Minnesota, Minneapolis, MN 55455. ,,.(home)S9: R-trees - Spatial Query Processing
OGIS Predicates - inside, touch, overlap, ...
Overlap is a nice filter for many topological predicates
Eact predicate checked in refine step
General strategy for other OGIS predicates
child J eliminates child I iff
... some condition C is satisfied
Recurse on childs which can not be eliminated
Nearest Neighbor Search for point QP
C = min-dist(MOBR(I), QP) > max-dist(MOBR(J), QP)
min-dist(rectangle R, QP) = distance(QP, closest point in R)
min-dist(rectangle R, QP) = distance(QP, farthest point in R)
... consider corner point and sides of rectangle R
Q? Will general strategy work for all OGIS predicates?
Copyright: S. Shekhar, C. S. Dept.,
University of Minnesota, Minneapolis, MN 55455. ,,.(home)S10: Update Processing with R-tree
Insertion: Where: ChooseLeaf. Least enlargement.
Ties broken by picking smallest key.
Node splitting as in B+-tree.
Q? what goes in each partition?
AdjustTree required. Why not in B+-tree?
Deletion: Seek and destroy
CondenseTree: throw entries from under-full pages
... back into tree while preserving level.
Why different from B+-tree?
Update: delete, update, reinsert
Split algorithms: exhaustive
quadratic: start with most distant seeds,
... greedily add based on maximal preference
linear: like quadratic, but picks seeds differently
Copyright: S. Shekhar, C. S. Dept.,
University of Minnesota, Minneapolis, MN 55455. ,,.(home)S11: R-tree Variants
R*-tree - several optimizations
Faster split algorithm (n * logn)
Reduces sibling overlap, Smaller MOBR for parents
Improves page utilization, reduces splits
Out-performs R-tree on point/range search.
But Concurrency problems (reinsertion of extreme entries).
R+-Tree
no sibling overlap
But replicate items across leafs
Faster search but slow insert/delete/update
R-trees partition data. R+-trees partition space.
... like K-D-B trees, Quad trees
Copyright: S. Shekhar, C. S. Dept.,
University of Minnesota, Minneapolis, MN 55455. ,,.(home)S12: Grid Files
Spatial queries (e.g. point/ range queries in N dim. )
Data Structure: Grid directory
N dimension vectors: cross-product is non-uniform grid
Grid directory : cell to data page
... many cells may share a data page
Grid directory can be quite large!
Point Search
Binary search of each dimension to identify a cell
Fetch grid-cell and then the data-page pointed to
2 I/Os for poit query (very fast)
Insert of a point key
Binary search of each dimension to identify a cell
If the page pointed has no page then split
... insert a whole new row or column
... induces more sharing of pages across cells
Copyright: S. Shekhar, C. S. Dept.,
University of Minnesota, Minneapolis, MN 55455. ,,.(home)S13: Grid Files
Q? How does Grid Files deal with extended objects?
? Replicate across cells (pages)
? Decompose large objects into sub-objects
Range Search
Binary search of each dimension - > a set of cells
Duplicate elimination on pages pointed to
Fetch unique data-page pointed to
#I/Os proportional to result size (very fast)
Nearest Neighbor Search
Extend R-tree algorithms on the unique pages in grid
Q? Will the algo. work for all OGIS operators?
Copyright: S. Shekhar, C. S. Dept.,
University of Minnesota, Minneapolis, MN 55455. ,,.(home)S14: 4.3 Related Topics
Topics
Concurrency Control
Join Index
TR* tree for object decomposition
Copyright: S. Shekhar, C. S. Dept.,
University of Minnesota, Minneapolis, MN 55455. ,,.(home)
The views and opinions expressed in this page are strictly those of the page author. The contents of this page have not been reviewed or approved by the University of Minnesota.