Optimization question about h3-js HOT 3 CLOSED

So Uber didn't have H3 for a long time after it started. At first it was pretty simple: shard based on political boundaries (city/county/etc) where the pricing differs and keep all of the drivers indexed by that (there weren't really that many). Then take the rider's lat, lng and the drivers' lat, lng values, subtract them to get the delta-lat and delta-lng for each, multiply the delta-latitude by a constant based on one of the latitudes to roughly "square up" versus the longitude to avoid distance distortion (or just ignore it at first if you're relatively close to the equator, it only matters very far north), and then square the deltas and add them together, then sort the drivers by this ranking and you have them by distance from the rider.
With a small number of drivers, doing this in a tight loop is more efficient than any database-driven indexing approach. When you have a ton of potential riders and drivers you can do something trickier, but for Uber-style dispatching, the right next move isn't going to H3, it's using OSRM to calculate ETAs from the drivers to the rider and sorting by that, so you don't accidentally dispatch drivers across a river with few bridges.
Once OSRM is showing some signs of strain would you introduce something like S2 or H3 to do rough bucketing like you've described, but then you just feed that subset of drivers to OSRM because distance "as the crow flies" is not the best approach when cars don't fly.
In conclusion, for actual Uber-style dispatching, H3 is the last kind of micro-optimization you might need when you have a ridiculous volume of requests.

Thank you A LOT! I was in this dilema hahaha, because I currently plan to have +5000 drivers and the database will be slow when comparing distances between all those drivers. That's why I wondered in those two approaches and then calculate, as you said, the route with OSRM to determine the best driver.

Thank you!!

No problem. I would also recommend keeping just the driver location data in a fast, simple nosql DB like Redis with their ids grouped by whatever basic sharing strategy you have. It's basically ephemeral data so no point in slamming your main DB that probably persists all updates to disk and killing its performance.

from h3-js.

So Uber didn't have H3 for a long time after it started. At first it was pretty simple: shard based on political boundaries (city/county/etc) where the pricing differs and keep all of the drivers indexed by that (there weren't really that many). Then take the rider's lat, lng and the drivers' lat, lng values, subtract them to get the delta-lat and delta-lng for each, multiply the delta-latitude by a constant based on one of the latitudes to roughly "square up" versus the longitude to avoid distance distortion (or just ignore it at first if you're relatively close to the equator, it only matters very far north), and then square the deltas and add them together, then sort the drivers by this ranking and you have them by distance from the rider.

With a small number of drivers, doing this in a tight loop is more efficient than any database-driven indexing approach. When you have a ton of potential riders and drivers you can do something trickier, but for Uber-style dispatching, the right next move isn't going to H3, it's using OSRM to calculate ETAs from the drivers to the rider and sorting by that, so you don't accidentally dispatch drivers across a river with few bridges.

Once OSRM is showing some signs of strain would you introduce something like S2 or H3 to do rough bucketing like you've described, but then you just feed that subset of drivers to OSRM because distance "as the crow flies" is not the best approach when cars don't fly.

In conclusion, for actual Uber-style dispatching, H3 is the last kind of micro-optimization you might need when you have a ridiculous volume of requests.

from h3-js.

So Uber didn't have H3 for a long time after it started. At first it was pretty simple: shard based on political boundaries (city/county/etc) where the pricing differs and keep all of the drivers indexed by that (there weren't really that many). Then take the rider's lat, lng and the drivers' lat, lng values, subtract them to get the delta-lat and delta-lng for each, multiply the delta-latitude by a constant based on one of the latitudes to roughly "square up" versus the longitude to avoid distance distortion (or just ignore it at first if you're relatively close to the equator, it only matters very far north), and then square the deltas and add them together, then sort the drivers by this ranking and you have them by distance from the rider.

With a small number of drivers, doing this in a tight loop is more efficient than any database-driven indexing approach. When you have a ton of potential riders and drivers you can do something trickier, but for Uber-style dispatching, the right next move isn't going to H3, it's using OSRM to calculate ETAs from the drivers to the rider and sorting by that, so you don't accidentally dispatch drivers across a river with few bridges.

Once OSRM is showing some signs of strain would you introduce something like S2 or H3 to do rough bucketing like you've described, but then you just feed that subset of drivers to OSRM because distance "as the crow flies" is not the best approach when cars don't fly.

In conclusion, for actual Uber-style dispatching, H3 is the last kind of micro-optimization you might need when you have a ridiculous volume of requests.

Thank you A LOT! I was in this dilema hahaha, because I currently plan to have +5000 drivers and the database will be slow when comparing distances between all those drivers. That's why I wondered in those two approaches and then calculate, as you said, the route with OSRM to determine the best driver.

Thank you!!

from h3-js.