Too many Markers, revisited

Too many Markers, revisited

An empirical analysis of web-based methods for overcoming the problem of too many markers in zoomable mapping applications

This paper was published at the 14th International Conference on Computational Science and Its Applications (ICCSA 2014). Authors: Sebastian Meier (Author), Frank Heidmann (Co-Author)
  Download Paper as PDF

Abstract

The growing amount of available data is creating a need for mass-data visualizations in many areas. The mapping of large spatial data sets is not only of interest for experts anymore but moves into the domain of public applications with regard to the latest advances in web cartography. This creates a need for usable and understandable interactive techniques that allow the visualization and exploration of large spatial data sets. In a series of experiments we look at a variety of technologies aiming at overcoming the obstacle of displaying large spatial datasets in interactive mapping applications. In this short paper we will present our ongoing research on the methods of Marker Clusters, Heatmaps and Tiled Heatmaps as well as a quantitative and qualitative empirical evaluations of the performance of each of these methods. We conclude with what we think should be a new direction for further research in this area.

Keywords: Geovisualization, maps, web, study, marker, cluster, heatmap

I. INTRODUCTION

The growing amount of data is a driving force behind new fields of research in mass data visualization. Latest example for research conducted in this area is the field of network visualizations or the massive data plots by Hochman and Manovich (Hochman & Manovich, 2013). One might argue that mass data visualizations are not new. What might be new are the technologies available for visualizations as well as the target audiences. The field of visualization is moving away from being an expert-only field towards being a field that is relevant for the public. Making data accessible and readable for scholars from many different fields as well as for a broad public audience.
The same applies for data visualization in cartography. Experts in the field have been working with mass data and geovisualization techniques since the introduction of the first Geo Information Systems (GIS) in the late 1960s (Coppock & Rhind, 2001). But especially with the advances in web cartography and the growing popularity of modern web mapping applications like Google maps (Google Inc., 2014) or Bing (Microsoft Corporation, 2014), we see the public and other fields involved in the usage of modern web-based cartographic applications for private and professional purposes. At the same time, we see a growing number of services collecting or creating large amounts of spatial data. Services like yelp (Yelp, 2014) or foursquare (Foursquare, 2014) for example. This combination of trends creates the need for new spatial mass data visualization methods for web-based cartographic applications.

Figure 1. Left: 200 Markers, Right: 1 Marker.

Figure 1. Left: 200 Markers, Right: 1 Marker.

II. CHALLENGE

Looking at small datasets the conventional marker is still sufficient, but with a growing number of data points, maps become confusing (Fig. 1). This is where our research starts. In the field of cartography, a large research corpus already exists when it comes to two-dimensional static maps. Research has been conducted with focus on e.g. label placement (Christensen, Marks, & Shieber, 1995; Marks & Shieber, 1991), dot placement (Hey, 2011) or – when it comes to clustered data – choropleth maps. All of this shows us how to work with visual features in dense spatial data environments.
The problem that arises when we try to translate this knowledge into the field of web cartography is the factor of zoomability. While the old methods concentrated on displaying information at one specific zoom-factor, modern web mapping applications allow the user to zoom in and out and thereby reach different levels of detail. As mentioned in Ben Shneidermans visualization mantra “overview first, zoom and filter, then details-on-demand” (Shneiderman, 1996), those web applications allow users to start at a low zoom-level and see a big area with a large spatial data-set and then zoom in and thereby minimize the amount of data being displayed.
The challenge is to overcome the confusing marker agglomerations in low zoom levels but still provide the user a detailed overview. Or as Woodruf et al framed it: “A constant information density” (Woodruff, Landay, & Stonebraker , 1998).

III. EXISTING METHODS

Over the last few years a couple of methods have been developed to overcome web-based geovisualization applications with too many markers. The most prominent methods are marker clusters, other solutions include heatmaps and choropleth based clustering approaches or tiled heatmap methods.

A. Marker Cluster

The marker cluster uses a grouping approach: if the density of markers is too high in a specified area, the markers are grouped and replaced by a cluster-object (Fig. 2.1) (Delort, 2010; Leaflet, 2014; Mahe & Broadfoot, 2010).
As a result of the clustering it is required to introduce a new visual entity to the map, which differentiates the cluster- object from the single markers. In addition to simply differentiating the two entities, some of the existing solutions let the reader of the map know how many markers are merged into each cluster-object. The simplest way of doing this is adding a label with a number indicating how many markers were merged.

