DOC PREVIEW
USC CSCI 585 - R-Tree

This preview shows page 1-2-3-4 out of 11 pages.

Save
View full document
View full document
Premium Document
Do you want full access? Go Premium and unlock all 11 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 11 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 11 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 11 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 11 pages.
Access to all documents
Download any document
Ad free experience

Unformatted text preview:

R-TREES. A DYNAMIC INDEX STRUCTURE FOR SPATIAL SEARCHING Antomn Guttman University of Cahforma Berkeley Abstract In order to handle spatial data efficiently, as required in computer aided design and geo-data applications, a database system needs an mdex mechanism that ti help it retrieve data items quickly accordmg to their spatial locations However, traditional mdexmg methods are not well suited to data oblects of non-zero size located m multi- dimensional spaces In this paper we describe a dynarmc mdex structure called an R-tree winch meets this need, and give algorithms for searching and updatmg it. We present the results of a series of tests which indicate that the structure performs well, and conclude that it is useful for current database systems m spatial applications 1. Intxoduction Spatial data oblects often cover areas m multi-dimensional spaces and are not well represented by pomt locations For example, map objects like counties, census tracts etc occupy regions of non-zero size m two dnnenslons A common operation on spatial data 1s a search for all oblects m an area, for example to find all counties that have land mthm 20 nnles of a particular pomt Tl~s kmd of spatial search occurs frequently m computer tided design (CAD) and geo-data applications, and therefore it 1s unportant to be able to retneve oblects efficiently according to their spatial loca- tion ‘llus research was sponsored by National Science Foundation grant ECS-8300463 and An Force Ofi?ce of Scientific Research grant AFOSR-83-0254 Pcrnuwon to copy mthout fee all of part of tlus matcnal Is granted prowled that the copses are not made or dmtnbutai for drrcct commcrctal advantage, the ACM copyright nohcc and the tltk of the pubbcauon and its date appear, and nottce u gwcn that copying L) by pcrnusslon of the Assoctauon for Computmg Macluncry To copy othc~~~sc, or to rcpubbsh, rqmrcs a fee and/or spcctfii pernuwon 0 1984 ACM O-89791-128-8/84/006/0047 $00 75 An mdex based on obJects’ spatial loca- tions 1s desirable, but classical one- dunenaonal database mdexmg structures are not appropriate to multi-dimensional spatial searchmg Structures based on exact matchmg of values, such as hash tables, are not useful because a range search 1s requed Structures usmg one- dnnenslonal ordermg of key values, such as B-trees and ISAM mdexes, do not work because the search space is multl- dnnenslonal A number of structures have been pro- posed for handling muhi-dimensional point data, and a survey of methods can be found m [5] Cell methods [4,8,16] are not good for dynamic structures because the cell boundmes must be decided m advance Quad trees [i’) and k-d trees [3] do not take pagmg of secondary memory into account. K-D-B trees [13] are designed for paged memory but are useful only for pomt data The use of mdex mter- vals has been suggested m [15], but tlus method cannot be used m multiple dnnen- sions Corner stitchmg [ 121 is an example of a structure for two-dimensional spatial searchmg smtable for data objects of non- zero size, but it assumes homogeneous pr~ mary memory and 1s not e-lent for ran- dom searches m very large collections of data. Grid files [lo] handle non-pomt data by mapping each object to a point in a 47higher-cllmenslonal space In this paper we descnbe an alternative structure called an R-tree wmch represents data objects by mtervals in several dnnenslons Section 2 outhnes the structure of an R-tree and Section 3 gives algornhms for searchmg, msertmg, deletmg, and updat- mg Results of R-tree mdex performance tests are presented m Section 4 Section 5 contams a summary of our conclusions 2. R-Tree Index Structure An R-tree 1s a height-balanced tree slrmlar to a B-tree [Z, 61 Pnth mdex records in its leaf nodes contammg pomters to data objects Nodes correspond to disk pages If the mdex 1s &Sk-resident, and the structure 1s designed so that a spatial search requnes visltmg only a small number of nodes The mdex 1s completely dynannc; inserts and deletes can be mter- rmxed pnth searches and no penodlc reor- gamzatlon 1s requn-ed. A spatial database consists of a collec- tion of tuples representmg spatial objects, and each tuple has a umque ldenttier wluch can be used to retneve it Leaf nodes m an R-tree contam mdex record entnes of the form (I, tupte -w!enCtfier) where tu#e -cdentijier refers to a tuple m the database and I 1s an n-dunenaonal rectangle wlvch 1s the boundmg box of the spatial object mdexed Here n 1s the number of dnnenaons and JT, is a closed bounded mterval [a ,b ] descnb- mg the extent of the object along dnnen- sion i. Alternatively 4 may have one or both endpoints equal to mfhuty, mdlcatmg that the object extends outward mdefimtely Non-leaf nodes contam entnes of the form (I, child -powder) where chdd -poznter 1s the address of a lower node in the R-tree and I covers all rectangles m the lower node’s entnes Let Y be the maxmum number of entn3 that snll At m one node and let ml- 2 be a parameter speclfymg the nnnnnum number of entnes m a node An R-tree satisfies the followmg properties Cl1 (2) (3) (4) (5) (6) Every leaf node contalns ‘between m and Y mdex records unless it 1s the root For each mdex record (I, tuple -zdent@er) m a leaf node, I 1s the smallest rectangle that spatially contams the n-dnnenslonal data obJect represented by the mdlcated tuple Every non-leaf node has between m and M chndren unless it 1s the root For each entry (I, child -poznter) ur a non-leaf node, I 1s the smallest rectan- gle that spatially contams the rectan- gles m the child node The root node has at least two cmdren unless it is a leaf All leaves appear on the same level Figure 2 la and 2 lb show the structure of an R-tree and illustrate the


View Full Document

USC CSCI 585 - R-Tree

Download R-Tree
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 R-Tree 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 R-Tree 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?