More Like this

1. DART: A Scalable and Adaptive Edge Stream Processing Engine

   Liu, Pinchao ; Da Silva, Dilma ; Hu, Liting ( July 2021 , USENIX Annual Technical Conference)

   null (Ed.)

   Many Internet of Things (IoT) applications are time-critical and dynamically changing. However, traditional data processing systems (e.g., stream processing systems, cloud-based IoT data processing systems, wide-area data analytics systems) are not well-suited for these IoT applications. These systems often do not scale well with a large number of concurrently running IoT applications, do not support low-latency processing under limited computing resources, and do not adapt to the level of heterogeneity and dynamicity commonly present at edge environments. This suggests a need for a new edge stream processing system that advances the stream processing paradigm to achieve efficiency and flexibility under the constraints presented by edge computing architectures. We present \textsc{Dart}, a scalable and adaptive edge stream processing engine that enables fast processing of a large number of concurrent running IoT applications’ queries in dynamic edge environments. The novelty of our work is the introduction of a dynamic dataflow abstraction by leveraging distributed hash table (DHT) based peer-to-peer (P2P) overlay networks, which can automatically place, chain, and scale stream operators to reduce query latency, adapt to edge dynamics, and recover from failures. We show analytically and empirically that DART outperforms Storm and EdgeWise on query latency and significantly improves scalability and adaptability when processing a large number of real-world IoT stream applications' queries. DART significantly reduces application deployment setup times, becoming the first streaming engine to support DevOps for IoT applications on edge platforms. 

   more » « less
2. Hierarchical Filter and Refinement System Over Large Polygonal Datasets on CPU-GPU

   https://doi.org/10.1109/HiPC.2019.00027  

   Liu, Yiming ; Yang, Jie ; Puri, Satish ( December 2019 , 2019 IEEE 26th International Conference on High Performance Computing, Data, and Analytics (HiPC))

   In this paper, we introduce our hierarchical filter and refinement technique that we have developed for parallel geometric intersection operations involving large polygons and polylines. The inputs are two layers of large polygonal datasets and the computations are spatial intersection on a pair of cross-layer polygons. These intersections are the compute-intensive spatial data analytic kernels in spatial join and map overlay computations. We have extended the classical filter and refine algorithms using PolySketch Filter to improve the performance of geospatial computations. In addition to filtering polygons by their Minimum Bounding Rectangle (MBR), our hierarchical approach explores further filtering using tiles (smaller MBRs) to increase the effectiveness of filtering and decrease the computational workload in the refinement phase. We have implemented this filter and refine system on CPU and GPU by using OpenMP and OpenACC. After using R-tree, on average, our filter technique can still discard 69% of polygon pairs which do not have segment intersection points. PolySketch filter reduces on average 99.77% of the workload of finding line segment intersections. PNP based task reduction and Striping algorithms filter out on average 95.84% of the workload of Point-in-Polygon tests. Our CPU-GPU system performs spatial join on two shapefiles, namely USA Water Bodies and USA Block Group Boundaries with 683K polygons in about 10 seconds using NVidia Titan V and Titan Xp GPU. 

   more » « less
3. Efficient Parallel and Adaptive Partitioning for Load-balancing in Spatial Join

   Yang, Jie ; Puri, Satish ( May 2020 , 34th IEEE International Parallel & Distributed Processing Symposium)

   Due to the developments of topographic techniques, clear satellite imagery, and various means for collecting information, geospatial datasets are growing in volume, complexity, and heterogeneity. For efficient execution of spatial computations and analytics on large spatial data sets, parallel processing is required. To exploit fine-grained parallel processing in large scale compute clusters, partitioning in a load-balanced way is necessary for skewed datasets. In this work, we focus on spatial join operation where the inputs are two layers of geospatial data. Our partitioning method for spatial join uses Adaptive Partitioning (ADP) technique, which is based on Quadtree partitioning. Unlike existing partitioning techniques, ADP partitions the spatial join workload instead of partitioning the individual datasets separately to provide better load-balancing. Based on our experimental evaluation, ADP partitions spatial data in a more balanced way than Quadtree partitioning and Uniform grid partitioning. ADP uses an output-sensitive duplication avoidance technique which minimizes duplication of geometries that are not part of spatial join output. In a distributed memory environment, this technique can reduce data communication and storage requirements compared to traditional methods. To improve the performance of ADP, an MPI+Threads based parallelization is presented. With ParADP, a pair of real world datasets, one with 717 million polylines and another with 10 million polygons, is partitioned into 65,536 grid cells within 7 seconds. ParADP performs well with both good weak scaling up to 4,032 CPU cores and good strong scaling up to 4,032 CPU cores. 

   more » « less
4. DDCEL: Efficient Distributed Doubly Connected Edge List for Large Spatial Networks

   https://doi.org/10.1109/MDM58254.2023.00029  

   Abdelhafeez, Laila ; Magdy, Amr ; Tsotras, Vassilis J. ( July 2023 , IEEE International Conference on Mobile Data Management (MDM))

   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
5. Hydrogen Station Location Planning via Geodesign in Connecticut: Comparing Optimization Models and Structured Stakeholder Collaboration

   https://doi.org/10.3390/en14227747  

   Lopez Jaramillo, Oscar ; Rinebold, Joel ; Kuby, Michael ; Kelley, Scott ; Ruddell, Darren ; Stotts, Rhian ; Krafft, Aimee ; Wentz, Elizabeth ( November 2021 , Energies)

   Geodesign is a participatory planning approach in which stakeholders use geographic information systems to develop and vet alternative design scenarios in a collaborative and iterative process. This study is based on a 2019 geodesign workshop in which 17 participants from industry, government, university, and non-profit sectors worked together to design an initial network of hydrogen refueling stations in the Hartford, Connecticut, metropolitan area. The workshop involved identifying relevant location factors, rapid prototyping of station network designs, and developing consensus on a final design. The geodesign platform, which was designed specifically for facility location problems, enables breakout groups to add or delete stations with a simple point-and-click operation, view and overlay different map layers, compute performance metrics, and compare their designs to those of other groups. By using these sources of information and their own expert local knowledge, participants recommended six locations for hydrogen refueling stations over two distinct phases of station installation. We quantitatively and qualitatively compared workshop recommendations to solutions of three optimal station location models that have been used to recommend station locations, which minimize travel times from stations to population and traffic or maximize trips that can be refueled on origin–destination routes. In a post-workshop survey, participants rated the workshop highly for facilitating mutual understanding and information sharing among stakeholders. To our knowledge, this workshop represents the first application of geodesign for hydrogen refueling station infrastructure planning. 

   more » « less