Building an Online Taxi App Like Uber With Golang — Part 1, Nearby Taxis | by Mohammad Hoseini Rad | MediumSitemapOpen in appSign up<br>Sign in

Medium Logo

Get app<br>Write

Search

Sign up<br>Sign in

Building an Online Taxi App Like Uber With Golang — Part 1, Nearby Taxis

Mohammad Hoseini Rad

9 min read·<br>Mar 20, 2023

Listen

Share

Well, I’ve always wanted to write a series of articles in which I talk about Golang and other technologies and build an application together. Some of the most challenging applications are those that require real-time (or almost real-time) locations of some point of interest (POI). Points of interest may be users of dating apps, taxis for online taxis, or even shops in your new project. However, these techniques we talk about can be used to satisfy the geospatial needs of any application.<br>How to find the nearby points of interest?<br>ٌHow does the application finds nearby drivers when you want to take an uber? All we have is some latitudes and longitudes, which are changing in real-time. If we saved all of the locations in an array and we wanted some nearby POIs, we would have checked the distance between the given location and other POIs, and it would have wasted almost all the resources we have, and after a couple of thousand users, the application would be unusable. Thus we must think about a new approach to index and search faster among all nearby POIs.<br>Imagine we want a taxi in an old-school way. What would we do? We look around and see multiple options, and then we take one of those. We can translate this approach to a computer algorithm. First of all, How far can we see? It depends on the application. If we are looking for a match in a dating app, we can see around 10km! But when we are looking for a taxi, taxis less than a kilometer away are acceptable. How about a restaurant? I think all within a 5km range are suitable. Then, after we figured out a list of candidate POIs, we can score them and sort them however we need. For example, we need to sort users by relevancy in a dating app.<br>Press enter or click to view image in full size

Imagine that cute little boy is me trying to find a taxi. How can we figure out the nearby taxis? Regarding what we just said, we need an algorithm to exclude irrelevant taxis. How about I split the map into four zones? Let’s see how it turns out.<br>Press enter or click to view image in full size

As you can see, we just need to consider the taxis in zone0. Although we are filtering far-away taxis, there are still some far taxis in zone 0. Let’s split zone 0 into four new zones.<br>Press enter or click to view image in full size

When we want to split a zone into four new ones, we use the identifier of the zone as a prefix, and we append the new identifier at the end of it. For example, we already had zone0 and wanted to split it into four new zones. Thus the identifiers were zone00, zone01, zone02, and zone03. As you can see, we have better options. However, there are still some distant taxis. Therefore, we split zone03 into zone030, zone031, zone032, and zone033.<br>Press enter or click to view image in full size

Everything is great now. All taxis in zone030 are within a reasonable distance from the client. The width of Tehran is around 50km. However, with three repetitions, we restricted our options to a 6.25km wide rectangle. What if we did it three times more? With five repetitions, we would have had a 781 meters wide rectangle! It’s the beauty of logarithmic algorithms.<br>Now, we need the formula to calculate the zone of the given location. In a better word, we need a hash function to convert a pair of latitudes and longitudes to a valid ID like Zone031. We already have it! GeoHash!<br>GeoHash!<br>Geo hash is simply what we’ve already done, but for the earth’s entire surface, instead of only one city. You can try it on this website. Give it some latitudes and longitudes and you will see the converted value is a string with 12 characters or less. Each character increases the precision of the point. But how much does the precision change for each character?<br>Press enter or click to view image in full size

As you can see, with more than ten characters, we reach the sub-meter realm! When we look for a taxi, we need around 1km wide rectangle. Thus, we can find taxis with the same prefix as my current location’s GeoHash, with a precision of six characters. What if we used it for a dating app? We would have used four characters for the precision.<br>Let’s implement a simple package to do this lookup for us.<br>Trie is a suitable data structure for this problem, But we need to change it slightly. How does Trie work? Imagine we have a list of words and want to check if that list contains some words frequently. If we used a simple array to store those words and search within that array, the algorithm’s time complexity would have been N, in which N is the array member’s count. N is not that bad when it is the final complexity. However, we want to use this lookup in other...