OSRM is a nice project - out of the box. The lead went to some giant - so project is currently a bit stray but there are also some other alternatives on github which work well but might not be as mature as OSRM.
Google caches insane amounts of things.
What one might think is insane algorithms, it's probably just Googles multimillion cluster memory.
Google is also lucky that no one needs the whole matrix, I'm sure that distance matrix is insanely sparse and can be stored in not that large amount of memory.
I understand completely that Google offers these APIs completely for free and they can shut them down easily. I'm willing to pay for more but my quadratic needs aren't met with root pricing.
So, to waste sub-linearly I can easily setup OSRM for my needs :D
Assume there are a billion places on Earth. (As there are ~7B people, each of whom lives in a "place", this is already an underestimate.) If it takes a single byte to store the distance between each of these places, you would need an exabyte of storage just for this single byte.
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.
Nobody stores all shortest paths, that's just silly. With some rather simple preprocessing you can answer shortest paths queries on the US road network in microseconds [1], with preprocessing time of less than a day on a single machine. Surely Google can scale that up to larger graphs.
OSRM is a nice project - out of the box. The lead went to some giant - so project is currently a bit stray but there are also some other alternatives on github which work well but might not be as mature as OSRM.
Google caches insane amounts of things. What one might think is insane algorithms, it's probably just Googles multimillion cluster memory.
Google is also lucky that no one needs the whole matrix, I'm sure that distance matrix is insanely sparse and can be stored in not that large amount of memory.
I understand completely that Google offers these APIs completely for free and they can shut them down easily. I'm willing to pay for more but my quadratic needs aren't met with root pricing.
So, to waste sub-linearly I can easily setup OSRM for my needs :D