How to store a GPS coordinate in one byte or less.

The market is flooded with GPS gadgets storing GPS coordinates in a very wasteful manner.

Below is an example of how one GPS coordinate is stored using 96 bytes, in the popular gpx format:

<trkpt lat=’59.271327′ lon=’17.846174′>
 <ele>1.375</ele>
 <time>2008-10-14T16:24:35Z</time>
</trkpt>

What a waste, thanks to XML!

Let’s make an example. The sample gpx file contains 2269 gps points. The size of this file is 223132 bytes.
The zipped file size is 30579 bytes. But, there is a lot of redundancy left.

Now we are going to see how it is possible to make a 94-fold reduction in size.

• Skip all time stamps except the first one.
• Use UTM instead of WGS84. Let’s use one meter precision.
• Skip the elevation, it has bad precision anyway.
• Compute the first difference between the points. This gives us the speed in m/s.
• Compute the second difference. This gives us the acceleration in m/s².
• Skip the XML. Use binary storage instead.

If the vehicle is moving straight at a constant speed, the acceleration will be zero (0,0).
Store accelerations between -7 and 8 m/s² in one byte (16×16=256).
Reserve one of these as a prefix for double byte acceleration covering -127 to 128 m/s² (256×256=65536).

This way 2269 points can be compressed into 4 + 8 + 8 + 2362 = 2382 bytes.

It is possible to save even more space using Huffman coding as some accelerations will be more common.
Huffman coding brings the numbers down from about 8.4 to 4.4 bits per gps position.

Using decimeter instead of meter precision approximately doubles the storage needed.

Note: Acceleration and retardation for a car is approx 1g = 10 m/s².
      Acceleration of the Space Shuttle or Jumbo Jet: 3g = 30 m/s².
      Turning acceleration for military aircraft: 9g = 90 m/s².
     
Constant recording during one year can be stored in 365 x 24 x 60 x 60 = 32 megabytes.
The gpx format will store only four days in the same amount of memory.