Social networks for volunteered geographic information - A case study of OpenStreetMap

The world of mapping has changed. Earlier, only professional experts were responsible for map production, but today ordinary people without any training or experience can become map-makers. The number of online mapping sites, and the number of volunteer mappers has increased significantly. The development of the technology, such as satellite navigation systems, Web 2.0, broadband Internet connections, and smartphones, have had one of the key roles in enabling the rise of volunteered geographic information (VGI). As opening governmental data to public is a current topic in many countries, the opening of high quality geographical data has a central role in this study. The aim of this study is to investigate how is the quality of spatial data produced by volunteers by comparing it with the map data produced by public authorities, to follow what occurs when spatial data are opened for users, and to get acquainted with the user profile of these volunteer mappers. A central part of this study is OpenStreetMap project (OSM), which aim is to create a map of the entire world by volunteers. Anyone can become an OpenStreetMap contributor, and the data created by the volunteers are free to use for anyone without restricting copyrights or license charges. In this study OpenStreetMap is investigated from two viewpoints. In the first part of the study, the aim was to investigate the quality of volunteered geographic information. A pilot project was implemented by following what occurs when a high-resolution aerial imagery is released freely to the OpenStreetMap contributors. The quality of VGI was investigated by comparing the OSM datasets with the map data of The National Land Survey of Finland (NLS). The quality of OpenStreetMap data was investigated by inspecting the positional accuracy and the completeness of the road datasets, as well as the differences in the attribute datasets between the studied datasets. Also the OSM community was under analysis and the development of the map data of OpenStreetMap was investigated by visual analysis. The aim of the second part of the study was to analyse the user profile of OpenStreetMap contributors, and to investigate how the contributors act when collecting data and editing OpenStreetMap. The aim was also to investigate what motivates users to map and how is the quality of volunteered geographic information envisaged. The second part of the study was implemented by conducting a web inquiry to the OpenStreetMap contributors. The results of the study show that the quality of OpenStreetMap data compared with the data of National Land Survey of Finland can be defined as good. OpenStreetMap differs from the map of National Land Survey especially because of the amount of uncertainty, for example because of the completeness and uniformity of the map are not known. The results of the study reveal that opening spatial data increased notably the amount of the data in the study area, and both the positional accuracy and completeness improved significantly. The study confirms the earlier arguments that only few contributors have created the majority of the data in OpenStreetMap. The inquiry made for the OpenStreetMap users revealed that the data are most often collected by foot or by bicycle using GPS device, or by editing the map with the help of aerial imageries. According to the responses, the users take part to the OpenStreetMap project because they want to make maps better, and want to produce maps, which have information that is up-to-date and cannot be found from any other maps. Almost all of the users exploit the maps by themselves, most popular methods being downloading the map into a navigator or into a mobile device. The users regard the quality of OpenStreetMap as good, especially because of the up-to-dateness and the accuracy of the map.

Fast distributed approximation algorithms for vertex cover and set cover in anonymous networks

We present a distributed algorithm that finds a maximal edge packing in O(Δ + log* W) synchronous communication rounds in a weighted graph, independent of the number of nodes in the network; here Δ is the maximum degree of the graph and W is the maximum weight. As a direct application, we have a distributed 2-approximation algorithm for minimum-weight vertex cover, with the same running time. We also show how to find an f-approximation of minimum-weight set cover in O(f2k2 + fk log* W) rounds; here k is the maximum size of a subset in the set cover instance, f is the maximum frequency of an element, and W is the maximum weight of a subset. The algorithms are deterministic, and they can be applied in anonymous networks.

Optimisation problems in wireless sensor networks

This thesis studies optimisation problems related to modern large-scale distributed systems, such as wireless sensor networks and wireless ad-hoc networks. The concrete tasks that we use as motivating examples are the following: (i) maximising the lifetime of a battery-powered wireless sensor network, (ii) maximising the capacity of a wireless communication network, and (iii) minimising the number of sensors in a surveillance application. A sensor node consumes energy both when it is transmitting or forwarding data, and when it is performing measurements. Hence task (i), lifetime maximisation, can be approached from two different perspectives. First, we can seek for optimal data flows that make the most out of the energy resources available in the network; such optimisation problems are examples of so-called max-min linear programs. Second, we can conserve energy by putting redundant sensors into sleep mode; we arrive at the sleep scheduling problem, in which the objective is to find an optimal schedule that determines when each sensor node is asleep and when it is awake. In a wireless network simultaneous radio transmissions may interfere with each other. Task (ii), capacity maximisation, therefore gives rise to another scheduling problem, the activity scheduling problem, in which the objective is to find a minimum-length conflict-free schedule that satisfies the data transmission requirements of all wireless communication links. Task (iii), minimising the number of sensors, is related to the classical graph problem of finding a minimum dominating set. However, if we are not only interested in detecting an intruder but also locating the intruder, it is not sufficient to solve the dominating set problem; formulations such as minimum-size identifying codes and locating–dominating codes are more appropriate. This thesis presents approximation algorithms for each of these optimisation problems, i.e., for max-min linear programs, sleep scheduling, activity scheduling, identifying codes, and locating–dominating codes. Two complementary approaches are taken. The main focus is on local algorithms, which are constant-time distributed algorithms. The contributions include local approximation algorithms for max-min linear programs, sleep scheduling, and activity scheduling. In the case of max-min linear programs, tight upper and lower bounds are proved for the best possible approximation ratio that can be achieved by any local algorithm. The second approach is the study of centralised polynomial-time algorithms in local graphs – these are geometric graphs whose structure exhibits spatial locality. Among other contributions, it is shown that while identifying codes and locating–dominating codes are hard to approximate in general graphs, they admit a polynomial-time approximation scheme in local graphs.