B. Heatmaps

The heatmap approach is a way of calculating the density of spatial data points per region and applying a color from a predefined color range to this region. Most commonly the color range of red for high to blue for low density is used in those visualizations (Fig. 2.2).

C. Tiled Heatmaps

On a very rudimentary level the tiled heatmap and the heatmap follow a similar approach. The tiled heatmap is also calculating the data points per region and applying a corresponding color to the value, but in contrast to the heatmap the tiled heatmap has a lower resolution (Fig. 2.3).

D. Choropleth Maps

Similar to heatmaps and tiled heatmaps choropleth maps also calculate data points per region. In contrast to heatmaps and tiled heatmaps that use a raster that is independent from the map, the choropleth map is using shapes that are predefined. Those predefined shapes can for example be of political origins and depict national borders. We included the choropleth maps in this list of methods because in some cases it is a valid solution for clustering spatial data points. We have excluded this type of visualization from our further research because this type of visualization requires additional data regarding the predefined shapes. This data is not available in most cases but of huge importance in the process since the zoomability of choropleth maps requires more detailed shapes for higher zoom levels.

IV. RELATED WORKS

The existing research regarding marker clusters is mostly looking at applications (Komninos, Besharat, Ferreira, & Garofalakis, 2013) or the algorithmic backbone of the clusters, that means at the algorithms that decide how the clustering is computed (Bär & Hurni, 2011; Delort, 2010;Kefaloukos, Vaz Salles, & Zachariasen, 2012; Stefanakis, 1996). Besides this computer-centered research the human- centered hci research on marker clusters is still not very profound. This is why our research is focusing on gaining more insights into the usability aspects and thereby the perceptual-cognitive tasks that those visualization methods bring with them, both of which were framed by Chen as 2 of the 10 unsolved information visualization problems (Chaomei Chen, 2005). 

Figure 2. 1. Marker Cluster, 2. Heatmaps, 3. Tiled Heatmaps

Figure 2. 1. Marker Cluster, 2. Heatmaps, 3. Tiled Heatmaps

V . EXPERIMENT

In this chapter we will describe two experiments that were conducted on the methods described above. The first experiment is looking at the performance of the subject group in terms of time and precision, while the second experiment is looking at the way people read and understand the visualizations.
We used a real world data set for the experiment, containing data on restaurants in the inner city of Berlin, Germany. The dataset was holding 15.329 positions in the urban area of Berlin.
The experiments were conducted through amazons mechanical turk (AMT) (Amazon Inc., 2014). The mechanical turk is an online platform that allows so-called workers to perform small tasks and in return being paid by the so-called requesters. Conducting academic surveys by means of the mechanical turk system is still a very new way of conducting surveys, but has already generated good results and positive feedback from a wide range of research fields (Buhrmester, Kwang, & Gosling, 2011; Paolacci, Chandler, & Ipeirotis, 2010). As long as several requirements are met, like keeping tasks short, easy to understand, and including verifiable questions, as for example Kittur et al suggest, mechanical turk can generate valid results (Kittur, Chi, & Suh, 2008). Joel Ross et al presented an overview of the demographic development of the mechanical turk participants (Ross, Irani, Silberman, Zaldivar, & Tomlinson, 2010), which says that workers come mostly from the US and India and that there is a slight bias towards female workers. The demographic data we collected showed that the participants we reached were more men (60%) and more Indian participants than workers from other countries (50%). The age of our participants ranged from 20 to 40 years with a peak in the mid 20s.
In our experiment we did not only want to test the existing visualizations against each other, but also wanted to go a step further and test how adding visual variables to the cluster-objects would influence the participants performance of comparing the cluster-objects with each other. Visual variables most prominently introduced by Bertin in 1983 (Bertin, Dodge, Kitchin, & Perkins, 2011) help the reader to not only differentiate between two objects but also to rank objects for example by size or color (Carpendale, 2008), which is one of the most fundamental functionalities of the visualization of a spatial data points (locate, read, classify, group and compare) (Heidmann, 2013).

A. Experiment I: Performance

1) Experiment Design:

