Swinbank, Richard (2008). Virtual forced splitting in multidimensional access methods. University of Birmingham. Ph.D.
Preview |
Swinbank08PhD.pdf
Download (2MB) |
Abstract
External, tree-based, multidimensional access methods typically attempt to provide B+ tree like behaviour and performance in the organisation of large collections of multidimensional data. The B+ tree’s efficiency comes directly from the fact that it organises data occupying a single dimension, which can be linearly ordered, and partitioned at arbitrary points in that order. Using a multiway tree to partition a multidimensional space becomes increasingly difficult with increasing dimensionality, often leading to the loss of desirable properties like high fanout and low internode overlap. The K-D-B tree is an example of a structure in which one property, that of zero internode overlap, is provided at the expense of another, high fanout. Its approach to doing this, by forced splitting, is shared by a collection of other structures, and in 1995 Freeston suggested a novel approach to mitigate the effects of forced splits, by executing them virtually. This approach has not been taken up widely, but we believe it shows a great deal of promise. In the thesis, we examine the virtual forced splitting approach in depth. We identify a number of problems presented by the approach, and propose solutions to them, allowing us to characterise a general class of virtual forced splitting structures that we call VFS-trees. The efficacy of our approach is demonstrated by our implementation of a new VFS structure, and by what we believe to be the first implementation of a BV-tree, together with new algorithms for region and K Nearest Neighbour search. We further report experimental results on construction, exact-match search and K-NN search of BV-trees, and show how they compare, very favourably, with the corresponding operations on the currently most popular multidimensional file access method, the R*-tree.
| Type of Work: | Thesis (Doctorates > Ph.D.) |
|---|---|
| Award Type: | Doctorates > Ph.D. |
| Supervisor(s): | Supervisor(s) Email ORCID Sexton, Alan P. UNSPECIFIED UNSPECIFIED |
| Licence: | |
| College/Faculty: | Colleges > College of Engineering & Physical Sciences |
| School or Department: | School of Computer Science |
| Funders: | None/not applicable |
| Subjects: | Q Science > QA Mathematics > QA75 Electronic computers. Computer science |
| URI: | https://bham-theses.eprints-hosting.org/id/eprint/213 |
Actions
![]() |
Request a Correction |
![]() |
View Item |
Downloads
Downloads per month over past year
Tools
Tools
