Spatial Access MethodsGeneral OverviewSAMs - Detailed outlineSpatial Access Methods - problemSlide 5Slide 6Slide 7Slide 8Slide 9SAMs - motivationSlide 11Slide 12Slide 13Slide 14Slide 15SAMs: solutionsSlide 17k-d trees2-d trees – node structure2-d trees – Example2-d trees: Insertion/Search2-d trees – Example of Insertion2-d trees: DeletionSlide 242-d trees: Range QueriesSlide 26Point QuadtreesSlide 28Point quadtrees - InsertionPoint Quadtrees - InsertionPoint quadtrees: DeletionSlide 32Point quadtrees: Range SearchesSlide 34MX-QuadtreesSlide 36MX-Quadtrees - InsertionSlide 38MX-Quadtrees - DeletionMX-Quadtrees –Range QueriesSlide 41z-orderingSlide 43Slide 44Slide 45Slide 46Slide 47Slide 48Slide 49Slide 50Slide 51Slide 52Slide 53Slide 54Slide 55Slide 56Slide 57Slide 58Slide 59Slide 60Slide 61Slide 62Slide 63Slide 64Slide 65Slide 66z-ordering - Detailed outlinez-ordering - usage & algo’sSlide 69Slide 70Slide 71Slide 72Slide 73Slide 74Slide 75Slide 76Slide 77Slide 78Slide 79Slide 80Slide 81Slide 82Slide 83Slide 84Slide 85Slide 86z-ordering - regionsSlide 88Slide 89Slide 90Slide 91Slide 92Slide 93Slide 94Slide 95Slide 96Slide 97Slide 98Slide 99Slide 100Slide 101Slide 102Slide 103Slide 104Slide 105Slide 106Slide 107z-ordering - variationsSlide 109Slide 110Slide 111Slide 112Slide 113Slide 114Slide 115Slide 116z-ordering - analysisSlide 118Slide 119Slide 120Slide 121Slide 122Slide 123z-ordering - fun observationsSlide 125Slide 126Slide 127ConclusionsSpatial Access MethodsCSCI 2720Spring 2005General OverviewMultimedia IndexingSpatial Access Methods (SAMs)k-d treesPoint QuadtreesMX-Quadtreez-orderingR-treesSAMs - Detailed outlinespatial access methodsproblem definitionk-d treespoint quadtreesMX-quadtreesz-ordering R-treesSpatial Access Methods - problemGiven a collection of geometric objects (points, lines, polygons, ...)organize them on disk, to answer spatial queriesSpatial Access Methods - problemGiven a collection of geometric objects (points, lines, polygons, ...)organize them on disk, to answerpoint queriesrange queriesk-nn queries spatial joins (‘all pairs’ queries)Spatial Access Methods - problemGiven a collection of geometric objects (points, lines, polygons, ...)organize them on disk, to answerpoint queriesrange queriesk-nn queriesspatial joins (‘all pairs’ queries)Spatial Access Methods - problemGiven a collection of geometric objects (points, lines, polygons, ...)organize them on disk, to answerpoint queriesrange queriesk-nn queriesspatial joins (‘all pairs’ queries)Spatial Access Methods - problemGiven a collection of geometric objects (points, lines, polygons, ...)organize them on disk, to answerpoint queriesrange queriesk-nn queries (nn=nearest neighbors)spatial joins (‘all pairs’ queries)Spatial Access Methods - problemGiven a collection of geometric objects (points, lines, polygons, ...)organize them on disk, to answerpoint queriesrange queriesk-nn queriesspatial joins (‘all pairs’ within ε)SAMs - motivationQ: applications?SAMs - motivationsalaryagetraditional DBGISSAMs - motivationsalaryagetraditional DBGISSAMs - motivationCAD/CAMfind elementstoo closeto each otherSAMs - motivationCAD/CAMday1 365day1 365S1SnF(S1)F(Sn)SAMs - motivationeg, avgeg,. stdSAMs: solutionsK-d treespoint quadtreesMX-quadtreesz-orderingR-trees(grid files)Q: how would you organize, e.g., n-dim points, on disk? (C points per disk page)SAMs - Detailed outlinespatial access methodsproblem dfnk-d treespoint quadtreesMX-quadtreesz-orderingR-treesk-d treesUsed to store k dimensional point dataIt is not used to store region dataA 2-d tree (i.e., for k=2) stores 2-dimensional point data while a 3-d tree stores 3-dimensional point data, etc.2-d trees – node structureBinary treesInfo: information fieldXval,Yval: coordinates of a point associated with the nodeLlink, Rlink: pointers to childrenProperties (N: node):If level N even -> for all nodes M in the subtree rooted at N.Llink: M.Xval < N.Xval for all nodes P in the subtree rooted at N.Rlink: P.Xval >= N.XvalIf level N odd ->Similarly use Yvals2-d trees – Example2-d trees: Insertion/SearchTo insert a node N into the tree pointed by TIf N and T agree on Xval, Yval then overwrite TElse, branch left if N.Xval < T.xval, right otherwise (even levels)Similarly for odd levels (branching on Yvals)2-d trees – Example of InsertionCity (Xval, Yval)Banja Luka (19, 45)Derventa (40, 50)Toslic (38, 38)Tuzla (54, 35)Sinj (4, 4)Splitting of region by Banja LukaSplitting of region by DerventaSplitting of region by Toslic Splitting of region by Sinj2-d trees: DeletionDeletion of point (x,y) from TIf N is a leaf node easyOtherwise either Tl (left subtree) or Tr (right subtree) is non-emptyFind a “candidate replacement” node R in Tl or TrReplace all of N’s non-link fields by those of RRecursively delete R from Ti Recursion guaranteed to terminate - Why?2-d trees: DeletionFinding candidate replacement nodes for deletion Replacement node R must bear same spatial relation to all nodes in Tl and Tr as node N2-d trees: Range QueriesQ: Given a point (xc, yc) and a distance r find all points in the 2-d tree that lie within the circleA: Each node N in a 2-d tree implicitly represents a region RN – If the circle (specified by the query) has no intersection with RN then there is no point in searching the subtree rooted at node NSAMs - Detailed outlinespatial access methodsproblem dfnk-d treespoint quadtreesz-orderingR-treesPoint QuadtreesRepresent point dataAlways split regions into 4 parts2-d tree: a node N splits a region into two by drawing one line through the point (N.xval, N.yval)Point quadtree: a node N splits a region by drawing a horizontal and a vertical line through the point (N.xval, N.yval)Four parts: NW, SW, NE, and SE quadrantsQ: Quadtree nodes have 4 children?Point QuadtreesNodes in point quadtrees represent regionsPoint quadtrees - InsertionCity (Xval, Yval)Banja Luka (19, 45)Derventa (40, 50)Toslic (38, 38)Tuzla (54, 35)Sinj (4, 4)Splitting of region by Banja LukaSplitting of region by DerventaSplitting of region by Toslic Splitting of region by SinjSplitting of region by TuzlaPoint Quadtrees - InsertionPoint quadtrees:
View Full Document