skip to main content


Title: Comparing Directed and Weighted Road Maps
With the increasing availability of GPS trajectory data, map construction algorithms have been developed that automatically construct road maps from this data. In order to assess the quality of such (constructed) road maps, the need for meaningful road map comparison algorithms becomes increasingly important. Indeed, different approaches for map comparison have been recently proposed; however, most of these approaches assume that the road maps are modeled as undirected embedded planar graphs. In this paper, we study map comparison algorithms for more realistic models of road maps: directed roads as well as weighted roads. In particular, we address two main questions: how close are the graphs to each other, and how close is the information presented by the graphs (i.e., traffic times, trajectories, and road type)? We propose new road network comparisons and give illustrative examples. Furthermore, our approaches do not only apply to road maps but can be used to compare other kinds of graphs as well.  more » « less
Award ID(s):
1618605
NSF-PAR ID:
10182068
Author(s) / Creator(s):
; ; ; ; ; ; ; ;
Date Published:
Journal Name:
Association for Women in Mathematics series
Volume:
13
ISSN:
2364-5733
Page Range / eLocation ID:
57-70
Format(s):
Medium: X
Sponsoring Org:
National Science Foundation
More Like this
  1. Abstract

    Proximity to roads is one of the main determinants of deforestation in the Amazon basin. Determining the construction year of roads (CYR) is critical to improve the understanding of the drivers of road construction and to enable predictions of the expansion of the road network and its consequent impact on ecosystems. While recent artificial intelligence approaches have been successfully used for road extraction, they have typically relied on high spatial‐resolution imagery, precluding their adoption for the determination of CYR for older roads. In this article, we developed a new approach to automate the process of determining CYR that relies on the approximate position of the current road network and a time‐series of the proportion of exposed soil based on the multidecadal remote sensing imagery from the Landsat program. Starting with these inputs, our methodology relies on the Least Cost Path algorithm to co‐register the road network and on a Before‐After Control‐Impact design to circumvent the inherent image‐to‐image variability in the estimated amount of exposed soil. We demonstrate this approach for a 357 000 km2area around the Transamazon highway (BR‐230) in the Brazilian Amazon, encompassing 36 240 road segments. The reliability of this approach is assessed by comparing the estimated CYR using our approach to the observed CYR based on a time‐series of Landsat images. This exercise reveals a close correspondence between the estimated and observed CYR (). Finally, we show how these data can be used to assess the effectiveness of protected areas (PAs) in reducing the yearly rate of road construction and thus their vulnerability to future degradation. In particular, we find that integral protection PAs in this region were generally more effective in reducing the expansion of the road network when compared to sustainable use PAs.

     
    more » « less
  2. We propose a new approach for constructing the underlying map from trajectory data. Our algorithm is based on the idea that road segments can be identified as stable subtrajectory clusters in the data. For this, we consider how subtrajectory clusters evolve for varying distance values, and choose stable values for these. In doing so we avoid a global proximity parameter. Within trajectory clusters, we choose representatives, which are combined to form the map. We experimentally evaluate our algorithm on vehicle and hiking tracking data. These experiments demonstrate that our approach can naturally separate roads that run close to each other and can deal with outliers in the data, two issues that are notoriously difficult in road network reconstruction. 
    more » « less
  3. The development of the transport network affects the socio-economic development of the territory and it is one of the most important factors in the growth of the level and quality of the population life. There is the need for a study of transport accessibility. In our work, we presented the mapping and assessment of changes in transport accessibility after the construction of service road. After the construction of the ESPO pipeline, a service road was built along it to maintenance the pipeline, which is located close to the district centers and crosses the local roads. This new road connected them into one network with year-round traffic. The object of our research is the Area of Oil and Gas Extraction in the Republic of Sakha (Yakutia) and the North Irkutsk region.We have created transport accessibility maps with and without all service roads, separately for winter and summer seasons. We have created maps for several district centers. We calculated transport accessibility using the method of constructing isochrones — lines of equal travel time to overcome the space relative to given points, using open GIS GRASS GIS. After construction, the company owner of this road gives permission to the municipal and federal services and local population use for free, but a preliminary application is required. There is a payment requirement and compliance with restrictions for transportation of commercial goods. After the construction of the ESPO pipeline, people who live close to the pipeline can reach to the district centers and neighboring districts by car year-round theoretically. The materials of this study can be useful in calculating the travel time on these roads, and finding priority areas for the construction of new roads. 
    more » « less
  4. Abstract

    As microbiome research has progressed, it has become clear that most, if not all, eukaryotic organisms are hosts to microbiomes composed of prokaryotes, other eukaryotes, and viruses. Fungi have only recently been considered holobionts with their own microbiomes, as filamentous fungi have been found to harbor bacteria (including cyanobacteria), mycoviruses, other fungi, and whole algal cells within their hyphae. Constituents of this complex endohyphal microbiome have been interrogated using multi-omic approaches. However, a lack of tools, techniques, and standardization for integrative multi-omics for small-scale microbiomes (e.g., intracellular microbiomes) has limited progress towards investigating and understanding the total diversity of the endohyphal microbiome and its functional impacts on fungal hosts. Understanding microbiome impacts on fungal hosts will advance explorations of how “microbiomes within microbiomes” affect broader microbial community dynamics and ecological functions. Progress to date as well as ongoing challenges of performing integrative multi-omics on the endohyphal microbiome is discussed herein. Addressing the challenges associated with the sample extraction, sample preparation, multi-omic data generation, and multi-omic data analysis and integration will help advance current knowledge of the endohyphal microbiome and provide a road map for shrinking microbiome investigations to smaller scales.

     
    more » « less
  5. Abstract Background

    Advances in imagery at atomic and near-atomic resolution, such as cryogenic electron microscopy (cryo-EM), have led to an influx of high resolution images of proteins and other macromolecular structures to data banks worldwide. Producing a protein structure from the discrete voxel grid data of cryo-EM maps involves interpolation into the continuous spatial domain. We present a novel data format called the neural cryo-EM map, which is formed from a set of neural networks that accurately parameterize cryo-EM maps and provide native, spatially continuous data for density and gradient. As a case study of this data format, we create graph-based interpretations of high resolution experimental cryo-EM maps.

    Results

    Normalized cryo-EM map values interpolated using the non-linear neural cryo-EM format are more accurate, consistently scoring less than 0.01 mean absolute error, than a conventional tri-linear interpolation, which scores up to 0.12 mean absolute error. Our graph-based interpretations of 115 experimental cryo-EM maps from 1.15 to 4.0 Å resolution provide high coverage of the underlying amino acid residue locations, while accuracy of nodes is correlated with resolution. The nodes of graphs created from atomic resolution maps (higher than 1.6 Å) provide greater than 99% residue coverage as well as 85% full atomic coverage with a mean of 0.19 Å root mean squared deviation. Other graphs have a mean 84% residue coverage with less specificity of the nodes due to experimental noise and differences of density context at lower resolutions.

    Conclusions

    The fully continuous and differentiable nature of the neural cryo-EM map enables the adaptation of the voxel data to alternative data formats, such as a graph that characterizes the atomic locations of the underlying protein or macromolecular structure. Graphs created from atomic resolution maps are superior in finding atom locations and may serve as input to predictive residue classification and structure segmentation methods. This work may be generalized to transform any 3D grid-based data format into non-linear, continuous, and differentiable format for downstream geometric deep learning applications.

     
    more » « less