nick at nickhill.co.uk
Wed Apr 26 18:40:10 BST 2006
dblasby at openplans.org wrote:
> R-trees are similar to "normal" B-trees, but you search multiple paths
> in the tree simultaneously. At the bottom of the tree (leaf nodes),
> each of the bboxes will "point to" a row in the main table. All the
> bboxes in node are unioned together and that is stored in the node
The fact that each zero size point is represented by a bounding box in
the index explains why the data set size is much bigger than a simple
x-y co-ordinate for points.
If we are only indexing collections of zero size points as opposed to
bounding boxes, would it make sense to hybridise the system by trimming
off the leaf nodes and in the layer above the leaf nodes have a pointer
to a b-tree representation of the points within the bounding box?
Do you know if experiments been carried out using integers instead of
floats in the internal bbox representation? These may have two positive
1) Speed the mathematical comparisons used to determine intersections.
2) All calculations will be exact, without any rounding errors. This
opens the possibility of only representing offsets within the index, in
tiny data types. The index might then be even smaller than the data
More information about the talk