1USCC. ShahabiCSCI585CSCI585Spatial Index StructuresCyrus ShahabiComputer Science DepartmentUniversity of Southern [email protected]. ShahabiCSCI585CSCI585OutlineIntroductionSpatial IndexingR-TreeR+-TreeQuad Trees2USC3C. ShahabiCSCI585CSCI585IntroductionSpatial objects– Points, lines, rectangles, regions, …Hierarchical data structures– Based on recursive decomposition, similar to divide and conquer method, like B-tree.Why not B-Tree?– More than one dimension– Concept of closeness relies on all the dimensions of the spatial dataSpatial index structures demo– http://www.cs.umd.edu/~brabec/quadtree/index.htmlUSC4C. ShahabiCSCI585CSCI585Spatial IndexingMapping spatial object into point– In either same, lower, or higher dimensional spaces– Good for storage purposes– Problems with queries like finding the nearest objectsBucketing methods– Based on spatial occupancy– Decomposing the space from which the data is drawn• Minimum bounding rectangle (MBR) : e.g., R-Tree• Disjoint cells: e.g., R+-Tree• Blocks of uniform size• Distribution of the data: e.g., quadtreedata-dependentgreater degree of data-independence3USC5C. ShahabiCSCI585CSCI585R-Tree[proposed in 1984 by Guttman]Based on Minimum Bounding Rectangle (m,M)=(1,3)R4d g hR3R1a babdghR2R5 R6c i e fciefbounding rectangles could overlap each others (e.g., R3 vs R4)an object is only associated with one bounding rectangleUSC6C. ShahabiCSCI585CSCI585R-Tree[proposed in 1984 by Guttman]Height-balanced tree similar to B-tree for k-dimensionsEvery leaf node contains between m (m ≤M/2) and M index records, unless it is the rootFor each index record (I, tuple-identifier) in a leaf node, I is the MBR that contains the n-dimensional data object represented by the indicated tupleEvery non-leaf node has between m and M children unless it is the rootFor each entry (I, child-pointer) in a non-leaf node, I is the MBR that spatially contains the rectangles in the child node.All leaves appear on the same levelThe root node has at least two children unless it is a leaf4USC7C. ShahabiCSCI585CSCI585Insertion ProcessesdefigmABhkljCXA new index entryXChooseLeafHas roomInstall XYesSplitNodeNoCAdjustTreeCAdjust all related entriesDifferent variant:•Exhaustive•Quadratic•Linear•Packed•Hilbert Packed•…etc.USC8C. ShahabiCSCI585CSCI585Processes of Quadratic Spilt(page 52 in Guttman’s paper)Pick first entry for each groupRun PickSeedsdefigmABhkljCXd e fg h i j k l mCBA5USC9C. ShahabiCSCI585CSCI585Processes of Quadratic Spilt(page 52 in Guttman’s paper)defigmABhkljCXd e fg h i j k l mCBAPickSeedsPS1 [Calculate inefficiency of grouping entries together]For each pair of E1 and E2, compose a rectangle R including E1 and E2Calculate d = area(R) - area(E1) - area(E2)PS2 [Choose the most wasteful pair ] Choose the pair with the largest dljkllXmlUSC10C. ShahabiCSCI585CSCI585Processes of Quadratic Spilt(page 52 in Guttman’s paper)Pick first entry for each group(PickSeeds)d e fg h i j k l mCBACheck if doneG1G2l mSelect entry to assign(PickNext)NoigmdefABhkljG1XG26USC11C. ShahabiCSCI585CSCI585Processes of Quadratic Spilt(page 52 in Guttman’s paper)Pick first entry for each group(PickSeeds)igmdefABhkljG1XCheck if doneG1G2l mPickNextPN1 [Determine cost of putting each entry in each group] For each entry Ecalculate d1 = the increased MBR area required for G1 calculate d2 = the increased MBR area required for G2 PN2 [Find entry with greatest preference for one group]Choose the entry with the maximum difference between d1 and d2NoG2G1G2kG2G1mXG2G1jUSC12C. ShahabiCSCI585CSCI585Processes of Quadratic Spilt(page 52 in Guttman’s paper)Pick first entry for each group(PickSeeds)d e fg h i j k l mCBACheck if doneG1G2l mSelect entry to assign(PickNext)NoG1 G2l mkigmdefABhkljG1XG27USC13C. ShahabiCSCI585CSCI585G2G2G1G1Processes of Quadratic Spilt(page 52 in Guttman’s paper)Pick first entry for each group(PickSeeds)Check if doneG1G2l mSelect entry to assign(PickNext)NoG1 G2l mkigmdefABhkljG1XG2jXUSC14C. ShahabiCSCI585CSCI585Processes of Quadratic Spilt(page 52 in Guttman’s paper)Pick first entry for each group(PickSeeds)Check if doneG1G2l mSelect entry to assign(PickNext)NoigmdefABhkljG1XG2G1 G2l mkX8USC15C. ShahabiCSCI585CSCI585Processes of Quadratic Spilt(page 52 in Guttman’s paper)Pick first entry for each group(PickSeeds)Check if doneG1G2l mSelect entry to assign(PickNext)NoigmdefABhkljG1XG2G1 G2l mkXjd e fg h i l kG2G1BAm x jUSC16C. ShahabiCSCI585CSCI585Your Exercise Before Midterm(m,M)=(2,4)Build a R-Tree for these spatial dataHint: You could use the Spatial index structures demo application step by stepDFGEHJKL9USC17C. ShahabiCSCI585CSCI585Search Object in R-TreeigmdefABhkljG1xG2d e fg h i l kG2G1BAm x jInput (T, j)Leaf?YesSearch each subtree E of TNoOverlap(E,j)YesCheck each entry E of TOverlapQualifyingrecordYesUSC18C. ShahabiCSCI585CSCI585Main Drawbacks of R-TreeR-tree is not unique, rectangles depend on how objects are inserted and deleted from the tree.In order to search some object you might have to go through several rectangles or the whole database–Why?– Solution?10USC19C. ShahabiCSCI585CSCI585R+-TreeOvercome problems with R-TreeIf node overlaps with several rectangles insert the node in allDecompose the space into disjoint cellsR2R3 R4 R5 R6R1a bd g h c i e fh i c igdhcifebUSC20C. ShahabiCSCI585CSCI585R+-Tree PropertiesR+-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 polyhedronR+-trees is extension of k-d-B-treeRetrieval times are smallerWhen summing the objects, needs eliminate duplicatesAgain, it is data-dependent11USC21C. ShahabiCSCI585CSCI585Quad TreesRegion Quadtree– The blocks are required to be disjoint– Have standard sizes (squares whose sides are power of two)– At standard locations– Based on successive subdivision of image array into four equal-size quadrants– If the region does not cover the entire array, subdivide into quadrants, sub-quadrants, etc.– A variable resolution data structureUSC22C. ShahabiCSCI585CSCI585Example of Region Quadtree123456789101112131415 16171819AB C E213 4 5 6 11 12D13 14 19F15 16 17 187 8 9 10NWNESWSE33111112USC23C. ShahabiCSCI585CSCI585PR QuadtreePR (Point-Region) quadtreeRegular decomposition (similar to Region quadtree)Independent of the order in which data points are inserted