Discriminative learning of Bayesian networks via factorized conditional log-likelihood

We propose an efficient and parameter-free scoring criterion, the factorized conditional log-likelihood (ˆfCLL), for learning Bayesian network classifiers. The proposed score is an approximation of the conditional log-likelihood criterion. The approximation is devised in order to guarantee decomposability over the network structure, as well as efficient estimation of the optimal parameters, achieving the same time and space complexity as the traditional log-likelihood scoring criterion. The resulting criterion has an information-theoretic interpretation based on interaction information, which exhibits its discriminative nature. To evaluate the performance of the proposed criterion, we present an empirical comparison with state-of-the-art classifiers. Results on a large suite of benchmark data sets from the UCI repository show that ˆfCLL-trained classifiers achieve at least as good accuracy as the best compared classifiers, using significantly less computational resources.

Identification of collagenolytic MMP networks as potential biomarkers in progressive chronic periodontitis subjects and MMP-8 null allele model

Chronic periodontitis results from a complex aetiology, including the formation of a subgingival biofilm and the elicitation of the host s immune and inflammatory response. The hallmark of chronic periodontitis is alveolar bone loss and soft periodontal tissue destruction. Evidence supports that periodontitis progresses in dynamic states of exacerbation and remission or quiescence. The major clinical approach to identify disease progression is the tolerance method, based on sequential probing. Collagen degradation is one of the key events in periodontal destructive lesions. Matrix metalloproteinase (MMP)-8 and MMP-13 are the primary collagenolytic MMPs that are associated with the severity of periodontal inflammation and disease, either by a direct breakdown of the collagenised matrix or by the processing of non-matrix bioactive substrates. Despite the numerous host mediators that have been proposed as potential biomarkers for chronic periodontitis, they reflect inflammation rather than the loss of periodontal attachment. The aim of the present study was to determine the key molecular MMP-8 and -13 interactions in gingival crevicular fluid (GCF) and gingival tissue from progressive periodontitis lesions and MMP-8 null allele mouse model. In study (I), GCF and gingival biopsies from active and inactive sites of chronic periodontitis patients, which were determined clinically by the tolerance method, and healthy GCF were analysed for MMP-13 and tissue inhibitor of matrix metalloproteinases (TIMP)-1. Chronic periodontitis was characterised by increased MMP-13 levels and the active sites showed a tendency of decreased TIMP-1 levels associated with increments of MMP-13 and total protein concentration compared to inactive sites. In study (II), we investigated whether MMP-13 activity was associated with TIMP-1, bone collagen breakdown through ICTP levels, as well as the activation rate of MMP-9 in destructive lesions. The active sites demonstrated increased GCF ICTP levels as well as lowered TIMP-1 detection along with elevated MMP-13 activity. MMP-9 activation rate was enhanced by MMP-13 in diseased gingival tissue. In study (III), we analysed the potential association between the levels, molecular forms, isoenzyme distribution and degree of activation of MMP-8, MMP-14, MPO and the inhibitor TIMP-1 in GCF from periodontitis progressive patients at baseline and after periodontal therapy. A positive correlation was found for MPO/MMP-8 and their levels associated with progression episodes and treatment response. Because MMP-8 is activated by hypochlorous acid in vitro, our results suggested an interaction between the MPO oxidative pathway and MMP-8 activation in GCF. Finally, in study (IV), on the basis of the previous finding that MMP-8-deficient mice showed impaired neutrophil responses and severe alveolar bone loss, we aimed to characterise the detection patterns of LIX/CXCL5, SDF-1/CXCL12 and RANKL in P. gingivalis-induced experimental periodontitis and in the MMP-8-/- murine model. The detection of neutrophil-chemoattractant LIX/CXCL5 was restricted to the oral-periodontal interface and its levels were reduced in infected MMP-8 null mice vs. wild type mice, whereas the detection of SDF-1/CXCL12 and RANKL in periodontal tissues increased in experimentally-induced periodontitis, irrespectively from the genotype. Accordingly, MMP-8 might regulate LIX/CXCL5 levels by undetermined mechanisms, and SDF-1/CXCL12 and RANKL might promote the development and/or progression of periodontitis.

Algorithms for Exact Structure Discovery in Bayesian Networks

Bayesian networks are compact, flexible, and interpretable representations of a joint distribution. When the network structure is unknown but there are observational data at hand, one can try to learn the network structure. This is called structure discovery. This thesis contributes to two areas of structure discovery in Bayesian networks: space--time tradeoffs and learning ancestor relations. The fastest exact algorithms for structure discovery in Bayesian networks are based on dynamic programming and use excessive amounts of space. Motivated by the space usage, several schemes for trading space against time are presented. These schemes are presented in a general setting for a class of computational problems called permutation problems; structure discovery in Bayesian networks is seen as a challenging variant of the permutation problems. The main contribution in the area of the space--time tradeoffs is the partial order approach, in which the standard dynamic programming algorithm is extended to run over partial orders. In particular, a certain family of partial orders called parallel bucket orders is considered. A partial order scheme that provably yields an optimal space--time tradeoff within parallel bucket orders is presented. Also practical issues concerning parallel bucket orders are discussed. Learning ancestor relations, that is, directed paths between nodes, is motivated by the need for robust summaries of the network structures when there are unobserved nodes at work. Ancestor relations are nonmodular features and hence learning them is more difficult than modular features. A dynamic programming algorithm is presented for computing posterior probabilities of ancestor relations exactly. Empirical tests suggest that ancestor relations can be learned from observational data almost as accurately as arcs even in the presence of unobserved nodes.