In a recent project, our multi-platform mobile application required the fast rendering of many (10000+) markers/annotations on a variety of popular map APIs, such as Apple Maps and Google Maps, in fully interactive mode. We were able to achieve this by using an approach which I summarize here.

Choosing a data structure depends on your data

• The optimal approach depends on the amount of data that has to be shown, and the associated spatial distribution, but in most cases we recommend using a clustering API. Even for small amounts of data (N<100), the visual and interactive benefits outweigh the cost of implementation, especially if open-source libraries or clustering libraries native to the map APIs can be used.

• In our case, we developed our own clustering API due to the need for both a consistent cross platform solution for all OS versions, and full customization.

• We find this approach appropriate for data counts of order N = 10000 to 100000, if the data can be efficiently compressed and stored in the application bundle. Our application commences the data decompression and initialization of the clustering data structure upon application launch, and this process (on a background queue) is near instantaneous for modern (iOS and Android) devices and up to an acceptable 1-2 seconds on older machines.

• If the data count and associated load times are larger than the approximate range given above, then a back-end server-based solution would be preferred.

• If adopting a clustering approach, it should be possible to control the visual density of individual markers that appear at any time on the screen. Care should be taken to avoid too high or too low a density, both of which can frustrate the user.

• When the user is presented with a particular map region, whether stationary or moving, the application must acquire all annotations/markers in that region. For this purpose, data acquisition from the tree structure that underlies the clustering approach is very efficient (logarithmic with N)

Adding markers to the map - the performance bottleneck

• In practice, the visual and computational performance of your application will most likely depend on the adding of markers for a specific map region to the map API, which is advised to take place on the main UI thread. Therefore, this process should be minimized.
• If this process is triggered by some movement of the map region by the user, you should control its frequency with a specified "frame-rate" in Hz. Movie-quality frame-rates (24 Hz +) are generally not required - in our experience 6-10 Hz can be visually acceptable

fun onMapStartsMoving() {
   //create timer which calls a callback every 1/framerate seconds
}

fun onMapStopsMoving() {
   //end timer
}

fun getPointsCallback() {
   //get region showing on map
   //get relevant data from data structure and convert into map markers
   //remove redundant markers and add appropriate markers
}

• Each time you acquire and add a new array of markers to the map, compare this array with existing markers on the map, and make sure to remove and add the absolute minimum number of markers, using a sequence of operations as below.

var currentMarkers: Set

func mapPointSwappingOperations(newMarkers: [markerType]) {

   val markersToKeep = currentMarkers.intersect(newMarkers)
   val markersToAdd = newMarkers.minus(markersToKeep)
   val mapPointsToRemove= currentMarkers.minus(markersToKeep)

}

• Ensure that each marker (both individual point and cluster) is assigned a unique hashcode, based on its coordinate (assuming no two points share the same location) or some other method to avoid collisions, to facilitate this comparisons.

• Even if you are adopting a low "frame-rate", adding a large number of markers at once can overwhelm the CPU in those cases where the map API generates many background threads to perform the rendering. Solving this problem by using parallelism can be risky and generally not recommended. Therefore, we introduce a queueing system, where "markersToAdd" is treated as a queue of map points to be added to the map at spaced time intervals.

• First, we modify "mapPointSwappingOperations" above to ensure the queue is not being emptied/flushed while we modify it. Here, "isFlushing" is a sentinel flag or lock, to be modified only in the UI thread.

func mapPointSwappingOperations(newMarkers: [markerType]) {

   if(isFlushing) {
      stopFlushingQueue()
      isFlushing = false
   }
   val markersToKeep = currentMarkers.intersect(newMarkers)
   val markersToAdd = newMarkers.minus(markersToKeep)
   val mapPointsToRemove= currentMarkers.minus(markersToKeep)

   startFlushingQueue()
}

• The final method call "startFlushingQueue()" commences the queue in which markers are sequentially added, as below:

 fun startFlushQueue() {
    isFlushing = true
    //start a repeating timer which calls the method below at a specified "queue flushing rate"
 }

 fun queueCallback() {
    // if markersToAdd is empty, end the timer and exit
    // add the first element in markersToAdd to the map
    // remove this element from markersToAdd
 }

Notes

• On recent mobile devices that we've tested, the addition of a single marker to the map can take the Google API of order 1-2 milliseconds, and the API can handle several overlapping marker additions at once. Therefore, we have used a queue flushing rate of about 0.5 marker per milliseconds.

• This queueing system ensures a smooth addition of markers, which is preferable to the brief freezing that can occur otherwise. Some further enhancements are as follows:

  • add a brief fade-in animation to the marker on addition to the map, which aids the visual impact and masks the brief delay in the queuing system
  • track how long each marker addition takes in queueCallback method, and assign this value to the queue flushing rate via a low pass filter to smooth out any major changes (e.g. when going from marker-dense to marker-sparse regions of the map).
  • we recommend experimenting with different combinations of the "frame-rate" and the "queue flushing rate" to obtain best performance. If your queueing system code works well, we found it possible to increase the frame-rate to close to movie-rate (24Hz), producing a very nice visual experience.