Unformatted text preview:

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 OverviewMultimedia IndexingSpatial Access Methods (SAMs)k-d treesPoint QuadtreesMX-Quadtreez-orderingR-treesSAMs - Detailed outlinespatial access methodsproblem definitionk-d treespoint quadtreesMX-quadtreesz-ordering R-treesSpatial Access Methods - problemGiven a collection of geometric objects (points, lines, polygons, ...)organize them on disk, to answer spatial queriesSpatial Access Methods - problemGiven a collection of geometric objects (points, lines, polygons, ...)organize them on disk, to answerpoint queriesrange queriesk-nn queries spatial joins (‘all pairs’ queries)Spatial Access Methods - problemGiven a collection of geometric objects (points, lines, polygons, ...)organize them on disk, to answerpoint queriesrange queriesk-nn queriesspatial joins (‘all pairs’ queries)Spatial Access Methods - problemGiven a collection of geometric objects (points, lines, polygons, ...)organize them on disk, to answerpoint queriesrange queriesk-nn queriesspatial joins (‘all pairs’ queries)Spatial Access Methods - problemGiven a collection of geometric objects (points, lines, polygons, ...)organize them on disk, to answerpoint queriesrange queriesk-nn queries (nn=nearest neighbors)spatial joins (‘all pairs’ queries)Spatial Access Methods - problemGiven a collection of geometric objects (points, lines, polygons, ...)organize them on disk, to answerpoint queriesrange queriesk-nn queriesspatial joins (‘all pairs’ within ε)SAMs - motivationQ: applications?SAMs - motivationsalaryagetraditional DBGISSAMs - motivationsalaryagetraditional DBGISSAMs - motivationCAD/CAMfind elementstoo closeto each otherSAMs - motivationCAD/CAMday1 365day1 365S1SnF(S1)F(Sn)SAMs - motivationeg, avgeg,. stdSAMs: solutionsK-d treespoint quadtreesMX-quadtreesz-orderingR-trees(grid files)Q: how would you organize, e.g., n-dim points, on disk? (C points per disk page)SAMs - Detailed outlinespatial access methodsproblem dfnk-d treespoint quadtreesMX-quadtreesz-orderingR-treesk-d treesUsed to store k dimensional point dataIt is not used to store region dataA 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 structureBinary treesInfo: information fieldXval,Yval: coordinates of a point associated with the nodeLlink, Rlink: pointers to childrenProperties (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.XvalIf level N odd ->Similarly use Yvals2-d trees – Example2-d trees: Insertion/SearchTo insert a node N into the tree pointed by TIf N and T agree on Xval, Yval then overwrite TElse, 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: DeletionDeletion of point (x,y) from TIf N is a leaf node easyOtherwise either Tl (left subtree) or Tr (right subtree) is non-emptyFind a “candidate replacement” node R in Tl or TrReplace all of N’s non-link fields by those of RRecursively delete R from Ti Recursion guaranteed to terminate - Why?2-d trees: DeletionFinding 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 QueriesQ: Given a point (xc, yc) and a distance r find all points in the 2-d tree that lie within the circleA: 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 outlinespatial access methodsproblem dfnk-d treespoint quadtreesz-orderingR-treesPoint QuadtreesRepresent point dataAlways split regions into 4 parts2-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 quadrantsQ: Quadtree nodes have 4 children?Point QuadtreesNodes 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

UGA CSCI 2720 - rangeSearching

Documents in this Course
Load more
Download rangeSearching
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view rangeSearching and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view rangeSearching 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?