In our first experiment we compared the marker cluster extended through visual variables (size and color) with heatmaps and tiled heatmaps regarding accuracy and time (Fig. 3). Through the variation of variables we reached a number of 11 visualizations, which were tested by 330 participants, 30 participants per visualization.
After answering a demographic questionnaire the participants received a short explanation on how the presented geovisualization works, which means they were explained which visual variables indicate high and low values on the map. Before they were allowed to see the map they were briefed on their first task: Click on the area with the highest/lowest values. Then the participants were directed to a page showing the visualization on top of a map. After the participant selected an area they were redirected to the next map. Every participant had to work on 6 maps.
On the last page the participants had to perform a semantic differential (Hassenzahl, Platz, Burmester, & Lehner, 2000) and a Subjective Mental Effort Questionnaire (SMEQ) which has proven to be a good tool for letting participants rate the difficulty of a task in a post-task questionnaire (Sauro & Dumas, 2009).

Figure 3. Visualization types used in Experiment I.

Figure 3. Visualization types used in Experiment I.

2) Evaluation

For evaluation purpose we collected the time it took participants to select the maximum or minimum value of each map they were shown as well as the precision of their task result, which means how close they were to the maximum or minimum.
The time distribution for all tasks was very close, the maximum differences between the averages were 4 seconds for the task of finding the maximum, and 5,5 seconds for the minimum. The bigger variation for the minimum goes along with the finding that the time for finding the minimum took an average of 35% longer across all visualizations. But we couldn’t find correlations to the visual variables or the visualization type.
The finding that the determination of the minimum was more difficult was also visible in the precision data. The task of finding the maximum had a maximum offset of 0.8%, the task of finding the minimum had maximum offset of 5%. Furthermore we could identify 2 patterns from the precision results (Fig. 4).

Figure 4. Precision offset in % for finding the maximum (1. row) and finding the minimum (2. row).

Figure 4. Precision offset in % for finding the maximum (1. row) and finding the minimum (2. row).

a) Heatmaps and tiled heatmaps performed better than cluster maps: This finding applies to tasks, finding the maximum and finding the minium. The three tiled heatmap visualizations performed best, followed by the heatmap, which performed equally good on finding the minimum but slightly worse for finding the maximum.

b) Size is a good visual variable for identifying the maximum: The visual variable size has proofen to be significant for identifying maximums (see Group 2 in Fig. 4). Regarding the task of finding the minimums, size has also been signifcant but not as outstanding as in the task of finding the maximum.

c) Regarding the collected SMEQ and semantic differential values: We received very similar values for each visualization and couldn’t find patterns or correlations regarding the visual variables nor the variable time or precision.

3) Discussion

From the results we can say that size is a good visual variable for marker clusters, which was identified by a previous study by Garlandini and Fabrikant who look at visual variables in spatial data visualization in general (Garlandini & Fabrikant, 2009). Furthermore we saw that the heatmaps and tiled heatmaps performed very well, here we need further research through qualitative studies to find out why those visualizations performed better.

B. Experiment II:

Understanding In Experiment I we gave each participant an introduction in order to explain how the visualization works. In the second experiment we were interested to find out what participants would actually see in the visualizations when they were given no introduction.

1) Experiment Design

Therefore we transferred the visualization types from Experiment I that we then extended by the color that was used. While in Experiment I we only used red as a visual variable due to its high contrast to the underlying map, we added blue and green as additional colors in our second experiment, because our hypothesis was that color will influence the understanding of what is shown in the visualization.
The second experiment also started with a demographic questionnaire. After the first round of questions the participants were shown one of 15 visualizations (Fig. 5). One group was shown just the visualization and one group was shown the visualization with a title that said “Restaurants in the city of Berlin”, and they were all asked to describe what they think the visualization on top of the map was supposed to be. The test was conducted on 239 participants, but due to errors we had to exclude 29 data sets and came down to 210 participants, 14 per visualization, 7 per group.

Figure 5. Visualization types used in Experiment II.

Figure 5. Visualization types used in Experiment II.

2) Evaluation

To evaluate the qualitative data we received from our participants we screened all answers first and identified a set of variables:

a) Location or Area: 70% of the participants connected the visualizations to either location or area data.

b) Density and Ranking: 40% of the participants identified the visual variables as a ranking of some sort, 13% even identified it as an indicator for density.

c) Urban entity: 70% of the participants identified some sort of urban entity, this ranked from hotels, restaurants, parks to more statistical data like crime rates.

d) Restaurant: 77% of the participants, that were shown the title, identified the visualized entities to be restaurants.

