PowerPoint PresentationSpatial Data StructuresIntroductionSpatial IndexingR-treeR-Trees (Continued)R-trees (Continued)R+ - TreesR+ Trees (Continued)R+Trees(Continued)More Spatial IndexingRegion DataMore Region DataRegion QuadtreeRegion Quadtree (Continued)Variations of QuadtreeSlide 17More Variations of QuadtreeSearching with QuadtreeAlgorithms with QuadtreePoint DataPR-tree (Continued)Rectangle DataRectangle Data (Continued)Slide 25Slide 26MX-CIF QuadtreeLine DataPM1 Quadtree(Continued)Line Data (Continued)PMR QuadtreeSlide 32Slide 33ConclusionSnehal Thakkar 1Snehal ThakkarSpatial Data StructuresHanan SametComputer Science DepartmentUniversity of MarylandSnehal Thakkar 2Spatial Data Structures•Introduction•Spatial Indexing•Region Data•Point Data•Rectangle Data•Line Data•ConclusionSnehal Thakkar 3Introduction•Spatial Objects Points, Lines, Regions, Rectangles …..•Spatial Indexing Unlike conventional data sort has to be on space occupied by data•Hierarchical Data StructuresBased on recursive decomposition, similar to divide and conquer methodSnehal Thakkar 4Spatial Indexing•Mapping Spatial Data into Point- Same, Higher or Lower Dimension- Good storage purposes, queries like intersect- Problems with queries like nearest•Bucketing Methods- Grid file, BANG file, LSD trees, Buddy trees….- Buckets based on not the representative point, but based on actual space.Snehal Thakkar 5R-tree•Based on Minimum Bounding Rectangle R2R3 R4 R5 R6R1a b d g h c i e fSnehal Thakkar 6R-Trees (Continued)•Organize spatial objects into d-dimensional rectangles.•Each node in the tree corresponds to smallest d-dimensional rectangle that encloses child nodes.•If an object is spatially contained in several nodes, it is only stored in one node.•Tree parameters are adjusted so that small number of pages are visited during a spatial query•All leaf nodes appear at same level•Each leaf node is (R,O) where R is smallest rectangle containing O, e.g. R3,R4……Snehal Thakkar 7R-trees (Continued)•Each non-leaf node is (R,P) where R is smallest rectangle containing all child rectangles, e.g. R1,R2•R-tree of order (m,M) means that each node in the tree has between floor M/2 and M nodes, with exception of root node. Root node has two entries unless it is a leaf node.•R-tree is not unique, rectangles depend on how objects are inserted and deleted from the tree.•Problem is that to find some object you might have to go through several rectangles or whole database.Snehal Thakkar 8R+ - Trees•Decomposition of Space into Disjoint CellsR2R3 R4 R5 R6R1a bd g h c i e fh i c iSnehal Thakkar 9R+ Trees (Continued)•R+-tree and Cell Trees used approach of discomposing space into cells•R+-trees deals with collection of objects bounded by rectangles•Cell tree deals with collection of objects bounded by convex polyhedra•R+-trees is extension of k-d-B-tree. •Try not to overlap the rectangles.•If object is in multiple rectangles, it will appear multiple times.Snehal Thakkar 10R+Trees(Continued)•Multiple paths to object from the root•Height of the tree is increased•Retrieval times are smaller•When summing the objects, needs eliminate duplicates•It is not possible to guarantee that all properties of B-trees is fulfilled without going through difficult insert and deletion routines.•It is data-dependent, so depending on how you insert or delete records R+-tree will be different.Snehal Thakkar 11More Spatial Indexing•Uniform Grid- Ideal for uniformly distributed data- More data-independence then R+-trees- Space decomposed on blocks on uniform size- Higher overhead•Quadtree- Space is decomposed based on data points- Sensitive to positioning of the object- Width of the blocks is restricted to power of two- Good for Set-theory type operations, like composition of data.Snehal Thakkar 12Region Data•Focus on Interior Representation•Represented as Image array of pixels•Runlength Code- Break array into 1*m blocks, row representation•Metal Axis Transformation (MAT)- Union of Maximal Square blocks- Blocks may overlap- Block are specified by center and radiusSnehal Thakkar 13More Region Data•Region Quadtree- Is Metal Axis Transformation- Whose blocks are required to be disjoint- To have standard sizes(squares whose sides are power of two)- To be at standard locations- Based on successive subdivision of image array into four equal size quadrants.Snehal Thakkar 14Region Quadtree12 34 513 141911 1261518171671098AB C F213 4 5 6 11 12D13 14 19E15 16 17 187 8 9 10NWNESWSESnehal Thakkar 15Region Quadtree (Continued)•Each leaf node is either Black or White•All non-leaf nodes are Gray(Circle is previous example•You can also use it for non-binary images•Resolution of the decomposition may be governed by data or predetermined•Can be used for several object representations.Snehal Thakkar 16Variations of Quadtree•Point Quadtree- Quadtree with rectangular quadrants- Adoption of Binary Search Tree to two dimensions or more- Useful for location based queries like where is nearest theatre from the location.- Descending the tree till you find the node for location based queries.- For nearest neighbor, search is continued in the neighborhood of the node containing object.- Feature based queries tough because index is based on spatial occupancy not on features.Snehal Thakkar 17Variations of Quadtree•Pyramid- Exponentially tapering stack of arrays, each one quarter size of previous- Useful for feature based queries like where does wheat grow in California.- Nodes that are not at maximum level of resolution contain summary information•Octree- Three dimensional analog of quadtree- Recursively subdivide into eight octantsSnehal Thakkar 18More Variations of Quadtree•Locational Code Based Quadtree- Treats image as a collection of leaf nodes, each encoded by pair of numbers- First is base 4 number, sequence of directional codes that locates leaf from the root- Second depth at which node is found or size•DF-expression- Represents the image in form of traversal of nodes of its quadtree- Very Compact storage, each node type can be encoded with two bits.- Not easy to use when random access to nodes is required.Snehal Thakkar 19Searching with Quadtree•Useful for performing set operations•When performing intersection, it only returns black node when both quadtrees have black nodes. •Operation is performed using three
View Full Document
Unlocking...