DOC PREVIEW
USC CSCI 585 - Session15

This preview shows page 1-2-16-17-18-34-35 out of 35 pages.

Save
View full document
View full document
Premium Document
Do you want full access? Go Premium and unlock all 35 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 35 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 35 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 35 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 35 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 35 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 35 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 35 pages.
Access to all documents
Download any document
Ad free experience

Unformatted text preview:

CSCI585CSCI585C. ShahabiCSCI585CSCI585Spatial Index Structures (R-tree Family)Instructor: Cyrus ShahabiCSCI585CSCI585C. ShahabiCSCI585CSCI585Problem• Given a collection of geometric objects (points, lines, polygons, ...)• organize them on disk, to answer spatial queries (range, nn, etc)CSCI585CSCI585C. ShahabiCSCI585CSCI585Problem• 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 dataCSCI585CSCI585C. ShahabiCSCI585CSCI585R-trees• [Guttman 84] Main idea: extend B+-tree to multi-dimensional spaces!– (only deal with Minimum Bounding Rectangles - MBRs)CSCI585CSCI585C. ShahabiCSCI585CSCI585• 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 leafCSCI585CSCI585C. ShahabiCSCI585CSCI585Example• m=2,M=4: group nearby rectangles to parent MBRs; each group -> disk pageABCDEFGHJICSCI585CSCI585C. ShahabiCSCI585CSCI585Example• m=2, M=4ABCDEFGHIJP1P2P3P4F GD EH I JA B CCSCI585CSCI585C. ShahabiCSCI585CSCI585Example• m=2, M=4ABCDEFGHIJP1P2P3P4P1 P2 P3 P4F GD EH I JA B CCSCI585CSCI585C. ShahabiCSCI585CSCI585R-trees - format of nodes• {(MBR; obj_ptr)} for leaf nodesP1 P2 P3 P4A B Cx-low; x-highy-low; y-high...objptr...CSCI585CSCI585C. ShahabiCSCI585CSCI585R-trees - format of nodes• {(MBR; node_ptr)} for non-leaf nodesP1 P2 P3 P4A B Cx-low; x-highy-low; y-high...nodeptr...CSCI585CSCI585C. ShahabiCSCI585CSCI585E204 6810246810x axisy axisbEfomitted1E2edcahgE3E5E6E4E78contentsE9iabc def h gE1E2E3E4E5E6E7E8RootE9iE1E2E4E5E8CSCI585CSCI585C. ShahabiCSCI585CSCI585Insertion ProcessesdefigmABhkljCXA new index entryXChooseLeafHas roomInstall XYesSplitNodeNoCAdjustTreeCAdjust all related entriesDifferent variant:•Exhaustive•Quadratic•Linear•Packed•Hilbert Packed•…etc.CSCI585CSCI585C. ShahabiCSCI585CSCI585Processes of Quadratic Spilt(page 52 in Guttman’s paper [1])Pick first entry for each groupRun PickSeedsdefigmABhkljCXd e fg h i j k l mCBACSCI585CSCI585C. 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 dljkllXmlCSCI585CSCI585C. 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)NoigmdefABhkljG1XG2CSCI585CSCI585C. 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 d2NoG2G1G2kG2G1mXG2G1jCSCI585CSCI585C. 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)NoG1G2l mkigmdefABhkljG1XG2CSCI585CSCI585C. 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)NoG1G2l mkigmdefABhkljG1XG2jXCSCI585CSCI585C. 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)NoigmdefABhkljG1XG2G1G2l mkXCSCI585CSCI585C. 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)NoigmdefABhkljG1XG2G1G2l mkXjd e fg h i l kG2G1BAm x jCSCI585CSCI585C. ShahabiCSCI585CSCI585Excercise• (m,M)=(2,4)• Build a R-Tree for these spatial dataDFGEHJKLCSCI585CSCI585C. ShahabiCSCI585CSCI585R-trees:SearchABCDEFGHIJP1P2P3P4P1 P2 P3 P4F GD EH I JA B CCSCI585CSCI585C. ShahabiCSCI585CSCI585R-trees:Search• 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.CSCI585CSCI585C. ShahabiCSCI585CSCI585Search Object in R-TreeigmdefABhkljG1xG2d e fg h i l kG2G1BAm x jInput (T, j)Leaf?YesFor each subtree E of TNoE Containsj(E,j)YesCheck each entry E of TE=jQualifyingrecordYesCSCI585CSCI585C. ShahabiCSCI585CSCI585Overlap query in R-Tree(find objects that overlap with Z)igmdefABhkljG1xG2d e fg h i l kG2G1BAm x jInput (T, Z)Leaf?YesSearch each subtree E of TNoOverlap(E,j)YesCheck each entry E of TOverlapQualifyingrecordYesCSCI585CSCI585C. ShahabiCSCI585CSCI585Main 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?CSCI585CSCI585C. ShahabiCSCI585CSCI585R+-Tree• Overcome problems with R-Tree• If node overlaps with several rectangles insert the node in all• Decompose the space into disjoint cellsR2R3 R4 R5 R6R1a bd g h c i e fh i c igdhcifebCSCI585CSCI585C. ShahabiCSCI585CSCI585R+-Tree Properties• R+-tree used approach of discomposing space into cells– R+-trees deals with collection of objects bounded by rectangles• R+-trees is extension of k-d-B-tree• Retrieval times are smaller• When summing the objects, needs


View Full Document

USC CSCI 585 - Session15

Download Session15
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 Session15 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 Session15 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?