Transcript PPT slide
Data Structure and access method Fan Zhang Zhiqi Chen Unordered file Linear search Ordered file Binary search 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 codes Run-length encoding (RLE) Block encoding dimensions. Point Object Structure Grid structure Point quadtree 2D-tree Linear Objects PM quadtrees 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. R-Trees A important access method in Spatial Data Management. 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. R*-Trees An efficiently access method for points and rectangles. A popular access method in database systems organizing both multidimensional point data and spatial data. More suitable for the more complex object representation. 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 question？