Transcript Midterm PPT

From GPS and Google Earth to Spatial Computing
CSCI 5980
Team 3: Fan Zhang, Zhiqi Chen
Oct 24, 2012
Structures and Access Methods
Chapter 6
Encyclopedia Articles
•Voronoi Diagram, J. Kang, page 1232-1235.
• R-tree, M. Hadjieleftheiou, et al, page 993-1002.
• R*-tree, H. Kriegel, P. Kunath, page 987-992.
• Mobile Object Indexing, G. Kollios, V. Tsotras, page 663670.
Relevance to Course
• Voronoi Diagram: The method decomposes a set of
objects in a spatial space to a set of polygonal partitions.
• R-tree: It is a hierarchical data structure based on B+-tree,
used for dynamic organization of a set of d-dimensional
geometric objects.
• R*-tree: An improvement of the R-tree. Popular access
method for points and rectangles.
• Mobile Object Indexing: Supplement content in the
textbook.
Related Material in Textbook
6.6 Collections of objects
 Rectangles and minimum bounding boxes(MBB)
– MBB, the smallest bounding rectangle with sides parallel to the axes of
the Cartesian frame.
 R tree
– A way of indexing rectangles.
– Each node represents a rectangle.
– The leaf nodes represent the actual rectangles to be indexed.
 R +-tree
– No overlapping rectangles associated with non-leaf nodes.
– Improve the efficiency of point and range queries.
Novelty in Encyclopedia Articles
• Characteristics of R-tree
• Algorithms cover Range search, insertion, delete, and
condense.
• R-tree Variants
• R +-tree
• R*-tree
• Other variants
Societal Motivation
• Voronoi diagram
‒ Sciences, Astronomy, Biology, Forestry, Geology, Medicine, Spatial Data,
Geography. Graph Theory, Nearest Neighbor Problem, Route Planning
• R-Trees
‒ Spatial data management, p2p system, data streams, bio-informatics,
all aspects concerning a database system
• R*-Tree
‒ Geographic Information Systems(GIS), Digital Mock-up(DMU),
Multidimensional Feature Vectors
• Mobile object indexing
‒ Traffic monitoring, intelligent navigation, mobile communications
management
Computer Science Motivation
• R*-Tree
•
•
•
•
•
Improvement of R-tree
Popular access methods for points and rectangles
Modifying the insert and split algorithms of R-tree
Supports point and spatial data at the same time
Implementation cost is slightly higher than that of other R-tree variants
• Mobile Object Indexing
• An object’s movement can be presented through a linear function of
time with their initial location, a starting tune instant and a velocity
vector.
R-Tree
Characteristics of R-Tree
• The root node of the tree
contains at least two entries.
• Every internal node contains a set
of rectangles and pointers to the
corresponding child node.
• Every leaf node contains the
rectangles of spatial objects.
• Nodes are guaranteed half full.
• The R-tree is a height-balanced
structure.
R-Tree
The R-tree range search algorithm
RangeSearch(TypeNode RN, TypeRegion Q)
/* Finds all rectangles that are stored in an R-tree with root
node RN, which intersect with a query rectangle Q.
Answers are stored in set A. */
if RN is not a leaf node
examine each entry e of RN to find e.mbb that intersect Q;
foreach such entry e call RangeSearch(e.p, Q);
else // RN is a leaf node
examine each entry e to find e.mbb that intersects Q;
add these entries to answer set A;
endif