GITTA-Logo
PDF Version of this document Search Help

Lesson Navigation IconSpatial Partitioning and Indexing

Unit Navigation IconOverview

Unit Navigation IconRegular Decomposition

Unit Navigation IconObject-oriented Decomposition

LO Navigation IconBinary Tree

LO Navigation IconR-Trees

Unit Navigation IconSummary

Unit Navigation IconBibliography

Unit Navigation IconMetadata


GITTA/CartouCHe news:


Go to previous page Go to next page

Object-oriented Decomposition

Introduction

In data driven indexing methods (object-directed decomposition) the objects determine the partitioning of space (e.g. the 2D space containing the lines) into regions called buckets. They are also commonly known as bucketing methods. There are some principal approaches to decomposing the space from which the data is drawn. In one possible approach to object-oriented decomposition, partitioning is achieved by applying divide-and-conquer strategies whereby individual data points or lines may be selected to subdivide the data space into successively smaller half-spaces (Binary-tree). Another approach buckets the data based on the concept of a minimum bounding (or enclosing) rectangle (R-tree).
Such strategies generate hierarchical or tree data structures, in which descending down each branch of the tree should result in reducing the relevant volume of data at each stage. The branching factor defines the number of branches at each fork and the number of leaves at the end of each branch. The height of a binary tree is the number of levels within the tree.

In the following section, two main approaches of object-directed decomposition will be presented in order to clarify the principles that drive these methods.

Top Go to previous page Go to next page