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:
what causes the increase?
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.