An online system builds a high definition (HD) map for a geographical region based on sensor data captured by a plurality of autonomous vehicles driving through a geographical region. The autonomous vehicles detect map discrepancies based on differences in the surroundings observed using sensor data compared to the high definition map and send messages describing these map discrepancies to the online system. The online system ranks the autonomous vehicles based on factors including an upload rate indicating how often the vehicle was used providing data to the online system. The sensor data from vehicles is uploaded to the online system (e.g., in the cloud) to create the HD map while spreading the burden of uploading this data as evenly as possible across a fleet of vehicles. Data uploads are expensive and time consuming, so the system makes this negligible for each vehicle by balancing/managing the uploads carefully across the fleet.