CSCI585 Spatial Index Structures Cyrus Shahabi Computer Science Department University of Southern California shahabi usc edu C Shahabi Outline CSCI585 Introduction Spatial Indexing R Tree R Tree Quad Trees 2 C Shahabi 1 Introduction CSCI585 Spatial 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 data Spatial index structures demo http www cs umd edu brabec quadtree index html 3 C Shahabi Spatial Indexing CSCI585 Mapping spatial object into point In either same lower or higher dimensional spaces Good for storage purposes Problems with queries like finding the nearest objects Bucketing methods Based on spatial occupancy Decomposing the space from which the data is drawn Minimum bounding rectangle MBR e g R Tree data dependent Disjoint cells e g R Tree Blocks of uniform size greater degree of Distribution of the data e g quadtree data independence 4 C Shahabi 2 R Tree CSCI585 proposed in 1984 by Guttman Based on Minimum Bounding Rectangle m M 1 3 R1 R2 a R3 a b R4 d g h R5 c i R6 e f g b h e d i f c bounding rectangles could overlap each others e g R3 vs R4 an object is only associated with one bounding rectangle 5 C Shahabi CSCI585 R Tree proposed in 1984 by Guttman Height balanced tree similar to B tree for k dimensions Every leaf node contains between m m M 2 and M index records unless it is the root For 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 tuple Every non leaf node has between m and M children unless it is the root For 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 level The root node has at least two children unless it is a leaf 6 C Shahabi 3 Insertion Processes CSCI585 A new index entry A d f e X ChooseLeaf C No m X C Different variant Exhaustive Quadratic Linear Packed Hilbert Packed etc SplitNode C l B g Yes Install X i h Has room k j Adjust all related entries AdjustTree 7 C Shahabi CSCI585 Processes of Quadratic Spilt page 52 in Guttman s paper Pick first entry for each group Run PickSeeds A d f e h g k l j i X m C B ABC d e f g h i j k l m 8 C Shahabi 4 Processes of Quadratic Spilt CSCI585 page 52 in Guttman s paper PickSeeds A d f e PS1 Calculate inefficiency of grouping entries together For each pair of E1 and E2 compose a rectangle R including E1 and E2 Calculate d area R area E1 area E2 PS2 Choose the most wasteful pair Choose the pair with the largest d k l j X i C m B g l l l h k ABC X m d e f l g h i j k l m 9 j C Shahabi CSCI585 Processes of Quadratic Spilt page 52 in Guttman s paper Pick first entry for each group PickSeeds A d f e G1 G2 l m h Check if done g No k G1 l j i G2 m B X Select entry to assign PickNext ABC d e f g h i j k l m 10 C Shahabi 5 CSCI585 Processes of Quadratic Spilt page 52 in Guttman s paper Pick first entry for each group PickSeeds A d f e G1 G2 l m g No PickNext PN1 Determine cost of putting each entry in each group For each entry E calculate 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 d2 j i G2 m B h Check if done k G1 l k G1 G2 X X G1 mG2 G1 j 11 G2 C Shahabi CSCI585 Processes of Quadratic Spilt page 52 in Guttman s paper Pick first entry for each group PickSeeds A d f e G1 G2 l m h Check if done g No k G1 l j i G2 m B X Select entry to assign PickNext ABC G1 G2 l m k d e f g h i j k l m 12 C Shahabi 6 CSCI585 Processes of Quadratic Spilt page 52 in Guttman s paper Pick first entry for each group PickSeeds A d f e G1 G2 l m h Check if done g No Select entry to assign PickNext j i G2 m B X G1 j G1 G2 l m k k G1 l X G1 G2 G2 13 C Shahabi CSCI585 Processes of Quadratic Spilt page 52 in Guttman s paper Pick first entry for each group PickSeeds A d f e G1 G2 l m h Check if done g No k G1 l j i X G2 m B Select entry to assign PickNext G1 G2 l m k X 14 C Shahabi 7 CSCI585 Processes of Quadratic Spilt page 52 in Guttman s paper Pick first entry for each group PickSeeds A d f e G1 G2 l m k G1 l j i h Check if done B g No X G2 m Select entry to assign PickNext A B G1G2 G1 G2 l m k X j g h i d e f l k mx j 15 C Shahabi CSCI585 Your Exercise Before Midterm m M 2 4 F D K G E J H L Build a R Tree for these spatial data Hint You could use the Spatial index structures demo application step by step 16 C Shahabi 8 Search Object in R Tree CSCI585 Input T j E j Leaf Yes No g Check each entry E of T Search each subtree E of T Overlap Overlap A d k G1 l f j e i x h G2 B m Yes A B G1G2 Yes Qualifying record d e f g h i l k mx j 17 C Shahabi CSCI585 Main Drawbacks of R Tree R 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 18 C Shahabi 9 R Tree CSCI585 Overcome problems with R Tree If node overlaps with several rectangles insert the node in all Decompose the space into disjoint cells R1 R2 b R3 d g h R4 R5 c h i a b e i h R6 e g c f i d i c f 19 C Shahabi CSCI585 R Tree Properties R tree and cell trees used approach of discomposing space into cells R trees deals with collection of objects bounded by …