choice of parameters for R* Tree using SpatialIndex library

Question

I am using the spatialindex library from http://libspatialindex.github.com/

I am creating an R* tree in the main memory:

size_t capacity = 10;
bool bWriteThrough = false;
fileInMem = StorageManager
    ::createNewRandomEvictionsBuffer(*memStorage, capacity, bWriteThrough);

double fillFactor = 0.7;
size_t indexCapacity = 10;
size_t leafCapacity = 10;
size_t dimension = 2;
RTree::RTreeVariant rv = RTree::RV_RSTAR;
tree = RTree::createNewRTree(*fileInMem, fillFactor, indexCapacity,
   leafCapacity, dimension, rv, indexIdentifier);

Then I am inserting a large number of bounding boxes, currently some 2.5M (road network of Bavaria in Germany). Later I'll aim at inserting all roads of Europe.

What are good choice of parameters for the storage manager and rtree? Mostly I am using the rtree to find the closest roads to a given query (bbox intersection).

Answer 1

As your data is static, a good bulk load may work for you. The most popular (and a rather simple) bluk load is Sort-Tile-Recursive. However, it is somewhat designed around point data. As you are inserting spatial objects, it may or may not work as well.

If you are using a bulk load, it will no longer be an R*-tree, but a plain R-tree.

Capacity 10 sounds way too little to me. You want a much larger fan-out. But you'll need to benchmark, this is data set and query dependant what is good. I'd definitely try 100 or more.