[OSM-talk] Re:

Nick Hill nick at nickhill.co.uk
Wed Apr 26 18:40:10 BST 2006


Hello David

dblasby at openplans.org wrote:
> Hi,

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

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 
effects;
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 
being indexed.


-Nick.




More information about the talk mailing list