Spatial Index Improvement

A spatial index is key to the routing calculations, since it allows us to convert from real-world coordinates to the internal nodes and links of the street network. Many data structures have been developed for spatial indices and for RW Net 4 we have chosen a quad tree, where we are storing a mix of nodes and partial links in the cells. This makes it very fast to generate and query. Storing partial links mean we don’t have to test every section of even very long roads, but can focus on the relevant part (within the grid cell).

Index generation wasn’t as fast as we would like it to be, so we have just improved it with reduced memory foot print and calculation time as a result. Testing it on USA+Canada (35 million links) showed an improvement from 30 min to just 5 min. Loading the spatial index is also faster and uses 25-30% less RAM, while the speed of searches has improved, but no big difference. With typical GPS data a search takes just a couple of msec on the same network.

Below is an example of a spatial index with max 50 nodes in every cell:

This entry was posted in RW Net. Bookmark the permalink.

2 Responses to Spatial Index Improvement

  1. what causes the increase?

  2. Uffe Kousgaard says:

    Deciding when a leave in the tree should be split, is now based upon the number of nodes, rather than the number of vertices in the partial links. That is a lot easier to keep track of and can be done in memory even for the largest networks.

Comments are closed.