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.