PPT slide

Data Structure
and access
Fan Zhang
Zhiqi Chen
Unordered file
 Linear
Ordered file
 Binary
One to Two Dimensions
 Six
title index:
row order
row-prime order
Cantor-diagonal order
spiral order
Morton order
Peano-Hilbert order.
Raster Structure
 chain
 Run-length encoding (RLE)
 Block encoding dimensions.
Point Object Structure
 Grid
 Point quadtree
 2D-tree
Linear Objects
 PM
PM1 quadtree
PM2 quadtree
PM3 quadtree
Collection of Objects
 Rectangles
& Minnimum bounding boxes
 R-trees & R+-trees
 BSP-tree
Spherical Data Structures
 Provide
methods to surface of the Earth
 Quaternary triangular mesh (QTM)
Voronio Diagram
 Decomposes
a set of objects in a spatial
 Variants: the k-th order, the Farthest-Site
 Method to create a Voronoi Diagram
 Been used in: science, astronomy,
biology, nearest neighbor problem, and
route planning.
A important access method in Spatial Data
A ubiquitous data structure
The splitting criteria: Linear Split, Quadratic Split,
Exponential Split.
Various: R+-tree, R*-Tree, Static R-tree, Packed R-tree,
Hilbert Packed R-tree, STR R-tree, Time-Evolving R-tree
Used for: processing spatial queries, spatio-temporal
database, multimedia database, data warehousing
and data mining. Based on the research, it covers
almost every aspect of concerning a database.
Will be important in modern system and application.
An efficiently access method for points and
A popular access method in database systems
organizing both multidimensional point data and
spatial data.
More suitable for the more complex object
Supports point and spatial data at the same time
and its implementation cost is a little higher than of
other R-tree variants.
R*-tree has been used in geographic information
system (GIS), digital mock-up (DMU), and
multidimensional feature vectors.
Mobile Object Indexing
 Been
used in location-aware applications
traffic monitoring,
intelligent navigation
mobile communications management
Thank you!
 Any

similar documents