So I am searching for a few addresses on the Google Maps website and I noticed that its results are almost instantaneous! I am not even typing these addresses, just copy-pasting them on the search bar. Then I noticed when I use the google maps app for navigation, it loads so fast and almost every thing on it is real-time like traffic and breakdowns and the rest. Even the direction where it uses the camera to point which direction to go when walking.
How is Google managing to load things this fast? Its mind boggling!
In: 1
Money. Lots and lots of money. A stupid amount of money. Google is absolutely massive and has all the funds they could possibly need to have very powerful servers and pay really smart devs to make really efficient apps. The real-time aspect is also aided by the fact that so many users are on the Google platform; they can use live data from their users to update traffic conditions quite reliably.
Maps is only really limited by your internet speed. All the street data is there, it only has to load it onto your device. Most of the time, the limiting factor will be your bandwidth, because nothing of what Maps does is taxing in other ways.
I dont really see any technical answers here so here is my take.
1) For your search autocomplete: When someone searches something in google, google stores the keyword in a database with a scoring system. The more people search it, the more score it gets.
Now. Fetch these highly searched keywords or sentence and store it in a different database which might be much smaller. Database has a feature called an index. Index basically works just like a dictionary. If you want to look up the meaning of word “zygote”, you dont have to scroll through all the pages, you just have to scroll to the page where words starts with “Z”. That makes searching faster. Ofcourse, they amp up their computing power to supercharge searching.
2) Google maps: There is a data structure called a tree or a graph. Suppose you want to go to the grocery store, in how many ways can you get there? Assume that you can use a street multiple times but you cant use the same route. You could either take left from your house or right. After taking left you could still take a left or a right. Now you have 100 different ways to go to the store. What if you already know a route that majority of the people take? Now you have a route. What if i keep updating you on traffic for these routes. You will take the next best route right? Thats how the maps work.
Your map app basically sends the start point and end point to the google server. The server already knows the most taken path and the traffic because there are people who are using maps at this moment on those routes. Based on this its easy for it to tell you what route to take.
I don’t know how Google Maps’ *specific* search feature is implemented, but it likely uses some variant of locality-sensitive hashing. In short, Google organizes its data in such a way that, when you ask Google Maps to find you some coffee, it can immediately jump to the coffee shops closest to you rather than having to sort through every coffee shop in the world.
You may have heard of regular old garden-variety hashes before. In short, a hash function is a function that converts arbitrary pieces of data (e.g. strings of letters, images, sequences of numbers, whatever) into single numbers. You can use hashes to implement filing systems that allow near-instant lookup without need for search.
Imagine you’re running a hash-based library and a new copy of the book Donutmaking for Dummies arrives. To determine where to shelve this book, you would feed the title into your hash function. It spits out a number, let’s say 9, and that tells you where the book goes: shelf #9. The next day, when a patron asks to check out Donutmaking for Dummies, finding the book is as simple as feeding its title into the hash function again and going to the corresponding shelf.
In this case, the exact workings of this function are not important; all that matters is:
1. the same title goes to the same shelf number every time
2. different titles don’t get mapped to the same shelf number “too often”. If too many titles go to the same shelf, then after finding out which shelf a book is on, you would still have to spend time searching within that shelf for your book. Ideally, you would have lots of shelves with only one book per shelf.
A locality-sensitive hash is a special kind of hash that transforms a set of coordinates (e.g. latitude-longitude pairs) into a single number, but relaxes requirement #2 in a clever way: instead of preventing different coordinates from mapping to the same number, we want different coordinates to map to the same number *only if they are close together in space*.
So let’s say we’re adding shops to Google Maps’ database. For each shop, we feed its coordinates into a locality-sensitive hash and get a number. Shops that are close together receive the same number and therefore go onto the same “shelf”.
When you search for a shop, all Google has to do is hash *your* coordinates. The resulting number will tell Google which shelf to look on, and that shelf will contain only shops near your location.
The really hard thing to do in tech is make something really hard look simple. Search, Google Maps. Amazon do that. This old [Wikipedia ](https://en.m.wikipedia.org/wiki/Google_Maps) is still current.
Latest Answers