educative.io

Educative

Why using quad tree at all instead of the Google Places API

Can somebody explain why quad trees are needed here? I understand their use with Yelp. However, why is it necessary to use such a convoluted algo when a system like Google Places will take two sets of GPS coordinates and compute the approximate distance and ETA pretty accurately? It appears to me that given the client’s GPS coords or address and the GPS coords of all drivers in a given city, it should not be slow to determine which ones are within a given radius of the customer. In fact, I could see an algo that pings taxis periodically to obtain their coords so you don’t have to do on demand.

Actually, if you ignore ETA, and all you want is distance between two sets of GPS coordinates, you can actually compute the geodesic distance very easily assuming the earth is a perfect sphere.

Let me be more precise. If the taxi drivers in a city are T_i for i 1 through n and the customer is a C, you can call the Google Places API to compute each of the distances distance(T_i, C). This does not seem much slower than taken each of the T_i and figuring out which node in the quad tree is T_i in and the selecting only those that are in certain nodes surrounding the client. Off the top of my head, I don’t see much advantage in using the quad tree. Moreover, you have update the link list in the leaves of the quad tree when a T_i crosses from one tree leave to another.

Am I missing anything here?

1 Like

+1. It will be good to know if there is a reason why quad tree is being used?

Also, I am not seeing uniform pattern for capacity estimation and it adds confusion as to what level of estimations should we make during short interview calls. It will be great to bring a pattern as that will structure the learnings.

@Pablo_Perez i am also not sure why QuadTree is used, but i think the point author is trying here to make us understand an underlying datastructure that supports such an operation.

Ofcourse google maps API and all makes very easy to hit and get an answer, but i think point is to go beyond it and see how can even a google maps API is able to achieve this.

Now i am not saying google maps uses Quadtree as such, but quadtree is a standard technique for querying spatial data in many spatial databases.

Moreover, if the interviewer does asks this question and you come up with an answer which involves a name of third party name such as google API, he may be curious to know how that’s implemented internally.

Maybe by explaining a quadTree, we can at least tell a sensible raw way to implement it.

1 Like

I would go with Redis Geospatial (Geospatial | Redis)