Boost::Geometry R*Tree and Paging/Lazy load?

Question

I tried yesterday the SqLite3 RTree Virtual Table to get one or more "Data" ID's from querying by (WGS) Coordinates. It works very fast! Unfortunatly inserting/building up the rtree was slow (half an hour for Turkey).

Found out that Boost::Geometry library also has a RTree implementation. My question concerning this RTree is: Can I use paging or lazy load with this r*tree? We have big maps and only want to load in id's into the rtree when its queryed by coresponding coordinates. Its like a database that loads in page(s) only when user is requesting for it.

Thanks a lot!

Henry

Answer 1

The Boost.Geometry rtree implementation supports stateful allocators. E.g. it's possible to use it with Boost.Interprocess to store the rtree in shared memory or mapped file.

If you were able to implement an allocator saving/loading nodes to/from files and allowing access to data when a pointer returned by this allocator is dereferenced then it'd work.

However it probably wouldn't be that simple in the case of an allocator loading chunks of data if needed. Loading and accessing the data is straightforward, but the allocator (or manager) would be forced to know when the data is no longer needed and currently there is no way of getting that information directly. It could be possible to obtain it indirectly but the rtree wasn't tested in such case so the official answer to your question is that it's not supported.

I planned to add the support for persistent storage but due to a lack of time didn't do it. If you have some ideas, want to help, etc. I invite you on the mailing list.

EDIT:

Actually it could be done if the stateful allocator was notified about operation finish explicitly by the user, e.g. after an insert was made or per some number of finished inserts or queries. The allocator could still store some usage metric (e.g. as dereferences counter) and do some cacheing but it'd know that some nodes could be removed if needed. I guess it'd be similar to ios flush(). Still it wouldn't work out of the box in the case of packing/bulk-loading which handles elements in a top-down manner. So:

persistent_allocator alloc(/*...*/);
bgi::rtree</*...*/> rt(/*...*/, alloc);
// ...
rt.insert(/*...*/);
rt.insert(/*...*/);
rt.insert(/*...*/);
alloc.flush();