Hacker News Reader

Comment by corndoge | Hacker News Reader

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.

View on HN

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.

I get incomparable functionality using OSM.

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/...

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 provides a distance matrix 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

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

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.

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=1456...

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

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.

What was your dataset for your reverse geocodes? The GeoNames dataset can't be that accurate, can it?

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.

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/ with a reasonable pricing model for the whole Directions API and specifically for the Matrix API https://github.com/graphhopper/directions-api/blob/master/FA...

(note: I'm the author of GraphHopper)

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.

Reply on news.ycombinator.com