[OSM-dev] on-disk indexing of geodata

[Sascha Silbe]

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.

>> 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.
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).

CU Sascha

-- 
http://sascha.silbe.org/
http://www.infra-silbe.de/
-------------- next part --------------
A non-text attachment was scrubbed...
Name: signature.asc
Type: application/pgp-signature
Size: 481 bytes
Desc: Digital signature
URL: <http://lists.openstreetmap.org/pipermail/dev/attachments/20081017/ebcf3784/attachment.pgp>