On Friday 17 October 2008, Sascha Silbe wrote: > On Fri, Oct 17, 2008 at 11:30:07AM +0200, Marcus Wolschon wrote: > > Do you have any Idea how such an index can be constructed, given that > > * the indexed dataset is mutable
See for example this follow-up paper on "Hilbert" R-trees: http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.45.9180 > > * At no time can the complete index be loaded into memory (e.g. for > > rebuilding the index). 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. > Unfortunately not. I suppose once you're dealing with non-constant data, > looking at a ready-made database implementation is worth a try. Most of > 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. -- Freek _______________________________________________ dev mailing list [email protected] http://lists.openstreetmap.org/listinfo/dev
