What system would calculate a shortest path between Sydney and London? There's an incredible amount of sparseness in the matrix.
OSRM builts a hierarchy that allows fast computation of shortest paths for the whole world map. It takes about 4 hours on my server, fills around 40GB of RAM, and then after that I can magically do insane amounts of shortest path queries.
Paper below has an even faster algorithm that has an operation of finding shortest paths equivalent to just several reads in memory (according to experimental results in the paper, it's roughly equal to 5 reads, meaning it's just 5 times slower than that 1E18 table we'd have). It works on a single workstation.
It might not be a pairwise cache but man, this is some advanced stuff and I'm sure Google's engineers wouldn't think of having 1E18 elements matrix.
That's why I'm a bit surprised by the pricing and the limits. I guess network traffic bandwidth costs.
What system would calculate a shortest path between Sydney and London? There's an incredible amount of sparseness in the matrix.
OSRM builts a hierarchy that allows fast computation of shortest paths for the whole world map. It takes about 4 hours on my server, fills around 40GB of RAM, and then after that I can magically do insane amounts of shortest path queries.
Paper below has an even faster algorithm that has an operation of finding shortest paths equivalent to just several reads in memory (according to experimental results in the paper, it's roughly equal to 5 reads, meaning it's just 5 times slower than that 1E18 table we'd have). It works on a single workstation.
It might not be a pairwise cache but man, this is some advanced stuff and I'm sure Google's engineers wouldn't think of having 1E18 elements matrix.
That's why I'm a bit surprised by the pricing and the limits. I guess network traffic bandwidth costs.
http://research.microsoft.com/apps/pubs/default.aspx?id=1456...