[OSM-dev] on-disk indexing of geodata

[Freek]

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