e) Water or Nature: 7% of the participants identified the represented entity to be some form of nature, like trees or parks or to be related to water.

f) Cities: 4% of the participants did not understand the map and thought the markers were labels for cities. Color correlation: 90% of the participants who identified water or nature did it in cases when they were presented green or blue maps.

From analyzing the results of our clustering process through the variables listed above we were able to identify some correlations and generate a series of insights:

a) Heatmaps and Tiled Heatmaps are more likely to be connected to area data than point data: 65% of the participants who received a heatmap or tiled heatmap saw area data like population density or crime rates in the data. Markers were instead referred to spatial location data, like restaurants or hotels. The only exceptions were the tiled heatmaps that used circles as visualizations, they seemed to be interpreted as markers and not as heatmaps.

b) Density is an abstract concept, people refer visual variable ranking to more common rankings: only 13% of the participants identified density, but 40% identified the visualization to be some sort of ranking. The most common association, especially from the participants who saw the title, was user rankings, like from a social media platform.

c) Color and label texts are used to connect the visualization to the mental models of the participants: the 7% of participants who saw nature and water were all participants who saw blue (water) or green (nature) visualizations. Beyond that we noticed several participants who tried to use the label information to make sense of the visualization. The numbers, actually representing the number of clustered data points, were connected to distances, ratings or highway ids.

3) Discussion

Even though the results discussed in the evaluation above sound promising, we have to point out that only 13% of participants identified the visualization to be about density. However, we were able to identify that heatmaps might not be the best visualization to show the density of location data and should instead be used to show areal data like population. Furthermore, the design of the visualization should take the single data items’ meaning into account, for example by visualizing data on water in blue.

VI. CONCLUSION

Marker clusters as well as heatmaps and tiled heatmaps are viable solutions for overcoming the problem of displaying a large number of markers in a small area from a technical viewpoint. But none of the proposed visualization methods has proven to be intuitively understood by our participants. From a design viewpoint we saw that it is important to add visual variables to the marker cluster object to help users identify, classify and compare the visual entities on the map.
As pointed out in the introduction the research presented in this paper is ongoing research. We see the two studies as a starting point for developing new methods and conducting further research on the cognitive processes involved in reading marker clusters, heatmaps and tiled heatmaps. Taking the findings of this paper into account we propose that new techniques should be developed that take the characteristics of the data into account and extend the existing visualizations in order to help users connect the visualization with the data beneath.

REFERENCES

[1] Amazon Inc. (2014). Amazon Mechanical Turk – Welcome. Retrieved March 10, 2014, from https://www.mturk.com/mturk/welcome

[2] Bär, H. R., & Hurni, L. (2011). Improved Density Estimation for the Visualisation of Literary Spaces. Cartographic Journal, the, 48(4), 309–316. doi:10.1179/1743277411Y.0000000022

[3] Bertin, J., Dodge, M., Kitchin, R., & Perkins, C. (2011). General Theory, from Semiology of Graphics. The Map Reader (pp. 8–16). Chichester, UK: John Wiley & Sons, Ltd. doi:10.1002/9780470979587.ch2

[4] Buhrmester, M., Kwang, T., & Gosling, S. D. (2011). Amazon’s Mechanical Turk: A New Source of Inexpensive, Yet High-Quality, Data? Perspectives on Psychological Science, 6(1), 3–5. doi:10.1177/1745691610393980

[5] Carpendale, M. S. T. (2008). Considering Visual Variables as a Basis for Information Visualisation.

[6] Chaomei Chen. (2005). Top 10 Unsolved Information Visualization Problems. IEEE Computer Graphics and Applications, 25(4), 12–16. doi:10.1109/MCG.2005.91

[7] Christensen, J., Marks, J., & Shieber, S. (1995). An empirical study of algorithms for point-feature label placement. ACM Transactions on Graphics, 14(3), 203–232. doi:10.1145/212332.212334

[8] Coppock, J. T., & Rhind, D. W. (2001). The History of GIS (Vol. 1, pp. 21–43).

[9] Delort, J.-Y. (2010). Hierarchical cluster visualization in web mapping systems (p. 1241). Presented at the the 19th international conference, New Y ork, New Y ork, USA: ACM Press. doi:10.1145/1772690.1772892

[10] Foursquare. (2014, March 10). Berlin | Food, Nightlife, Entertainment. Retrieved March 10, 2014, from https://foursquare.com/

