[OSM-dev] on-disk indexing of geodata
sascha-ml-gis-osm-dev at silbe.org
Fri Oct 17 14:04:35 BST 2008
On Fri, Oct 17, 2008 at 02:31:26PM +0200, Freek wrote:
> See for example this follow-up paper on "Hilbert" R-trees:
Interesting paper. Thanks for the pointer!
> The whole point of R-trees is that they are efficient when stored in
> external memory. In the case of Hilbert R-trees, bulk-loading is
> particularly easy because you can just use an external-memory sorting
> algorithm to sort your input data along a space-filling curve, store
> consecutive sets of input-item bounding boxes in the leaves of the
> tree, and build the rest of the tree bottom-up.
That's exactly what I do. And since everything is constant, the R-Tree
node addresses are constant, too => no need for "pointers", very
efficient on-disk storage format.
>> Unfortunately not. I suppose once you're dealing with non-constant
>> looking at a ready-made database implementation is worth a try. Most
>> the overhead of usual databases will probably come from having to
>> support updates.
> Also, they often use (as far as I can tell) the original R-tree
> algorithm by Guttman from 1984. In the meantime more efficient
> algorithms have been developed, the Hilbert R-tree being a
> particularly practical and quite efficient one.
Actually it seems I've been limited in view by my own application. The
problem I'd have with updating data isn't how to map data updates to
tree updates (the topic covered by the paper mentioned above) but how to
efficiently do inserts and deletes on an on-disk tree. I haven't done
any research on that topic, though, since I don't need it yet (bulk
imports are quite fast - ~25 minutes for the 865MB europe.osm.bz2).
-------------- next part --------------
A non-text attachment was scrubbed...
Size: 481 bytes
Desc: Digital signature
More information about the dev