How do you suggest to partition QuadTrees?

Oleg666 · July 27, 2020, 2:29pm

Hi

How do you suggest to partition QuadTrees in case of Uber?
In Yelp we used LocationId, but it’s not the case for Uber

Thanks

Ahmed_Ali · January 4, 2020, 4:46pm

Good question, I also want to know the answer since Now the quad tree has two type of info Driver and customer right?
@Design_Gurus please help us on this

kiliman · February 28, 2020, 8:39pm

I believe the QuadTree is partitioned by DriverID. Customers will send their current location, then the service will consult the QuadTree to determine what are the closest drivers to the customer’s location. Those drivers are then notified, and when a driver accepts the request, the driver is sent to the customer.

Because the driver location is constantly updating, they added the driver location cache in front of the QuadTree. It is queried only after a driver accepts the customer request. This way they can track the drivers current location without having to update the QuadTree so frequently. The QuadTree is updated periodically from the cache.