0

I have created a main memory R* index with the help of spatialindex library in the following way (DBStream implements the interface for bulkLoading)

// creating a main memory RTree
memStorage = StorageManager::createNewMemoryStorageManager();

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

DBStream dstream(streets);

tree = RTree::createAndBulkLoadNewRTree(SpatialIndex::RTree::BLM_STR, dstream,
   *fileInMem,
   fillFactor, indexCapacity,
   leafCapacity, dimension, rv, indexIdentifier);

My data is read-only, i.e., I want to build the tree only once, save it, and reload from persistent storage every time I use my program. Clearly, I can save and load the memStorage myself, but how to recreate the RTree from it?

Richard
  • 56,349
  • 34
  • 180
  • 251
arthur
  • 1,034
  • 2
  • 17
  • 31

2 Answers2

1

Since you are bulk-loading the tree anyway, there is little to gain here, actually. All that a STR bulk load does is sort the data. This is O(n log n) theoretically, but if you have the data sorted appropriately it will actually be in O(n) with most sorting implementations.

So most likely, serializing the tree into a file and back is not much cheaper than bulk-loading it again each time. It does take away some flexibility though.

R-Trees in general are meant for dynamic data IMHO. Sure, they do work for static data. But their key strength (opposed to other structures) is that the tree supports balancing on insert.

Has QUIT--Anony-Mousse
  • 76,138
  • 12
  • 138
  • 194
  • That's an interesting observation. I am bulkloading the tree by reading the data from the Database. Since it is a select *, therefore the database overhead might be not that signnificant. I'll try to compare the numbers and post them here.. – arthur Nov 05 '12 at 14:42
0

After extensive research I must conclude that it is possible to save the MainMemoryStorage object but it is impossible to load it. Saving the object is possible through a derived class, that keeps track of all used page IDs (and later saving them to the file). Loading these pages is very problematic as one needs a direct access to

std::vector<Entry*> m_buffer;
std::stack<id_type> m_emptyPages;

from MemoryStorageManager.h. These guys are private, and the MemoryStorageManager.h is not available as this is a private include available only to spatiallibrary.

What a depressing answer.

arthur
  • 1,034
  • 2
  • 17
  • 31