3 ms·

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 distan

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. I get incomparable functionality using OSM.

jpatokal 11y ago
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: https://developers.google.com/maps/documentation/javascript/distancematrix https://developers.google.com/maps/documentation/javascript/... 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.)
- sp8962 11y ago
  OSRM provides a distance matrix API https://github.com/Project-OSRM/osrm-backend/wiki/Server-api https://github.com/Project-OSRM/osrm-backend/wiki/Server-api ("table"). All open source, if you don't want to run it yourself, you can turn to a commercial service provider, see switch2osm.org
- skimpycompiler 11y ago
  It's a mobile app primarily. 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
  - jpatokal 11y ago
    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.
    - skimpycompiler 11y ago
      You are really arguing that? 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=145689 http://research.microsoft.com/apps/pubs/default.aspx?id=1456...
    - adrianN 11y ago
      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. [1]http://people.mpi-inf.mpg.de/~dmatijev/papers/DIMACS06.pdf http://people.mpi-inf.mpg.de/~dmatijev/papers/DIMACS06.pdf
AReallyGoodName 11y ago
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 https://github.com/AReallyGoodName/OfflineReverseGeocode in a day that could easily do millions of lookups each minute.
- voltagex_ 11y ago
  What was your dataset for your reverse geocodes? The GeoNames dataset can't be that accurate, can it?
  - AReallyGoodName 11y ago
    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.
karussell 11y ago
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. > I get incomparable functionality using OSM. Have a look at https://graphhopper.com/ https://graphhopper.com/ with a reasonable pricing model for the whole Directions API and specifically for the Matrix API https://github.com/graphhopper/directions-api/blob/master/FAQ.md#what-is-one-credit https://github.com/graphhopper/directions-api/blob/master/FA... (note: I'm the author of GraphHopper)
- skimpycompiler 11y ago
  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. OSS is eating the world of geo.

jpatokal 11y ago

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: https://developers.google.com/maps/documentation/javascript/distancematrix https://developers.google.com/maps/documentation/javascript/... 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.)

sp8962 11y ago
OSRM provides a distance matrix API https://github.com/Project-OSRM/osrm-backend/wiki/Server-api https://github.com/Project-OSRM/osrm-backend/wiki/Server-api ("table"). All open source, if you don't want to run it yourself, you can turn to a commercial service provider, see switch2osm.org
skimpycompiler 11y ago
It's a mobile app primarily. 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
- jpatokal 11y ago
  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.
  - skimpycompiler 11y ago
    You are really arguing that? 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=145689 http://research.microsoft.com/apps/pubs/default.aspx?id=1456...
  - adrianN 11y ago
    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. [1]http://people.mpi-inf.mpg.de/~dmatijev/papers/DIMACS06.pdf http://people.mpi-inf.mpg.de/~dmatijev/papers/DIMACS06.pdf

AReallyGoodName 11y ago

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 https://github.com/AReallyGoodName/OfflineReverseGeocode in a day that could easily do millions of lookups each minute.

voltagex_ 11y ago
What was your dataset for your reverse geocodes? The GeoNames dataset can't be that accurate, can it?
- AReallyGoodName 11y ago
  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.

karussell 11y ago

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. > I get incomparable functionality using OSM. Have a look at https://graphhopper.com/ https://graphhopper.com/ with a reasonable pricing model for the whole Directions API and specifically for the Matrix API https://github.com/graphhopper/directions-api/blob/master/FAQ.md#what-is-one-credit https://github.com/graphhopper/directions-api/blob/master/FA... (note: I'm the author of GraphHopper)

skimpycompiler 11y ago
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. OSS is eating the world of geo.