|
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.