Introduction to Google Maps

What is Google maps?

Let’s introduce the problem by assuming that we want to travel from one place to another. The possible things that we might want to know are:

• What are the best possible paths that take us to our destination depending on the particular vehicle type.
• How much distance in miles does each path have?
• How much time does each path take us to get to my destination?

A maps application (like Google Maps, Apple Maps, etc.) enables the users to answer all the above questions easily. The following illustration shows the calculated paths by Google maps from the “Los Angeles, USA” to “New York City, USA”.

Why maps service?

Individuals and organizations rely on location data to navigate around the world. Maps help:

• Individuals find the location and directions to the new place quickly instead of roaming here and there wasting their time and the cost of travel such as gas.
• Individuals use maps to see the estimated time of arrival (ETA) and shortest path based on current traffic data.
• Many modern applications heavily rely on maps such as ride-hailing services, autonomous vehicles, and hiking maps. For example:
  • Waymo self-driving car system uses Google maps to navigate efficiently, quickly, and safely.
  • Uber uses Google maps as part of its app to assist drivers and provide customers with a visual representation of their journey.
• Routing and logistics-based companies reduce the time it takes to make deliveries. By using the map’s unique real-time and historical traffic data, it minimizes the overall cost of deliveries by reducing gas usage and time spent stuck in traffic.

In 2022, more than 5 million businesses are using Google maps. It provides an API for enterprises to use a map system in their application.

Requirements

Before we start requirements, let’s clarify that we will design a system like Google maps by picking a few key features (because actual Google maps are feature-rich and complex).

Let’s list the functional and non-functional requirements of the system under design.

Functional requirements

Following are the functional requirements of our system:

• Identify the current location: The users should be able to approximate their current location (latitude/longitude — decimal values) on the world map.
• Recommend the fastest route: Given the source and destination (place name — text), the system should recommend the optimal route with distance and time depending on the type of transportation means.
• Give directions: Once the user has chosen the route, the system should list directions in textual format, where each item in the list guides the user to turn in a specific direction to reach the destination.

Non-functional requirements

Following are the non-functional requirements of our system:

• Availability: The system should be highly available.
• Scalability: It should be scalable because both individuals and other enterprise applications (like Uber, Lyft) use Google maps to find the appropriate routes.
• Less response time: It shouldn’t take more than two or three seconds to calculate the ETAEstimated Time of Arrival and the route, given the source and the destination points.
• Accuracy: The ETA we predict should not deviate too much from the actual travel time.

We are not getting into the details of how we get the roads data. Government agencies provide maps, and in some places, Google itself drives mapping vehicles to find roads and their intersection points. Road networks are modeled with a graph data structure, where intersections points are the vertices and roads between intersections are the weighted edges.

Challenges

Following are some challenges that need to be focused on while designing a system like Google maps.

• ETA computation: In an ideal situation with empty roads, it’s straightforward to compute ETA using the distance and the speed of the vehicle we want to ride on. However, we cannot ignore factors like the amount of traffic on the roads and road conditions that affect the ETA directly. For example, a road under construction, collision, and/or rush hours slow down the traffic. Quantifying the above factors to design our system is not trivial; we will, therefore, categorize the above factors in terms of traffic load to complete our design.

Estimations

Let’s estimate the total number of ...