How We reduced our Google Maps API cost • Hacker News Board

Re: How We reduced our Google Maps API cost

#31

Post by Doctor_Fegg » Sat, Apr 04, 2020, 9:01 AM UTC

fulafel wrote: post #15

Doctor_Fegg wrote: post #8

Earlier quoted context omitted.

PSA: Open Source Routing Machine (OSRM) was largely abandoned by its maintainers. Several of us are working to reboot it, so if you enjoy map data and/or graph theory and have C++ skills, this would be a great project to work on. https://github.com/Project-OSRM/osrm-backend/ (Reboot discussion at https://github.com/Project-OSRM/osrm-backend/issues/5209 )

That issue links to another open source routing engine for OSM (Valhalla) that is actively developed, what are the strengths of each?

OSRM is astonishingly fast (it uses the Contraction Hierarchies routing algorithm, or alternatively Multi-Level Dijkstra). This is compelling for draggable routing UIs, and for large matrix calculations used in the Vehicle Routing Problem (Travelling Salesman). It also makes it easy to customise your routing weightings through Lua 'profile' scripts.

The principal downside is that the routing graph takes a lot of time and memory to prepare; runtime RAM usage is also high, though not so much. I think there's some potential for reducing its memory footprint.

Valhalla builds on the older A* algorithm, so it's not so fast (or memory-hungry), though it does make some use of hierarchies to shorten query time. Graphhopper is another, featureful routing engine designed for use with OSM data (written in Java).

Re: How We reduced our Google Maps API cost

#32

Post by DeathArrow » Sat, Apr 04, 2020, 9:02 AM UTC

samcheng wrote: post #4

sudhirj wrote: post #3

Earlier quoted context omitted.

I think real time traffic awareness is exactly what the poster wanted, but yeah it seems like people who don’t need that would be better off using OSS where possible.

Yeah, unfortunately I'm not aware of any open/free sources of real-time traffic data.

Maybe there is the opportunity for someone starting an open source solution to provide real time traffic data.

Until now there wasn't a need since Google provided the data for free.

But everything changed and I bet there are lots of people who need the data but can't afford paying Google.

The only question is how you gather the data since you don't have Google maps and Waze?

You can try to provide a Waze alternative, but how would you convince people to use it?

Re: How We reduced our Google Maps API cost

#33

Post by remus » Sat, Apr 04, 2020, 9:02 AM UTC

austurist wrote: post #9

It is a proof of that Google API is overpriced. Google apparently sells something, that can be computed as well.

That's a pretty cynical interpretation. To me it seems more like they took an easy engineering approach when the cost per API call was low, then when the price went up they re-designed their software to use API calls more frugally by using some domain specific knowledge (that google couldn't know about so wouldn't be able to build in to their pricing).

Re: How We reduced our Google Maps API cost

#34

Post by thelastbender12 » Sat, Apr 04, 2020, 9:05 AM UTC

DeathArrow wrote: post #26

thelastbender12 wrote: post #23

This is a pretty nifty solution! To nitpick, I'm curious how much the ETA between successive stops fluctuates. For example, if you have 2 buses on the route `A-B-C-D-E-F-G-H`, using the same value of T(F-H) for the bus starting off at A and another one already at D, might not be quite right?

They said in the article they sample the time as frequently they deem necessary.

Hmm, could you please expand? What I'm trying to get at is that the Bus at D and the bus at A expect to reach stop F at different times. So, the ETA between F and H is never quite the same for them, as the traffic conditions could change.

When google maps gives me an ETA, I assume they account for it (or their ML model does from the vast troves of past data).

Re: How We reduced our Google Maps API cost

#35

Post by DeathArrow » Sat, Apr 04, 2020, 9:06 AM UTC

kijin wrote: post #6

Since they have actual vehicles on the ground, they could collect data on actual travel times under various traffic conditions and apply a bit of ML to predict how long it's going to take under current conditions. No need for any Google API there. But now that their Google bill is only ~$50/day, it might not be worth building their own prediction system.

If ML could predict everything with accuracy, they would be better by predicting lottery, stock prices or Forex pairs.

I used an app which predicts public transportation arrival time based on historic data and it mistakes most often than not, sometimes by a lot.

Re: How We reduced our Google Maps API cost

#36

Post by mehrdadn » Sat, Apr 04, 2020, 9:06 AM UTC

boojing wrote: post #27

lrem wrote: post #17

Earlier quoted context omitted.

Placement of the cache definitely matters, even more so if you can take advantage of the more specific data freshness requirements. Disclaimer: I work in Google. But I also worked a bit on effects of cache placement in my PhD.

Why is the fact that you work at Google and have researched caching for your PhD a disclaimer? I fail to see how it denies your previous statement

People say "disclaimer" when they mean "disclosure" for some reason.

Re: How We reduced our Google Maps API cost

#37

Post by Reason077 » Sat, Apr 04, 2020, 9:07 AM UTC

rkda wrote: post #25

Author mentioned OSM but they could also use Mapbox's navigation APIs if they don't want to host things themselves. https://www.mapbox.com/navigation/

It would certainly be interesting if they had compared the quality of Mapbox’s traffic data to Google’s. Perhaps the authors tried this and the data wasn’t as good? But it’s not mentioned.

OpenStreetMap itself is just the base map, not a provider of traffic data or routing.

Re: How We reduced our Google Maps API cost

#38

Post by disillusioned » Sat, Apr 04, 2020, 9:10 AM UTC

bad_user wrote: post #29

DeathArrow wrote: post #24

Earlier quoted context omitted.

It's not clever, it's just much more simpler. Using linear interpolation for the time between 2 stops will have low accuracy because for the particular situation time might not be linear with position and distance. Also traffic incidents might happen. Going with a pool of free keys will be much more dependable, even if somehow more complicated to manage and easier to break.

It's probably against their ToS and Google could detect it and ban all of those accounts, or the servers' IPs. You can then keep fooling them by creating new accounts or changing IPs (assuming your usage doesn't have clear patterns they could look at). But such events would be clearly disruptive for the business. Works for a POC, but if your business has actual customers, it's a terrible solution.

This company was shockingly deep into their lifecycle to still be using this approach. And yeah, they'd cycle IPs as needed too. I think the thought was that Google isn't doing a ton of fraud analysis for this particular modality of fraud. Still though...

Re: How We reduced our Google Maps API cost

#39

Post by karussell » Sat, Apr 04, 2020, 9:11 AM UTC

samcheng wrote: post #4

sudhirj wrote: post #3

Earlier quoted context omitted.

I think real time traffic awareness is exactly what the poster wanted, but yeah it seems like people who don’t need that would be better off using OSS where possible.

Yeah, unfortunately I'm not aware of any open/free sources of real-time traffic data.

Here is a collection I started some time ago: https://github.com/graphhopper/open-traffic-collection

Re: How We reduced our Google Maps API cost

#40

Post by DeathArrow » Sat, Apr 04, 2020, 9:11 AM UTC

thelastbender12 wrote: post #34

DeathArrow wrote: post #26

Earlier quoted context omitted.

They said in the article they sample the time as frequently they deem necessary.

Hmm, could you please expand? What I'm trying to get at is that the Bus at D and the bus at A expect to reach stop F at different times. So, the ETA between F and H is never quite the same for them, as the traffic conditions could change. When google maps gives me an ETA, I assume they account for it (or their ML model does from the vast troves of past data).

I get they compare the prediction from maps with actual time for a few stops / busses and if the difference is big they make a new API request, making Google wealthier.