Embodiments relate to methods for efficiently encoding sensor data captured by an autonomous vehicle and building a high definition map using the encoded sensor data. The sensor data can be LiDAR data which is expressed as multiple image representations. Image representations that include important LiDAR data undergo a lossless compression while image representations that include LiDAR data that is more error-tolerant undergo a lossy compression. Therefore, the compressed sensor data can be transmitted to an online system for building a high definition map. When building a high definition map, entities, such as road signs and road lines, are constructed such that when encoded and compressed, the high definition map consumes less storage space. The positions of entities are expressed in relation to a reference centerline in the high definition map. Therefore, each position of an entity can be expressed in fewer numerical digits in comparison to conventional methods.