How much storage space do you need for Google Maps?

My approach to this Google estimation question would be as follows.

Answer:

• Clarify

  • Which version of Google Maps do you want me to go first? (Map or Satellite) => Map

  • You mean Google Map for a specific region or around the globe? => Around the globe

• To estimate the space we need for Google Maps I will use this formula

Total = Background + Information of each place in Google Maps

1. Background

• Surface area ~ 5x10^8 km2  

• Could you tell me how much space for storing one km2 background in average?=> 100 Mb (not sure) 

• We have to spend 50 TB to store background of Map

2. Place

• There are different kinds of places Google Maps stores including:

1. 1. Street names

• [# of cities] x [streets/city] x [storage/street]

• I will assume that there are 1000 streets in a big city (NYC) 

• We need to save the text of each street, so I think 10MB is a suitable space for each street

• Because there are ~ 8 million people in NYC and there are 8 billion around the world => I will assume that all of the cities in the world will look like 1000 cities like NYC.

• Therefore, the space storing streets is 1000 x 1000 x 10MB = 10TB

1. 2. Transportation

• As I see, Google Maps also has information about some public transportation like bus, MRT, …

• [# of cities] x ([bus station/city]x[storage/bus station] + [MRT station/city]x[storage/MRT station])

• We have 1000 streets in each city, so I will assume that one station covers 10 streets => There are 100 bus stations and 100 MRT stations in each city.

• I’m not so sure of the storage/bus station. But I think we have to store the schedule, photo, announcement, … So I will assume that we need 1GB per each station

• Therefore, the space storing transportation is 1000 x (100x1GB + 100x1GB) = 100TB

1. 3. Business

• I mean restaurants, coffee shops, gas stations, ….

• [# of cities] x [# of business/city] x [storage/business]

• I think that in one street there are around 200 business => there are 200,000 business in a city

• Because for each business, we have to store the text information including operation hour, business’s description, users’ feedback, et al. I assume that we need 10Mb to store all the text information of each place

• On the other hand, Google Maps also stores images, so I will assume that there are 50 images per business in avg and the size of each img is around 1Mb.

• Therefore, the space storing business would be 1000 x 200,000 x (50+10)MB = 12PB

1. 4. Tourist Attraction

• I separate the tourist attraction and business because in tourist attraction the number of photos and feedback is much higher than business. But the number of tourist attraction in each city would be significant lower than the figure for business

• I will assume that there are 100 Tourist Attractions in each big city

• There is nearly 100,000 feedback in each tourist attraction and each feedback has 5 photos and 1Mb text => 500Gb for images and 100Gb for text in each place

• Therefore, the space storing business would be 1000x100 x 600Gb = 60Pb

The total = 50TB + 10TB + 100TB + 12PB + 60PB ~ 72,2 PB

Google holds about 15 EB per year, so I think that 72,2 PB for Google Maps is not unreasonable.

Confirm with Interviewer your understanding of the product

Google maps is an mobile app and desktop site with following capabilities

• world map w/ different zoom levels
• turn by turn directions
• satellite view
• birds eye view
• map data and vareity of other features

Clarifying questions

• Should we focus on just the world map w/ different zoom levels? Yes
• Current google maps use vector data instead of image tiles. The client draws the maps based on the vector data. Should we assume for this excercise that we are still using image tiles? Yes 

That's good to start. Ask clarifying questions throughout or state assumptions.

Equation

Things we know - 

• Maps are shown as a tiles. Users can scroll through them up/down, left/right and new tiles are loaded. 
• Each zoom level adds a new level of detail to the tile. The tile size itself doesn't change but the number of tiles increase at each zoom level to accomodate the details.
• At each zoom level, each tile will have map meta data (labels on the maps). The data size will vary with different zoom levels.

Given that, the equation is

# of zoom levels * # tiles / zoom level x [(avg size of the tile / zoom level) + (meta data for each tile / zoom level)] 

Lets start with the average tile size. What do we know - each tile is of size 256 * 256 pixels (confirm with the interviewer but this is a well known number). Lets also assume the bit depth for an image is 8bit (maps don't need more than 256 colors). Given that, we can calculate the size of a tile, (the equation below is just a standard image size calculation based on width, height and depth). You can also make assumption (size cannot be greater than 100kb and can't be less than 1kb).

size of the tile = (((w * h) * bit depth) / 8 ) / 1024 kilo bytes => ( (256 * 256 * 8 ) / 8 ) / 1024 => 64 kb

Note that the zoom level increase the details of a map by creating more tiles but the size of the tile remains the same. Now lets focus on label data. We can assume that label data cannot be bigger than 64kb and cannot be less than 1kb. Label data is probably stored as json data, so it is plain text. We can assume that per tile between of 5kb to 10kb (note that label data will vary at zoom level. World zoom level will have lot less data than at city / block label data). 

size of the tile  = 64kb (tile image size) + 11kb = 75kb (adjusted number for easier calculation)

Lets now focus on the # of tiles per zoom. We know that number of tiles are much higher at highest zoom level. We also know that at there are upto 21 zoom levels (open maps and zoom out all the way to earth and then zoom in untile you reach at street level. Notice you can do it about 20/21 times). We also know that at zoom level 0, we only see 2 tiles (divided by the equator). At zoom level 1, this doubles to 4 tiles. At zoom 2, it doubles again to 16 tiles. At zoom 3, it doubles to 64 tiles. (you can check this in browser easily).

So, we can find the number of tiles at any zoom level as ,

2 ^ (2 * zoom level)

zoom level 2 = 2 ^ (2 * 2) = 16 tiles

zoom level 5 = 2 ^ (2 * 5) = 1024 tiles

zoom level 15 = 2 ^ (2 * 15) = 1,073,741,824 tiles

zoom level 21 = 2 ^ (2 * 21) = 4,398,046,511,104 tiles (wow! 4 trillion tiles)

We can apply 80/20 principle and approx to 4.5 trillon tiles. So the total size required to store tiles at different zoom levels

= 4.5 T * 75 kb = ~ 300 T kb => 3 * 10^14 kb  or 300 pb (peta bytes)

Total size required to hold images of earth at different zoom levels is 300 peta bytes. 

Given the population is 7B, we can assume people live in:

• Large cities (10%) = 700M
• Town/small cities (20%) = 1.5B
• Rural/villages (70%) = 5B

• For large cities - we can assume that - people live in apartments and on avg 10 households per apartment = 20M buildings
• For town/cities - we can assume that - peole live in townhomes (avg 3 per home) = 200M homes
• For rural/villages - assume 1 household per home = 2B homes

• Assuming homes (with pictures, metadata, etc..) is 100Kb per home = 200TB
• Assuming business have more metadata (reviews, more pics, open hours, etc...) is 200kb = 40TB

• We assume a grid (square in the middle) and 4 streets around
• For large cities:
  • 20M x 4 streets x (1mb for images, street view, etc..) = 80TB
• For small cities/towns
  • 200M x 4 streets x (100kb as less images, metadata, etc..) = 80TB
• For rural areas
  • 2B x 4 streets x (10kb as no street view only basic metadata) = 80TB
• Total storage for roads = 240TB

• Google Maps refer to Google Satellite Maps
• No user-uploaded images considered
• Only the raw version of Google Satellite Maps
• Entire Earth is covered on Google Maps uniformly

Since, it's related to the entire Earth, we should start by calculating the total area of the Earth

Earth's radius = 6400 km (assuming Earth to be circular)

Total Area of the Earth = pi x radius x radius = 22/7 x 6400 x 6400 = 3.14 x 40,000,000 = 120 M sq. km

# Coverage of one image

Google Maps shows any area in a detailed manner. It means if we capture from a camera covering a particular house, we have to capture it closely. 

Assuming one image covers 100 sq. m to maintain the same level of detail as that of Google Maps.

#Total Number of Images = Total Area of the Earth / Area covered per Image

#Total Number of Images = 120 x 10^6 x 10^6 sq. m / 100 sq. m = 1.2 x 10^12 images

Approx. 75% of area is covered with water

Assume the rest 25% is land area

Assuming Image size on the land area is captured in higher resolution than that of the sea/ocean area

Image size on land area = 10MB

Image size on water area  = 5 MB

Average Image Size = 0.25 x 10 + 0.75 x 5 = ~ 6 MB

Usually we have almost 15 zoom levels.

#No. of Resolutions = 15