[11] Garlandini, S., & Fabrikant, S. I. (2009). Evaluating the Effectiveness and Efficiency of Visual Variables for Geographic Information Visualization. In Lecture Notes in Computer Science (Vol. 5756, pp. 195–211). Berlin, Heidelberg: Springer Berlin Heidelberg. doi:10.1007/978-3-642-03832-7_12

[12] Google Inc. (2014, March 10). Google Maps. Retrieved March 10, 2014, from https://maps.google.com/

[13] Hassenzahl, M., Platz, A., Burmester, M., & Lehner, K. (2000). Hedonic and ergonomic quality aspects determine a software’s appeal (pp. 201–208). Presented at the the SIGCHI Conference, New York, New York, USA: ACM Press. doi:10.1145/332040.332432

[14] Heidmann, F. (2013). Interaktive Karten und Geovisualisierungen. In W. Weber, M. Burmester, & R. Tille (Eds.), Interaktive Infografiken (pp. 39–69). Berlin, Heidelberg: Springer Berlin Heidelberg.

[15] Hey, A. (2011). AUTOMATED DOT MAPPING – HOW TO GENERATE DOT CLUSTERS (pp. 1–6). Presented at the Proceedings of the 22nd International Cartographic ….

[16] Hochman, N., & Manovich, L. (2013). Zooming into an Instagram City: Reading the local through social media. First Monday.

[17] Kefaloukos, P. K., Vaz Salles, M., & Zachariasen, M. (2012). TileHeat (1389023194 ed., pp. 349–358). Presented at the the 20th International Conference, New York, New York, USA: ACM Press. doi:10.1145/2424321.2424366

[18] Kittur, A., Chi, E. H., & Suh, B. (2008). Crowdsourcing user studies with Mechanical Turk (p. 453). Presented at the Proceeding of the twenty-sixth annual CHI conference, New York, New York, USA: ACM Press. doi:10.1145/1357054.1357127

[19] Komninos, A., Besharat, J., Ferreira, D., & Garofalakis, J. (2013). HotCity (pp. 1–10). Presented at the the 12th International Conference, New Y ork, New Y ork, USA: ACM doi:10.1145/2541831.2543694

[20] Leaflet.(2014).Leaflet/Leaflet.markercluster. Press.

[21] Mahe, L., & Broadfoot, C. (2010, December). Too Many Markers! – Google Maps API — Google Developers. Retrieved March 2, 2014, from https://developers.google.com/maps/articles/toomanymarkers

[22] Marks, J., & Shieber, S. (1991). The Computational Complexity of Cartographic Label Placement, 1–28.

[23] Microsoft Corporation. (2014). Bing Karten – Anfahrtsbeschreibungen, V erkehrsinfos und Straßenbedingungen. Retrieved from http://maps.bing.com

[24] Paolacci, G., Chandler, J., & Ipeirotis, P. G. (2010). Running Experiments on Amazon Mechanical Turk. Judgement and Decision Making, 5(5), 411–419. Retrieved from http://papers.ssrn.com/sol3/papers.cfm?abstract_id=1626226

[25] Ross, J., Irani, L., Silberman, M. S., Zaldivar, A., & Tomlinson, B. (2010). Who are the crowdworkers? (pp. 2863–10). Presented at the the 28th of the international conference extended abstracts, New York, New York, USA: ACM Press. doi:10.1145/1753846.1753873

[26] Sauro, J., & Dumas, J. S. (2009). Comparison of three one-question, post-task usability questionnaires (pp. 1599–1608). Presented at the the SIGCHI Conference, New York, New York, USA: ACM Press. doi:10.1145/1518701.1518946

[27] Shneiderman, B. (1996). The eyes have it: a task by data type taxonomy for information visualizations (pp. 336–343). Presented at the 1996 IEEE Symposium on Visual Languages, IEEE Comput. Soc. Press. doi:10.1109/VL.1996.545307

[28] Stefanakis, E. (1996). CLUSTERING DYNAMIC MAP OBJECTS BASED ON DENSITY MEASURES, 1–6.

[29] Woodruff, A., Landay, J., & Stonebraker, M. (1998). Constant information density in zoomable interfaces. The Working Conference, 57–65. doi:10.1145/948496.948505

[30] Yelp. (2014, March 10). Berlin Restaurants, Dentists, Bars, Beauty Salons, Doctors. Retrieved March 10, http://www.yelp.com/berlin