How I Shortened Aviation Maps URLs by 75% (Using Information Theory)

[!WARNING] NERD ALERT!! This write-up requires deep technical knowledge to follow. Don’t want to read? Scroll through the pretty pictures instead :)

One of the coolest features we have at Aviation Maps is the ability for customers to completely customize the exact style and zoom level of their maps. This information needs to be relayed back to us somehow, and the way I decided to do so when I first designed the website was to simply throw all the options to the end of the URL, giving us this:

https://aviation-maps.com/etsy?bounds=%7B%22sw%22%3A%7B%22lat%22%3A32.51177440448512%2C%22lng%22%3A-117.3310206318627%7D%2C%22ne%22%3A%7B%22lat%22%3A33.09228566324369%2C%22lng%22%3A-116.79734413813729%7D%7D&frameColor=black&isHorizontal=false&airports=KSDM%2CKSAN%2CKMYF%2CKNKX%2CKNRS%2CKNZY%2CKRNM%2CKSEE&home=KSAN

The first annoyance.

This was an issue, since our Etsy page allows customers to visit our website, customize their map, and paste the link into a “personalization” field to finish checkout. One time, a customer didn’t use the large “Copy Link” button, and instead choose to copy the URL from her web browser instead (which is completely expected! As a human interface designer, you should be aware all users developed different habits in navigating their devices). The link was cut off since she didn’t select it all, but luckily after painful digging through the server logs, I was able to recover her selection.

More annoying reasons to switch

Other times, customers run their selection and everything is fine, but we notice that an LED would be uncomfortably close to the edge. Since most customers appreciate a heads-up, our standard operating procedure outlines that we reply with a recommendation that has more comfortable bounds and the customization link if the customer wants to make any tweaks. On the phone, it makes the message look like this, with the URL taking up an unnatural amount of screen real estate.

Why not use a database?

Common URL shorteners like bit.ly or tinyurl.com use a database to store this information, and simply perform a database lookup every time they need to grab it. This way, they can achieve truly tiny URL sizes. It’s like saying “page 64, section 10” instead of saving a whole book. However, I didn’t want to be reliant on a database. What if the database goes offline? What if the data gets lost? After years and years, the database size will continue to grow. (slowly, but still).

Information Theory

The solution: Information Theory. I had watched a video by 3Blue1Brown: Reinventing Entropy | Compression is Intelligence Part 1 and realized there are different levels of importance to the data I am storing and the data could be heavily compressed.

Data Structure (for nerds)

Feel free to skip this part. For nerds though, this is the juiciest part of this whole write-up. Every Aviation Map follows the following data structure:

• Bounds (North, East, South, West)
• Frame Variant (color, orientation)
• Home Airport
• Airports

North, South, East, and West

For bounds, the FAA source files are 42.33 meters/pixel. This means there is a theoretical limit for how precise we can get with the latitude/longitude. At the Equator, 0.001° ≈ 111 meters, while 0.0001° ≈ 11.1 meters. (Our target is 42m/px.) Therefore, 4 decimal points of precision get us more than enough accuracy to pinpoint the exact pixel boundaries for each individual map. With 21 bits (2^21 = 2097152) we have enough information to encode any number from -90.0000 to +90.0000, or the range of latitude as standardized by WGS84. Similarly, 22 bits can encode any number from -180.0000 to +180.0000, or longitude.

Now our dataframe looks like this:

bits 1-21: South
bits 22-43: West
bits 44-64: North
bits 65-86: East

Frame Variations

Currently, we only have black and white frames, and they can either be horizontal or vertical. For this, there are only 4 possibilities: black vertical, black horizontal, white vertical, or white horizontal. This may feel familiar to binary encoding: 00, 01, 10, 11. (Where the first digit represents isWhite, and the second digit represents isHorizontal). However, we want to keep some options available for the future while keeping the data protocol readable at all times. Since Aviation Maps may expand to more frame variants in the future, I opted to pad the “variants” to fill 8 bits, meaning 6 are currently unused.

Now our dataframe looks like this:

bits 1-21: South
bits 22-43: West
bits 44-64: North
bits 65-86: East

bits 87-95: Variant

Airports

Airports are a little trickier. Our database sorts airports by their ICAO (International Civil Aviation Organization) identifier. ICAO IDs are always 4-digit codes which identify every major airport in the world. They can only contain the characters A-Z, 0-9, or 36 unique possibilities for each character.

This means that with 144 bits (36 × 4), we can easily identify a single airport. But we can do better.

The first character of the ICAO ID in most places in the US is K. (KSAN, KLAX, KJFK, KSTL). The first letter of the ICAO ID represents a broad global geographic region, which means more than likely, all the airports will have the same code. This means we only need to keep track of the first letter once, then follow with the rest for a cheap 25% information discount.

Ex: KSAN, KLAX, KJFK, KSTL -> SAN, LAX, JFK, STL

What if we DO have multiple beginning codes? In the future, we may have a gigantic aviation map of the entire US, which may include the prefix “P” instead of just “K”. Well, that’s why protocol engineering is so lovely, we get to make our own rules. I opted to also encode the number of airports which this first digit, or “prefix” covers. I’ll outline this clearer below, but here is the idea:

Ex: “The next 10 airports start with K, then 5 airports start with P”

Now we are getting REAL technical. 36^3 = 46656 unique combinations (three times 0-9, A-Z). To squeeze what we can out of information theory here, 16 bits happen to be able to store 65536 unique combinations. Technically we are leaving a tiny bit of information on the table here (less than 1 bit per airport), but practically this is already incredibly compact for our use case.

Now any code from 000 to ZZZ can be packed into just 16 bits.

Finally, we need to store the home airport. Since the home airport must be in the list of airports we already know, we don’t need to write it all by hand, we can simply store its index.

Let’s see all this in action. Ex: KSAN, KLAX, KJFK, KSTL, PANC, PARC, PHNL with home airport KSAN

In computer talk, this looks like this: 001010 Prefix K in base-36 00000100 4 airports begin with K 1000111100111111 SAN in base-36 0110101111011001 LAX in base-36 0110001001100000 JFK in base-36 1001000111101001 STL in base-36 011001 Prefix P in base-36 00000011 3 airports begin with K 0011010111101000 ANC in base-36 0011011001111000 ARC in base-36 0101100101100001 HNL in base-36 00000000 Home airport is the 1st element (KSAN)

Storing this information in a URL

We can pack all of these tiny 1s and 0s into a URL by using URL Base-64 encoding. The computer can encode all of this using uppercase letters (A–Z), lowercase letters (a–z), digits (0–9), a hyphen (-), and an underscore (_). Since the server and the browser both understand how to parse this protocol, the following link works to uniquely identify a white, horizontal frame of Phoenix with 11 airports:

https://aviation-maps.com/etsy?c=lg6xR-kS6_sqAqgMJUCzxoPzFGSU4vUxZV41-qbpd-mIEVj6kA

And importantly, this link will take up ~3 lines when displayed fully on a mobile device as opposed to 10+.

Conclusion

Yes, that was an absurd amount of engineering to reduce a couple of characters in the URL. But these are exactly the kinds of problems I love solving. While it may seem like a small quality of life improvement, it represents a love for the process of engineering- of finding an elegant solution for a frustrating problem- of future-proofing a design such that I have a strong foundation to build off of.

Now that you know how this works, why don’t you try it yourself? The protocol you just learned about is powering our website right now! Head on over to the customize page and give it a go. If you’d like to support our business and have a neat Aviation Map to display the live weather in your own home, feel free to customize it to your heart’s content and purchase one! It means a lot!