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
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.
Latest Answers