The emergence and evolution of OpenStreetMap: a cellular automata approach

Abstract

Collaborative mapping projects, such as OpenStreetMap (OSM), have received tremendous amounts of contributed data from voluntary participants over time. So far, most research efforts deal with data quality issues, but the OSM evolution across space and over time has not been noted. Therefore, this study is dedicated to the evolution of the contributed information in order to understand an emergent phenomenon of so-called collaborative contributing. The main objective of this paper is to monitor the evolutional pattern of OSM and predict potential future states through a cellular automata (CA) model. This is exceedingly relevant for numerous OSM-based applications. Descriptive spatiotemporal analysis of the contributions for the time period 2007–2012, using the city of Heidelberg (Germany) as a case study, reveals that early contributions are given three years after the launching of OSM, while after nearly six years, most of the areas are discovered. The simulation results for the validated CA model, predicting OSM states for 2014, provide clear evidence that most of the areas have been explored three years after people began mapping until 2010, and thereafter, the densification process has begun and will cover most parts of the city although the amount of contribution depends on the land use types.

Keywords:

• cellular automata
• OpenStreetMap
• transition rules
• spatiotemporal analysis
• collaborative contributing

1. Introduction

The emergence and evolution of Web 2.0 technologies provide the public with the opportunity to interactively share their information of objects in the form of notes and photos, among others, and openly communicate with other people in a virtual world (Goodchild 2007a). A big portion of user-generated contents (UGCs) contains geo-enabled information. This part of UGC is termed volunteered geographic information (VGI: Goodchild 2007b), which represents an alternative source of geodata collected from individuals through a bottom-up process. As proven by the Economist News Report (2012), nowadays, these data, as well as the companies behind them, have a far-reaching monetary and economic impact. For instance, Facebook was priced at almost US$100 billion in 2012 (Economist News Report 2012).

