Show simple item record

dc.contributor.authorHamilton, Christopher
dc.date.accessioned2011-04-15T14:02:33Z
dc.date.available2011-04-15T14:02:33Z
dc.date.issued2011-04-15
dc.identifier.urihttp://hdl.handle.net/10222/13363
dc.description.abstractThis thesis focuses on range searching data structures, an elementary problem in computational geometry with research spanning decades. These problems often involve very large data sets. Processor speeds increase faster than memory speeds, thus the gap between the rate at which CPUs can process data and the rate at which it can be retrieved is increasing. To bridge this gap, various levels of cache are used. Since cache misses are costly, algorithms should be cache-friendly. The input-output (I/O) model was the first model for constructing cache-efficient algorithms, focusing on a two-level memory hierarchy. Algorithms for this model require manual tuning to determine optimal values for hardware dependent parameters, and are only optimal at a single level of a memory hierarchy. Cache-oblivious (CO) algorithms are built without knowledge of the hierarchy, allowing them to be optimal across all levels at once. There exist strong theoretical and practical results for I/O-efficient range searching. Recently, the CO model has received attention, but range searching remains poorly understood. This thesis explores data structures for CO range counting and reporting. It presents the first space and worst-case query-time optimal approximate range counting structure for a family of related problems, and associated O(N log N)-space query-optimal reporting structures. The approximate counting structure is the first of its kind in internal memory, I/O and CO models. Researchers have been trying to create linear-space query-optimal CO reporting structures. This thesis shows that for a variety of problems, linear space is in fact impossible. Heuristics are also used for building cache-friendly algorithms. Space-filling curves are continuous functions mapping multi-dimensional sets into one-dimensional ones. They are used to build search structures in the hopes that objects that were close in the original space remain close in the resulting ordering. This results in queries incurring fewer page swaps when traversing the structure. The Hilbert curve is notably good at this, but often imposes a space or time penalty. This thesis introduces compact Hilbert indices, which remove the ineffiency inherent for input point sets with bounding boxes smaller than their bounding hypercubes.en_US
dc.language.isoenen_US
dc.subjectcomputational geometryen_US
dc.subjectrange searchingen_US
dc.subjectrange countingen_US
dc.subjectapproximate range countingen_US
dc.subjectexternal memoryen_US
dc.subjectcache obliviousen_US
dc.subjectdata structuresen_US
dc.subjectalgorithmsen_US
dc.subjectspace-filling curvesen_US
dc.subjectHilbert curveen_US
dc.subjectorthogonal range searchingen_US
dc.subjecthalfspace range searchingen_US
dc.subjectshallow cuttingsen_US
dc.subjectlower boundsen_US
dc.titleRange Searching Data Structures with Cache Localityen_US
dc.date.defence2011-03-17
dc.contributor.departmentFaculty of Computer Scienceen_US
dc.contributor.degreeDoctor of Philosophyen_US
dc.contributor.external-examinerDr. Pat Morinen_US
dc.contributor.graduate-coordinatorDr. Malcolm Heywooden_US
dc.contributor.thesis-readerDr. Andrew Rau-Chaplinen_US
dc.contributor.thesis-readerDr. Alex Brodskyen_US
dc.contributor.thesis-supervisorDr. Norbert Zehen_US
dc.contributor.ethics-approvalNot Applicableen_US
dc.contributor.manuscriptsNot Applicableen_US
dc.contributor.copyright-releaseNot Applicableen_US
 Find Full text

Files in this item

Thumbnail

This item appears in the following Collection(s)

Show simple item record