CSCI585 Spatial Index Structures R tree Family Instructor Cyrus Shahabi C Shahabi CSCI585 Problem Given a collection of geometric objects points lines polygons organize them on disk to answer spatial queries range nn etc C Shahabi CSCI585 Problem 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 C Shahabi CSCI585 R trees Guttman 84 Main idea extend B tree to multi dimensional spaces only deal with Minimum Bounding Rectangles MBRs C Shahabi CSCI585 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 C Shahabi Example CSCI585 m 2 M 4 group nearby rectangles to parent MBRs each group disk page I AC G F B E D C Shahabi H J Example CSCI585 m 2 M 4 P1 P3 AC G F B E P2 D C Shahabi I H P4 J A B C D E H I F G J Example CSCI585 m 2 M 4 P1 P3 AC F E C Shahabi P1 P2 P3 P4 G B P2 D I H P4 J A B C D E H I F G J CSCI585 R trees format of nodes MBR obj ptr for leaf nodes P1 P2 P3 P4 x low x high obj y low y high ptr C Shahabi A B C CSCI585 R trees format of nodes MBR node ptr for non leaf nodes x low x high y low y high node ptr P1 P2 P3 P4 A B C C Shahabi CSCI585 y axis Root E7 10 E1 e f 8 E8 6 4 2 E9 contents omitted E4 b i h E6 E 2 E 3 E 2 E 1 g E5 d E 1 E2 E 4 E 5 E 6 c d e E 7 E 8 E 9 a c a E3 b f h g x axis 0 C Shahabi 2 4 6 8 10 E 4 E 5 E 8 i Insertion Processes CSCI585 A new index entry A d f e X ChooseLeaf C h g Has room No Yes Install X SplitNode C Adjust all related entries AdjustTree C Shahabi k l j i m X C B Different variant Exhaustive Quadratic Linear Packed Hilbert Packed etc CSCI585 Processes of Quadratic Spilt page 52 in Guttman s paper 1 Pick first entry for each group Run PickSeeds A d f e h g k j i X m B ABC d e f C Shahabi g h i l j k l m C CSCI585 Processes of Quadratic Spilt 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 g i X m B ABC X m l j C Shahabi d e f g h i l j l l l h k j k l m C 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 C Shahabi g h i j k l m 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 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 g k G1 G2 X G1 mG2 G1 j G2 C Shahabi X 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 C Shahabi d e f g h i j k l m 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 C Shahabi j i G2 m B X G1 j G1 G2 l m k k G1 l G2 X G1 G2 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 G1 G2 l m k X C Shahabi k G1 l j i B X mG2 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 X mG2 B g No j i h Check if done k G1 l Select entry to assign PickNext A B G1G2 G1 G2 l m k X j C Shahabi d e f g h i l k mx j Excercise CSCI585 m M 2 4 F D K G E J H L Build a R Tree for these spatial data C Shahabi R trees Search CSCI585 P1 P3 AC F E C Shahabi P1 P2 P3 P4 G B P2 D I H P4 J A B C D E H I F G J R trees Search CSCI585 Main points every parent node completely covers its children a child MBR may be covered by more than one parent it is stored under ONLY ONE of them ie no need for dup elim a point query may follow multiple branches C Shahabi CSCI585 Search Object in R Tree Input T j E j Leaf Yes No g Check each entry E of T For each subtree E of T E j E Contains j Yes A B G1G2 Yes Qualifying record C Shahabi A d k G1 l f j e i …