This revolutionary data-gathering process is permitted because of the rapid and wide penetration of smartphones and GPS-enabled devices, among other things. Moreover, citizens’ science projects have given this opportunity to non-expert people to map the environment by themselves and not through a classical method (Mooney and Corcoran 2013). Although these neo-mappers may not have acquired enough expertise in collecting data, the information coming from them comprises new spatial objects and attributes that do not exist in traditional databases (Haklay, Singleton, and Parker 2008). Until now, a large number of citizens’ knowledge-based projects (Georgiadou et al. 2013) for diverse purposes have been launched, including OpenStreetMap (OSM: Ramm, Topf, and Chilton 2010), Wikimapia (Goodchild and Li 2012), Geowiki (Fritz et al. 2012), and Eye on Earth (Bernard et al. 2013). Among them, OSM has been a unique project due to its huge success in attracting the most public attention and a considerable amount of contributions so far. By July 2013, OSM possessed nearly 1.33 million users (retrieved from http://osmstats.altogetherlost.com/). The major benefit of OSM is not only having access to the entire database for any timestamp, but also having a rising network of people shaping a community intent on correcting inaccurate or erroneous contributions of others, and thus improving the entire quality of the data-set in a systematic way (Mooney and Corcoran 2012b). The dictum of OSM is that the whole mapping process is organized in a democratic manner in which (1) everyone is invited to join, (2) everyone can create/edit/delete objects, (3) everyone has access to the data, and, finally, (4) the entire data history is shared free of charge (Goodchild and Glennon 2010). The OSM community is actively considering feedback from users and attempts to improve the performance of the entire system by updating the image libraries and editing tools and functionalities. To be noted, it is assumed that the whole OSM project, comprising the participators, the data collection process, the collected data, etc., forms a holistic system together. Furthermore, some active members of the community even observe and report destructive and harmful activities through the wiki pages and discussion lists (Ramm, Topf, and Chilton 2010). Even more essential, the OSM contributors mostly have detailed knowledge about the local environment, not anticipated in proprietary databases, and also share their latest observations together with their previous information; hence, some data might be totally up-to-date (Chilton 2009; Mooney and Corcoran 2012a). This is one of the most noteworthy advantages of OSM compared to traditional data providers.

Besides these appealing properties, the foremost concern of the OSM has been the origin, quality, and reliability of information (Flanagin and Metzger 2008). This fact is also reflected in the literature, where most efforts and research deal with evaluating the quality of OSM, including data completeness, spatial accuracy, and topological consistency (e.g., Haklay and Weber 2008; Haklay 2010; Hagenauer and Helbich 2012; Helbich, Amelunxen, and Neis 2012; Jokar Arsanjani et al. 2013a, 2013b). For example, Neis and Zipf (2012) analyzed OSM data completeness in Germany. They concluded that OSM data have proven their competence even with the proprietary TomTom data-set. More precisely, the total measured length of the OSM's contributed roads in Germany exceeds the total length of roads in TomTom. In a subsequent study, Neis, Zielstra, and Zipf (2013) compared several cities worldwide and concluded that the given contributions from these cities to OSM are competitive with Germany. In contrast to quality issues, less attention is paid to recognizing the OSM contributors’ motivations and also realizing the emergence and evolution of OSM (Neis, Zielstra, and Zipf 2013). This is of great importance, because if the degree of evolution in a specific area is high, it is more likely to receive more reliable information as more users are involved and, therefore, they correct each other's incorrect and inaccurate information.

Closely related to this lack of research, to the best of the authors’ knowledge, very little research deals with the spatiotemporal evolution of the OSM contents. This obscures insights into how OSM, as a dynamic humans-based system, functions, and where and when OSM attracts people to contribute and which spatial features direct peoples’ attention. Following Linus's Law (e.g. Haklay et al. 2010), it is expected that the more editions that are done by mappers on OSM features, the bigger the simultaneous increase in the quality of the data. Thus, the spatiotemporal OSM evolution is highly relevant to get knowledge of how OSM might emerge in the future and allows (at least crudely) statements about the future data quality for certain areas, impacting on potential applications based on OSM-data (e.g. navigation tasks, land-use mapping). A first analysis on the OSM evolution is carried out by Corcoran, Mooney, and Bertolotto (2013). They propose following two major processes within the OSM network: (1) the exploration of objects through discovering new areas to map, and (2) the densification of objects by digging into the previously explored areas and condensing the objects and information. In the present research, collaborative contributing is understood as a continuous and dynamic process, which is not limited in time and space. In this context, the OSM contributors are the actors, who are interactively contributing their information to the community and keeping it running.

Based on the identified research gaps, the main objective of this research is, therefore, to investigate past OSM developments in order to predict possible future OSM states. To be more precise, in order to leverage the understanding of the spatiotemporal evolution of OSM, a cellular automata (CA) model is used to embed the individuals’ contributions in OSM into a cellular network. Subsequently, the CA predicts the spatially and temporally upcoming OSM contributions for the year 2014. The following three research questions will be addressed:

• How has the collaborative contributing to the OSM project evolved?

• How can we effectively project contributions onto a spatiotemporal framework to study this phenomenon in space and time?

• Is there any evident spatial dependency between the amount, and location, of contributions and physical characteristics (e.g. land-use)?

The remainder of the paper is structured as follows. While Section 2 presents an overview on CA modeling, Section 3 introduces the materials used and discusses the applied methodology. Furthermore, in the final part of Section 3, the main outcomes of the modeling process are presented. Finally, Section 4 highlights major conclusions and outlines recommendations for future research.

CA modeling, introduced by von Neumann (1951), is a rule-based modeling technique based on customized and simple rules that can simulate the behavior of a phenomenon across time and space. Wolfram (1984) highlights the benefit of CAs to model highly complex real-world systems by means of simplified local rules. Ever since, due to their conceptual simplicity being a key advantage of this modeling approach, CAs are utilized for modeling a variety of dynamic phenomena, including land-use/land-cover changes (e.g. Mitsova, Shuster, and Wang 2011; Huang, Zhang, and Wu 2009), fire spread (e.g. Stambaugh and Guyette 2008), disease dissemination (e.g. Doran and Laffan 2005; González et al. 2013), and social changes and dynamics (e.g. Nowak and Lewenstein 1996; Dabbaghian et al. 2011).

Briefly, cells are the basic units of CA models in which each cell represents the status of the phenomenon in a specific location and for a given discrete timestamp. For example, a binary CA consists of a lattice of cells where the absence of a phenomenon is represented by ‘0’ and the presence of a phenomenon by ‘1’ (Chandler 2003). The state of a cell at time t + 1 is a function of the state of itself and of its neighboring cells at time t; this function is specified by a ‘transition rule’. The neighborhood specification is another crucial parameter for CA modeling that determines (1) how many cells are impacted by the transition rules and (2) by how many neighboring cells the central one is impacted (Verburg et al. 2004). The two most well-known neighborhood definitions are the ‘von Neumann’ and the ‘Moore’ neighborhood, as illustrated in Figure 1 (Fonstad 2006).

Figure 1. Common representations of CA models and first- and second-order neighborhood functions (von Neumann and Moore neighborhoods).

As indicated in Figure 1, the central cell of the square projects the simulated core-cell defined by its own neighborhood. The size of a neighborhood can be defined by different kernel sizes (e.g. 3 × 3; 5 × 5). A set of transition rules determines how the phenomenon develops over time (Wu and Webster 1998, Pan et al. 2010), and is fundamental for an appropriate model output and to determine how the CA interacts in space (White and Engelen 2000). Depending on the system development – the defined neighbors’ states and the respective rules – the state of the cells may change concurrently at each discrete time step (Spicer et al. 2012). Transition rules convey a kind of ‘what-if’ scenario in order to be able to see the evolvement of the phenomenon over time and across space. Thus, this technique takes into account local circumstances of individual cells as well as the global situation of cells throughout the entire system (Batty et al. 1999).

2. Materials and methods

2.1. Study area and data

For this study, Heidelberg, the fourth largest city of the Baden-Wuerttemberg state of Germany, was selected. The area of interest is shown in Figure 2, which covers the city of Heidelberg and its surrounding area.

Figure 2. Spatial extent of the study site, Heidelberg.

Justifications for choosing this study area are twofold: firstly, the selected study area has received substantial records of contributions, according to the OSMatrix (Roick, Hagenauer, and Zipf 2011); secondly, the study area consists of several land types, as shown in Figure 3. This land-use map distinguishes several land types, including transport units, water bodies, farming lands, industrial units, protected areas, urban fabrics, facilities, commercial units, leisure areas, and forests. The reason for considering land-use features is grounded on the assumption that the amount of contributions depends on the type of land that is being contributed by people. For example, urban fabrics contain more points of interest and features to be mapped than water bodies and natural features. Particularly, as noted by Neis and Zipf (2012), the latter is of major interest, because heterogeneous amounts of contributions to rural and urban areas have been received.

Figure 3. The land-use map of Heidelberg provided by ATKIS.

The data used in this investigation are the OSM nodes extracted from the OSM-dump file for August, 2012. Mapped objects in the OSM are represented as (1) a single node for point features (e.g. POIs), (2) a set of nodes illustrating a polyline (e.g. roads) or a polygon (e.g. buildings). Each single node is named as a contribution from a user and shared with OSM. Moreover, the land-use map of the study area provided by the Bundesamt für Kartographie und Geodäsie (BKG), derived from the ‘Amtliches Topographisch-Kartographisches Informationssystem’ (ATKIS) is available at a scale of 1:10,000.

2.2. CA-based modeling of OSM evolution

The entire process of contributing to OSM shapes a dynamic phenomenon, referred to as collaborative contributing, that has an explicit spatiotemporal evolution. Once one contribution is made by a user (i.e. a node is created), it is more likely that (1) he/she comes back and continues/finishes his/her contribution and the phenomenon spreads across the network, (2) a new contributor gets involved and starts completing the contribution of the previous contributor(s) by applying creation/edition/deletion actions, or finally, (3) as the process of contributing is continuous in time and space, the chances of receiving contributions from nearby cells are higher than from ones farther apart. Obviously, contributions are received at dissimilar rates for each area, and therefore, the rate of contributions depends on the quantity of existing objects and number of interested users. The rate of dynamism of this phenomenon varies depending on time and location. Thus, the OSM mapping process is taken as a space-time-dependent dynamic phenomenon whose evolution can be modeled by means of a CA. As a consequence, the contributions must be transferred to a grid representation. Based on this cell representation, CA modeling can be utilized to effectively analyze the emergence and evolution of the spatiotemporal collaborative contributions.

Subsequently, a cellular grid is generated at a spatial resolution of 50 m in which each cell covers 0.25 ha. In doing so, the finest possible resolution was selected to keep the computational tasks feasible while ensuring that morphological details (e.g. stream course of the Neckar) are retained. The cellular grid covers the study area with 14,456 pixels. Six timestamps from 22 July 2006, until 22 July 2012, with one-year sequences, are extracted to analyze trends in the mapping behavior of OSM contributors. At each timestamp, the cellular tessellation contains either non-contributed cells (values of 0) or contributed cells (values of 1; blue cells in Figure 6). Supported by empirical tests, the CA setup is based on a 3×3 neighborhood size applying von Neumann's neighborhood definition, as recommended by Pan et al. (2010). Next, the model calibration process is carried out to assure the performance of the model and to determine the most appropriate transition rules. The CA model was executed iteratively until the associated transition rules resulted in generating high correlated outputs compared to the actual reality represented through the latest available timestamp. As a correlation measure, the Kappa index is utilized. Finally, the best calibrated model is employed to simulate the upcoming contributions for the year 2014. Figure 4 summarizes the outlined workflow.

Figure 4. Schematic workflow of CA modeling.

3. Results and discussions

3.1. Descriptive spatiotemporal analysis

Initially, a spatial and temporal quantitative analysis on the amount of contributions is carried out to determine (1) how and where the collaborative contributing has emerged and evolved, (2) how the rate at which this phenomenon has disseminated, and (3) to investigate whether any relationship between the land-use patterns and the contributed cells can be discovered.

The results are as follows: within the first year (from 22 July 2006 to 22 July 2007), only seven cells covering leisure areas show OSM content gathered by three individuals, which is not substantial for one year. By July 2008, 808 cells are contributed by 15 users, representing 5.6% of the contributed cells. The contributions mainly form facilities and urban fabrics in which the campus of the University of Heidelberg is obvious. Gradually, an increasing trend of original contributions and new users becomes evident starting from 2009. Within 2009, a substantial number of contributions mainly covering urban fabrics, transport units, and commercial areas were received, which are 6637 nodes into 2436 cells by 55 contributors. 2010 shows a slower trend in attracting contributions at 9318 nodes into 3428 cells. This is only 40% more than the last timestamp. Within this year, 96 contributors shared their contributions. The pattern shapes mainly facilities and commercial units, but diffused cells are also noticeable. In 2011, a sharp increase is evident with a remarkable amount of contributions received: 38,536 nodes occupying 7614 cells by 148 volunteers. More importantly, within this period, more diffused cells in terms of spatial location are contributed, which form the city and lack of mappings of forests and farming lands. The last timestamp contains contributions from July 2011 to July 2012. Within this period, 53,680 nodes covering 8640 cells out of 14,456 cells are received, while 243 users contributed in this area. In comparison with 2012, in 2011, relatively more contributions were received, as only 13% more nodes were received within 2012. However, this is the case if we only consider the process of creation of objects, which is named ‘exploration’ by Corcoran, Mooney, and Bertolotto (2013). Furthermore, some cells might be under the densification (Corcoran, Mooney, and Bertolotto 2013) process and, therefore, they do not occupy new cells. To sum up, while Table 1 depicts the number of cells occupied by contributions for each timestamp, Figure 5 visualizes the temporal development.

Figure 5. Trends of OSM contributions (nodes).

Table 1. Summary of temporal trends of the contributors and their contributions.

	Year
	2007	2008	2009	2010	2011	2012
Number of contributed nodes	7	2266	6637	9318	38536	53680
Number of cells representing contributions	7	808	2436	3428	7614	8640
Average number of node per cell	7	2.8	2.7	2.7	5.1	6.2
Percentage of occupied cells	0.05	5.59	16.85	23.71	52.67	59.77
Number of contributors	3	15	55	96	148	243
Rate of Contributions (node/person)	2.3	53.9	44.3	35.7	51.4	35.6

As Figure 6 illustrates, by 2012, most of the cells were contributed with only a small number of cells (1348 cells) remaining to be contributed. However, the average number of nodes per cell has increased to the highest value. It must be mentioned that the remaining non-contributed cells cover natural features, such as farming lands and water bodies, where the geographical objects are not as dense as urban areas. Perhaps either these areas have not attracted people to contribute, or the existing features to be mapped are not dense enough to occupy a cell.

Figure 6. Spatio-temporal representation of contributions for each timestamp.

3.2. CA implementation and validation

In order to configure the simulation process, the three timestamps – 2009, 2010, and 2011 – are selected to calibrate the model using the setting outlined in Section 2.2. For each simulation run, the model is iterated 10 times. According to Table 2, representing the reaction of the model to the number of iterations as well as the input timestamp, the future contributions can be best predicted with the latest timestamp at certain iterations. By inputting the 2009 map, the model predicts the contributions of 2010 at an overall Kappa index of 83.72% agreement. The highest Kappa index for prediction of 2011, based on 2010, is gained at 41.7%. The reason for the low coincidence is the fact that the process of contribution changes very quickly over time, and long-term predictions cannot be made as the densification process is being spread and many areas have already been discovered in the exploration process. The model predicts the contributions in 2012 at the fourth iteration with a Kappa index of 83.36% agreement. This implies that, for OSM evolution, the most accurate result can be achieved if the latest timestamp is used to run the simulation.

Table 2. CA calibration results for several iterations and different years.

Base time stamp	2009			2010		2011
Predicted year	2010	2011	2012	2011	2012	2012
Iteration 1	83.48	28.31	15.3	42.03	29.44	82.69
Iteration 2	84.01	27.92	15	41.66	29.21	83.37
Iteration 3	83.69	27.82	15.18	41.56	29.36	83.19
Iteration 4	83.72	27.88	15.23	41.67	29.5	83.36
Iteration 5	83.72	27.93	15.32	41.67	29.52	83.33
Iteration 6	83.69	27.93	15.34	41.7	29.58	83.33	Kappa index %
Iteration 7	83.66	27.96	15.37	41.71	29.59	83.33
Iteration 8	83.66	27.96	15.37	41.7	29.58	83.33
Iteration 9	83.66	27.96	15.37	41.7	29.58	83.33
Iteration 10	83.66	27.96	15.37	41.7	29.58	83.33

3.3. Prediction

Next, the calibrated CA model is applied for predicting future OSM states for the year of 2014, utilizing similar transition rules which have maximized the Kappa index. The map of 2012 was imported to the model as a base timestamp and iterated four times to predict the contributions of 2014. Figure 7 illustrates the spatial distribution of potential upcoming contributions.

Figure 7. CA prediction for 2014.

Based on a visual analysis, as well as overlying the land-use map, the predicted contributions will cover all of the urban fabrics. This means the exploration process in urban areas is finished. Nonetheless, the results reveal that farming lands will not be further mapped, perhaps, because this land-use type is not interesting enough to attract people to mapping. However, since OSM-nodes are taken as footprints of contributions, only the edges of farming lands (i.e. features represented as polygons) are considered, and the covered area by polygons are not considered. According to Figure 7, 9,395 cells will be contributed by 2014. However, due to the inherent nature of CA models and the associated transition rules, as well as the number of iterations, the nearby cells are more likely to be contributed, while in reality, individuals are behind this phenomenon and might not necessarily act as continuous phenomena do. Besides, certain other physical and socioeconomic variables are involved in receiving contributions, which are not considered in simple CA models.

4. Conclusions

The main objective of this study was to monitor the process of collaborative contribution to the OSM project spatially and temporally for the city of Heidelberg, Germany, in order to provide insights about the future of OSM. The footprints of contributions were projected onto a spatiotemporal framework, and a CA model was implemented to simulate future OSM states, permitting us to analyze the OSM mapping process from a thus far neglected perspective. To the best of the authors’ knowledge, this is the first study using past spatiotemporal development trends to predict upcoming contributions.

This research enhances the literature on OSM in several ways. Firstly, the analysis reveals that an insignificant amount of contributions were received nearly three years (i.e. 2007) after launching the OSM project in 2004. Four years after, in 2011, the whole area was explored by 338 mappers, and afterward the area has been under the densification process. Secondly, spatial and temporal dependency between the amount of contributions and physical characteristics are existent as proven by analyzing land use patterns (Jokar Arsanjani et al. 2013c). Land-use types, such as transport units, leisure facilities, urban fabrics, commercial units, and forest areas, are of high interest for mappers in OSM. The results show that, until 2014, contributions on all of the urban fabrics will be received and land-use types such as farming lands, water bodies, and forest receive the least amount of contribution, because (1) the objects in such land-types are not dense, (2) less people are interactively involved with these features types, (3) these land types change very slowly over time, and (4) there is not too much information about these objects, while more attributes on urban fabrics and their contents can be contributed.

Even though the empirical results are limited to a specific area, the findings prove that the contributions are dependent on some socio-economic and physical factors. As an example, the earliest and the most prevalent contributions were received on urban fabrics and primarily on the university campus area, where education is taking place and educated people are connected to this place. This might be due to high and unlimited accessibility to Internet infrastructures by people who are very up-to-date with recent technological developments. Instead, farming lands and water bodies receive contributions later than other features. Thus, it is of importance to investigate their relationship to the dissemination of this contribution phenomenon for future work. It is concluded that there is a correlation between land-use features and density of contributions. However, the individuals, as mappers, are also a key feature affecting the degree and type of contributions. As OSM and similar projects are growing and being disseminated exceptionally fast, further studies on discovering the behavior of individuals in collaborative projects can help to explore which factors and parameters influence the receiving of people's information. Certainly, this approach helps to have a better perspective on how long it takes people to map a specific area and how well planners can rely on individuals in a mapping call. Whereas individuals are the main actors in such a phenomenon, agent-based modeling might also be an alternative technique to simulate this phenomenon, which must be evaluated in this respect. Hence, OSM remains a highly vibrant research domain.

Acknowledgments

Jamal Jokar Arsanjani gratefully acknowledge the financial support from the Alexander von Humboldt Foundation. Additionally, the authors would like to thank the three anonymous reviewers and the editor for their useful and constructive comments.