I'm developing a transit mapping application for Android. OpenStreetMap in place of the standard Google Maps components has been far easier, much more hackable, more flexible, and overall much more fun to work with than Google's MapView. As an added bonus the libraries for Android (OSMDroid in particular) have total interop with the Google Maps API. It really has been a pleasure to dev against.
I think OSM is an accomplishment on the significance level of Wikipedia and I'm glad it exists.
Android developer here as well. Have found the same. It has saved the day before where the only other option would have been licensing commercial options like skobbler.
I don't think Google actually dog foods their Android Google Maps API, so it tends to be pretty limited.
Google Maps is just too expensive and its pricing model isn't exponential at all, it's not even quadratic.
Very common operation is looking for pairwise distance matrix. Pricing and limits are totally irrational.
100,000 daily limit is totally impossible for an app with 10 users. 100x100 = 10,000 :D
Given that Google probably has all of the distances cached somewhere on their servers, I see no technical reason why this limit can't easily be increased. My app can have millions of shortest paths requests per day, and I certainly do not have Google's infrastructure.
Online geocoding service are always the worst way to go. You only use the online services if you don't have an alternative dataset.
The osm datasets actually aren't that big, the entire PBF formatted dataset is <30GB. You can fit that on any system (not in RAM of course but hard disk access is still a million times quicker than using an online service). There are simple scripts to keep the dataset in sync on your server.
Also it's just completely fucking ridiculous to send a request over the internet to perform a calculation.
I encountered the issue myself ages ago where i had a task to reverse geocode for a railways GPS system for every train every minute. Google and other services would have costed millions of dollars every year, used massive amounts of bandwidth and been waaay too slow. I wrote a library - https://github.com/AReallyGoodName/OfflineReverseGeocode in a day that could easily do millions of lookups each minute.
It's quite reasonable despite being a non-polygonal dataset if all you want is the nearest suburb (this was my use case). They have multiple points for the same ___location so nearest point search works quite well even with weirdly shaped suburbs. I've mucked around with other datasets (there's an OSM branch in my public repo that i'm currently working on to get down to street and street number level) but for the use i mentioned above the geonames works well.
You seem to be talking about the HTTP web service Distance Matrix API, but why would you call that from an app? The JavaScript Distance Matrix API scales to essentially unlimited users for free:
I'm also not aware of OSM offering anything comparable out of the box, although there are some commercial providers who offers similar paid services based on OSM data.
Also, if you think "all of the distances" are cached, I invite you to estimate how many places there are in the world and how big a matrix of every distance from every point to every other point would be.
(Disclaimer: Used to work on Geo at Google. Opinions mine only, etc.)
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.
We often hear that the pricing model is not the only problem. E.g. there are other restrictions like being forced to display the result on a (google) map etc
Also not that you cannot really cache routes, nor could you store all (not even Google) or even just distances or ETAs. But that is also not necessary to get fast and relative 'CPU light' responses.
As I've said somewhere down the thread, OSRM has the same functionality and speed is supreme. Microsoft Research paper I've cited is equivalent to 5 reads of memory and needs about 20GB RAM for the whole Europe. It's a pretty good cache.
I think OSM is an accomplishment on the significance level of Wikipedia and I'm glad it exists.