On Fri, Oct 17, 2008 at 02:31:26PM +0200, Freek wrote:
See for example this follow-up paper on "Hilbert" R-trees: http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.45.9180
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.
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).Unfortunately not. I suppose once you're dealing with non-constant data, looking at a ready-made database implementation is worth a try. Most ofAlso, 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.the overhead of usual databases will probably come from having to support updates.
CU Sascha -- http://sascha.silbe.org/ http://www.infra-silbe.de/
signature.asc
Description: Digital signature
_______________________________________________ dev mailing list [email protected] http://lists.openstreetmap.org/listinfo/dev
