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
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
- ISBN:
- 979-8-3503-4101-0
- 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
-
-
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
-
The rapid growth in technology and wide use of internet has increased smart applications such as intelligent transportation control system, and Internet of Things, which heavily rely on an efficient and reliable connectivity network. To overcome high bandwidth work load on the network, as well as minimize latency for real-time applications, the computation can be moved from the central cloud to a distributed edge cloud. The edge computing benefits various smart applications that uses distributed network for data analytics and services. Different from the existing cloud management solutions, edge computing needs to move cloud management services towards distributed heterogeneous edge nodes for multi-tenant user applications. However, existing cloud management services do not offer remote deployment of multi-tenant user applications on the cloud of edge nodes. In this paper, we propose a practical edge cloud software framework for deploying multi-tenant distributed smart applications. Having multiple distributed end nodes, auto discovery of all active end nodes is required for deploying multi-tenant user applications. However, existing cloud solutions require either private network or fixed IP address, which is not achievable for the distributed edge nodes. Most of the edge nodes connected through the public internet without fixed IP, and some of them even connect through IEEE 802.15 based sensor networks. We propose to build a software platform to manage the distributed edge nodes as well as support services to deploy and launch isolated, multi-tenant user applications through a lightweight container. We propose an architectural solution to remotely access edge cloud management services through intermittent internet connections. We open sourced our whole set of software solutions, and analyzed the major performance metrics of the edge cloud platform.more » « less
-
more » « less
Abstract Reliable simulations of molecules in condensed phase require the combination of an accurate quantum mechanical method for the core region, and a realistic model to describe the interaction with the environment. Additionally, this combination should not significantly increase the computational cost of the calculation compared to the corresponding in vacuo case. In this review, we describe the combination of methods based on coupled cluster (CC) theory with polarizable classical models for the environment. We use the polarizable continuum model (PCM) of solvation to discuss the equations, but we also show how the same theoretical framework can be extended to polarizable force fields. The theory is developed within the perturbation theory energy and singles‐T density (PTES) scheme, where the environmental response is computed with the CC single excitation amplitudes as an approximation for the full one‐particle reduced density. The CC‐PTES combination provides the best compromise between accuracy and computational effort for CC calculations in condensed phase, because it includes the response of the environment to the correlation density at the same computational cost of in vacuo CC. We discuss a number of numerical applications for ground and excited state properties, based on the implementation of CC‐PTES with single and double excitations (CCSD‐PTES), which show the reliability and computational efficiency of the method in reproducing experimental or full‐CC data.
This article is characterized under:
Electronic Structure Theory > Ab Initio Electronic Structure Methods
Electronic Structure Theory > Combined QM/MM Methods
Software > Quantum Chemistry
-
Edge computing is a distributed computing paradigm that moves data-intensive applications and services (e.g., AI) closer to the data source. The rapid growth of edge endpoints connected to the Internet today poses several challenges in scalable application life cycle management. That is, managing data and workloads on several thousand, up to millions of edge endpoints, challenged by limited connectivity, resource constraints, network and edge endpoint failures. In this work, we present EdgeRDV, a new edge abstraction that builds on the idea of rendezvous nodes to manage edge workloads at scale. The EdgeRDV architecture is comprised of a central cloud management endpoint (or cloud hub), a central gateway for each edge site (or edge hub), redundant gateways (or rendezvous nodes), and edge endpoints. Beyond its scalable architecture, EdgeRDV presents new techniques and algorithms that address single points of failures and provide adjustable levels of resilience and cost-effectiveness in edge network deployments. We conducted preliminary experiments to evaluate EdgeRDV, through simulations, and our results show that EdgeRDV requires one to three orders of magnitude fewer intermediate nodes compared to relay structures, can gracefully adapt to failures, and requires a constant number of messages during failure recovery in edge sites with up to 667K+ edge endpoints.more » « less
- Free Publicly Accessible Full Text
-
Accepted Manuscript1.0
- Conference Paper:
- https://doi.org/10.1109/MDM58254.2023.00029
