[OSM-talk] RE:

dblasby at openplans.org dblasby at openplans.org
Wed Apr 26 23:58:55 BST 2006


Nick wrote:
>
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.
>

I must admit, I was quite suprised when I saw that you got 2-3* the
performance with integers vs doubles.  I would expect the fact that the
index data is 1/2 the size makes up most of this difference (64bit
doubles vs 32bit ints).  Have you tried double vs float?  I cannot
image that a<b for int32 and float32s is going to make that much of a
difference, but who knows?

Back to Rtree/GiST indexes.  The PostGIS (and the built in postgresql
geometry-types) are indexed by implementing an Rtree in GiST.  The GiST
index (Generalized Index Search Tree) can support "custom" Rtree
implementations.  For example, you could have your actual data in
double precision but index using integers (ie. 10,000,000 * lat/long as
mentioned earlier).  The nice thing is only the person implementing the
Rtree has to know this is being done - they can hide it from anyone
who's actually using the index.  Hardly anyone knows that the postgis
index is based on FLOAT32BOX2D operations because its hidden - they
just know queries like "the_geom && geometry" are quick.

You could make a complex indexing schema with the leaf nodes behaving
differently, but it would makes things more complex.

dave



----------------------------------------------------------
This mail sent through IMP: https://webmail.limegroup.com/




More information about the talk mailing list