ABSTRACT
The Doubly Connected Edge List (DCEL) is an edge-list structure that has been widely utilized in spatial applications for planar topological computations. An important operation is the overlay which combines the DCELs of two input layers and can easily support spatial queries like the intersection, union and difference between these layers. However, existing sequential implementations for computing the overlay do not scale and fail to complete for large datasets (for example the US census tracks). In this paper we propose a distributed and scalable way to compute the overlay operation and its related supported queries. We address the issues involved in efficiently distributing the overlay operator and over various optimizations that improve performance. Our scalable solution can compute the overlay of very large real datasets (32M edges) in few minutes.
more »
« less
This content will become publicly available on July 1, 2024
DDCEL: Efficient Distributed Doubly Connected Edge List for Large Spatial Networks
Abstract—The Doubly Connected Edge List (DCEL) is a popular data structure for representing planar subdivisions and is used to accelerate spatial applications like map overlay, graph simplification, and subdivision traversal. Current DCEL imple- mentations assume a standalone machine environment, which does not scale when processing the large dataset sizes that abound in today’s spatial applications. This paper proposes a Distributed Doubly Connected Edge List (DDCEL) data structure extending the DCEL to a distributed environment. The DDCEL constructor undergoes a two-phase paradigm to generate the subdivision’s vertices, half-edges, and faces. After spatially partitioning the input data, the first phase runs the sequential DCEL construction algorithm on each data partition in parallel. The second phase then iteratively merges information from multiple data parti- tions to generate the shared data structure. Our experimental evaluation with real data of road networks of up to 563 million line segments shows significant performance advantages of the proposed approach over the existing techniques.
more »
« less
- NSF-PAR ID:
- 10476566
- Publisher / Repository:
- IEEE
- Date Published:
- Journal Name:
- IEEE International Conference on Mobile Data Management (MDM)
- ISSN:
- 2375-0324
- Page Range / eLocation ID:
- 122 to 131
- Subject(s) / Keyword(s):
- ["DCEL","Distributed","Polygonization"]
- Format(s):
- Medium: X
- Location:
- Singapore, Singapore
- Sponsoring Org:
- National Science Foundation
More Like this
-
-
more » « less
Abstract Tropical floodplains secure the protein supply of millions of people, but only sound management can ensure the long‐term continuity of such ecosystem services. Overfishing is a widespread threat to multitrophic systems, but how it affects ecosystem functioning is poorly understood, particularly in tropical freshwater food webs. Models based on temperate lakes frequently assume that primary producers are mostly bottom‐up controlled by nutrient and light limitations, with negligible effects of top‐down forces. Yet this assumption remains untested in complex tropical freshwater systems experiencing marked spatiotemporal variation.
We use consolidated community‐based fisheries management practices and spatial zoning to test the relative importance of bottom‐up versus top‐down drivers of phytoplankton biomass, controlling for the influence of local to landscape heterogeneity. Our study focuses on 58 large Amazonian floodplain lakes under different management regimes that resulted in a gradient of apex‐predator abundance. These lakes, distributed along ~600 km of a major tributary of the Amazon River, varied widely in size, structure, landscape context, and hydrological seasonality.
Using generalised linear models, we show that community‐based fisheries management, which controls the density of apex predators, is the strongest predictor of phytoplankton biomass during the dry season, when lakes become discrete landscape units. Water transparency also emerges as an important bottom‐up factor, but phosphorus, nitrogen and several lake and landscape metrics had minor or no effects on phytoplankton biomass. During the wet‐season food pulse, when lakes become connected to adjacent water bodies and homogenise the landscape, only lake depth explained phytoplankton biomass.
Synthesis and applications . Tropical freshwaters fisheries typically assume that fish biomass is controlled by bottom‐up mechanisms, so that overexploitation of large predators would not affect overall ecosystem productivity. Our results, however, show that top‐down forces are important drivers of primary productivity in tropical lakes, above and beyond the effects of bottom‐up factors. This helps us to understand the enormous success of community‐based ‘fishing agreements’ in the Amazon. Multiple stakeholders should embrace socio‐ecological management practices that shape both bottom‐up and top‐down forces to ensure biodiversity protection, sustainable fisheries yields and food security for local communities and regional economies. -
null (Ed.)With the explosion in Big Data, it is often forgotten that much of the data nowadays is generated at the edge. Specifically, a major source of data is users' endpoint devices like phones, smart watches, etc., that are connected to the internet, also known as the Internet-of-Things (IoT). This "edge of data" faces several new challenges related to hardware-constraints, privacy-aware learning, and distributed learning (both training as well as inference). So what systems and machine learning algorithms can we use to generate or exploit data at the edge? Can network science help us solve machine learning (ML) problems? Can IoT-devices help people who live with some form of disability and many others benefit from health monitoring? In this tutorial, we introduce the network science and ML techniques relevant to edge computing, discuss systems for ML (e.g., model compression, quantization, HW/SW co-design, etc.) and ML for systems design (e.g., run-time resource optimization, power management for training and inference on edge devices), and illustrate their impact in addressing concrete IoT applications.more » « less
-
more » « less
Key points The functional neuroanatomy of the mammalian respiratory network is far from being understood since experimental tools that measure neural activity across this brainstem‐wide circuit are lacking.
Here, we use silicon multi‐electrode arrays to record respiratory local field potentials (rLFPs) from 196–364 electrode sites within 8–10 mm3of brainstem tissue in single arterially perfused brainstem preparations with respect to the ongoing respiratory motor pattern of inspiration (I), post‐inspiration (PI) and late‐expiration (E2).
rLFPs peaked specifically at the three respiratory phase transitions, E2–I, I–PI and PI–E2.
We show, for the first time, that only the I–PI transition engages a brainstem‐wide network, and that rLFPs during the PI–E2 transition identify a hitherto unknown role for the dorsal respiratory group.
Volumetric mapping of pontomedullary rLFPs in single preparations could become a reliable tool for assessing the functional neuroanatomy of the respiratory network in health and disease.
Abstract While it is widely accepted that inspiratory rhythm generation depends on the pre‐Bötzinger complex, the functional neuroanatomy of the neural circuits that generate expiration is debated. We hypothesized that the compartmental organization of the brainstem respiratory network is sufficient to generate macroscopic local field potentials (LFPs), and if so, respiratory (r) LFPs could be used to map the functional neuroanatomy of the respiratory network. We developed an approach using silicon multi‐electrode arrays to record spontaneous LFPs from hundreds of electrode sites in a volume of brainstem tissue while monitoring the respiratory motor pattern on phrenic and vagal nerves in the perfused brainstem preparation. Our results revealed the expression of rLFPs across the pontomedullary brainstem. rLFPs occurred specifically at the three transitions between respiratory phases: (1) from late expiration (E2) to inspiration (I), (2) from I to post‐inspiration (PI), and (3) from PI to E2. Thus, respiratory network activity was maximal at respiratory phase transitions. Spatially, the E2–I, and PI–E2 transitions were anatomically localized to the ventral and dorsal respiratory groups, respectively. In contrast, our data show, for the first time, that the generation of controlled expiration during the post‐inspiratory phase engages a distributed neuronal population within ventral, dorsal and pontine network compartments. A group‐wise independent component analysis demonstrated that all preparations exhibited rLFPs with a similar temporal structure and thus share a similar functional neuroanatomy. Thus, volumetric mapping of rLFPs could allow for the physiological assessment of global respiratory network organization in health and disease.
-
more » « less
Confining proteins in synthetic nanoscale spatial compartments has offered a cell-free avenue to understand enzyme structure–function relationships and complex cellular processes near the physiological conditions, an important branch of fundamental protein biophysics studies. Enzyme confinement has also provided advancement in biocatalysis by offering enhanced enzyme reusability, cost-efficiency, and substrate selectivity in certain cases for research and industrial applications. However, the primary research efforts in this area have been focused on the development of novel confinement materials and investigating protein adsorption/interaction with various surfaces, leaving a fundamental knowledge gap, namely, the lack of understanding of the confined enzymes (note that enzyme adsorption to or interactions with surfaces differs from enzyme confinement as the latter offers an enhanced extent of restriction to enzyme movement and/or conformational flexibility). In particular, there is limited understanding of enzymes' structure, dynamics, translocation (into biological pores), folding, and aggregation in extreme cases upon confinement, and how confinement properties such as the size, shape, and rigidity affect these details. The first barrier to bridge this gap is the difficulty in “penetrating” the “shielding” of the confinement walls experimentally; confinement could also lead to high heterogeneity and dynamics in the entrapped enzymes, challenging most protein-probing experimental techniques. The complexity is raised by the variety in the possible confinement environments that enzymes may encounter in nature or on lab benches, which can be categorized to rigid confinement with regular shapes, rigid restriction without regular shapes, and flexible/dynamic confinement which also introduces crowding effects. Thus, to bridge such a knowledge gap, it is critical to combine advanced materials and cutting-edge techniques to re-create the various confinement conditions and understand enzymes therein. We have spearheaded in this challenging area by creating various confinement conditions to restrict enzymes while exploring experimental techniques to understand enzyme behaviors upon confinement at the molecular/residue level. This review is to summarize our key findings on the molecular level details of enzymes confined in (i) rigid compartments with regular shapes based on pre-formed, mesoporous nanoparticles and Metal–Organic Frameworks/Covalent-Organic Frameworks (MOFs/COFs), (ii) rigid confinement with irregular crystal defects with shapes close to the outline of the confined enzymes via co-crystallization of enzymes with certain metal ions and ligands in the aqueous phase (biomineralization), and (iii) flexible, dynamic confinement created by protein-friendly polymeric materials and assemblies. Under each case, we will focus our discussion on (a) the way to load enzymes into the confined spaces, (b) the structural basis of the function and behavior of enzymes within each compartment environments, and (c) technical advances of our methodology to probe the needed structural information. The purposes are to depict the chemical physics details of enzymes at the challenging interface of natural molecules and synthetic compartment materials, guide the selection of enzyme confinement platforms for various applications, and generate excitement in the community on combining cutting-edge technologies and synthetic materials to better understand enzyme performance in biophysics, biocatalysis, and biomedical applications.
