VTechWorks staff will be away for the winter holidays starting Tuesday, December 24, 2024, through Wednesday, January 1, 2025, and will not be replying to requests during this time. Thank you for your patience, and happy holidays!
 

A paging scheme for pointer-based quadtrees

Simple item page
dc.contributor.authorBrown, Patrick R.en
dc.contributor.committeechairShaffer, Clifford A.en
dc.contributor.committeememberAbrams, Marcen
dc.contributor.committeememberHeath, Lenwood S.en
dc.contributor.departmentComputer Science and Applicationsen
dc.date.accessioned2014-03-14T21:46:50Zen
dc.date.adate2009-10-06en
dc.date.available2014-03-14T21:46:50Zen
dc.date.issued1992-05-19en
dc.date.rdate2009-10-06en
dc.date.sdate2009-10-06en
dc.description.abstractThe quadtree is a family of data structures that organize spatial data using recursive subdivision. A pointer-based quadtree uses an explicit tree structure to represent the subdivision, while a linear quadtree holds a sorted list of records corresponding to the leaves of the tree structure. Small quadtrees are typically represented using pointers since this leads to simpler algorithms. However, linear quadtrees have been historically used to represent larger data sets. The primary reason is that linear quadtrees are easily organized on pages in disk files. In addition, linear quadtrees were thought to require less space than pointerbased quadtrees. Though pointer-based quadtrees have many other advantages, there has still been much interest in the linear quadtree. This thesis presents a pointer-based representation for quadtrees called the paged-pointer quadtree. The paged-pointer quadtree overcomes both of the historical advantages of the linear quadtree. It partitions the nodes of a pointer-based quadtree into pages, stores these nodes in order, and manages pages using B-tree techniques. In addition, a paged-pointer quadtree always requires less space than a corresponding linear quadtree. Our representation overcomes the performance problems associated with representing traditional pointer-based quadtrees on disk. As a result, our implementation produces better performance than highly optimized systems based on linear quadtrees.en
dc.description.degreeMaster of Scienceen
dc.format.extentvii, 75 leavesen
dc.format.mediumBTDen
dc.format.mimetypeapplication/pdfen
dc.identifier.otheretd-10062009-020024en
dc.identifier.sourceurlhttp://scholar.lib.vt.edu/theses/available/etd-10062009-020024/en
dc.identifier.urihttp://hdl.handle.net/10919/45001en
dc.language.isoenen
dc.publisherVirginia Techen
dc.relation.haspartLD5655.V855_1992.B768.pdfen
dc.relation.isformatofOCLC# 26233980en
dc.rightsIn Copyrighten
dc.rights.urihttp://rightsstatements.org/vocab/InC/1.0/en
dc.subject.lccLD5655.V855 1992.B768en
dc.subject.lcshComputer graphicsen
dc.subject.lcshData structures (Computer science)en
dc.titleA paging scheme for pointer-based quadtreesen
dc.typeThesisen
dc.type.dcmitypeTexten
thesis.degree.disciplineComputer Science and Applicationsen
thesis.degree.grantorVirginia Polytechnic Institute and State Universityen
thesis.degree.levelmastersen
thesis.degree.nameMaster of Scienceen

Files

Original bundle
Now showing 1 - 1 of 1
Thumbnail Image
Name:
LD5655.V855_1992.B768.pdf
Size:
3.15 MB
Format:
Adobe Portable Document Format
Download

Collections

Masters Theses