Advanced SmartNICs known as Data Processing Units (DPU) enable in-network data analytics, being equipped with standard processors and accelerators capable of doing custom computation on-NIC. These SmartNICs are advantageous because the host CPU can delegate simpler data analytics tasks, like filtering, to the NIC where the data first arrives. Only data needing further refinement must be passed on to the host CPU. Our benchmarks focus on NVIDIA’s commercially available Bluefield-3 DPU.

Similarity searches are a critical task in data mining. As datasets grow larger, exact nearest neighbor searches quickly become unfeasible, leading to the adoption of approximate nearest neighbor (ANN) searches. ANN has been studied for text data, images, and trajectories. However, there has been little effort to develop ANN systems for polygons in spatial database systems and geographic information systems. We present PolyMinHash, a system for approximate polygon similarity search that adapts MinHashing into a novel 2D polygon-hashing scheme to generate short, similarity-preserving signatures of input polygons. Minhash is generated by counting the number of randomly sampled points needed before the sampled point lands within the polygon's interior area, yielding hash values that preserve area-based Jaccard similarity.

A segment tree is a versatile tree-based data structure over intervals or line segments efficiently supporting several computational operations such as stabbing query, segment arrangement, and planar point location, both theoretically and practically. Polygon clipping is a basic operation in domains such as Computer Graphics, Computer-aided Design, and Geographic Information Science (GIS). Given two polygons with n vertices, polygon clipping algorithms find the geometric intersection or union in <?TeX $\mathcal {O}(n^2)$?> Math 1 time using Foster’s all-to-all edge intersection testing and <?TeX $\mathcal {O}((n+k)\log n)$?> Math 2 time using Vatti’s sweep line-based method, where k is the number of intersections. No known segment tree implementation, including the CGAL library, supports intersection finding or polygon clipping. We extended the segment tree leveraging Chaselle’s PRAM-model augmentation, parallelized the construction of our augmented segment tree, and employed it to find line segment intersections for polygon clipping while handling degenerate cases. Augmented segment tree eliminates 99% of non-intersecting edge pairs compared to 63% by the state-of-the-art filtering based on common minimum bounding rectangle method employed in Foster’s GPU-based implementation. This, coupled with Ω(nlog n) work on a single CPU core, beats Foster’s GPU performance with <?TeX $\mathcal {O}(n^2)$?> Math 3 work. Our OpenMP directive based multi-core implementation achieves up to 4X relative speedup for clipping two polygons with 182K vertices and 5X speedup for five polygons with 398K vertices. We also offloaded the parallel kernels to a GPU using OpenACC achieving performance competitive with Foster’s GPU implementation. Our profiling indicates limitations of the compiler directives and potential for superior performance by employing pthread/cuda libraries.

Polygonal geometric operations are fundamental in domains such as Computer Graphics, Computer-Aided Design, and Geographic Information Systems. Handling degenerate cases in such operations is important when real-world spatial data are used. The popular Greiner-Hormann (GH) clipping algorithm does not handle such cases properly without perturbing vertices leading to inaccuracies and ambiguities. In this work, we parallelize the$O$(n2)-time general polygon clipping algorithm by Foster et al., which can handle degenerate cases without perturbation. Our CREW PRAM algorithm can perform clipping in O (log n) time using$n$+$k$number of processors with simple polygons, where$n$is the number of input edges and$k$is the number of edge intersections. For efficient GPU implementation, we employ three effective filters which have not been used in prior work on polygon clipping: 1) Common-minimum-bounding-rectangle filter, 2) Count-based filter, and 3) Line-segment-minimum-bounding-rectangle filter. They drastically reduce O($n$2) candidate edge pairs comparisons by 80% - 99%, leading to significantly faster parallel execution. In our experiments, C++ CUDA-based implementation yields up to 40X speedup over real-world datasets, processing two polygons with a total of 174K vertices on an Nvidia Quadro RTX 5000 GPU compared to the sequential Foster's algorithm running on an Intel Xeon Silver 4210R CPU.

Geographic information systems deal with spatial data and its analysis. Spatial data contains many attributes with location information. Spatial autocorrelation is a fundamental concept in spatial analysis. It suggests that similar objects tend to cluster in geographic space. Hotspots, an example of autocorrelation, are statistically significant clusters of spatial data. Other autocorrelation measures like Moran's I are used to quantify spatial dependence. Large scale spatial autocorrelation methods are compute-intensive. Fast methods for hotspots detection and analysis are crucial in recent times of COVID-19 pandemic. Therefore, we have developed parallelization methods on heterogeneous CPU and GPU environments. To the best of our knowledge, this is the first GPU and SIMD-based design and implementation of autocorrelation kernels. Earlier methods in literature intro-duced cluster-based and Map Reduce-based parallelization. We have used Intrinsics to exploit SIMD parallelism on x86 CPU architecture. We have used MPI Graph Topology to minimize inter- process communication. Our benchmarks for CPU/GPU optimizations gain upto 750X relative speedup with a 8 GPU setup when compared to baseline sequential implementation. Compared to the best implementation using OpenMP + R-tree data structure on a single compute node, our accelerated hotspots benchmark gains a 25X speedup. For real world US counties and COVID data evolution calculated over 500 days, we gain upto 110X speedup reducing time from 33 minutes to 0.3 minutes.

Spatial join is an important operation for combining spatial data. Parallelization is essential for improving spatial join performance. However, load imbalance due to data skew limits the scalability of parallel spatial join. There are many work sharing techniques to address this problem in a parallel environment. One of the techniques is to use data and space partitioning and then scheduling the partitions among threads/processes with the goal of minimizing workload differences across threads/processes. However, load imbalance still exists due to differences in join costs of different pairs of input geometries in the partitions.

Geometric intersection algorithms are fundamental in spatial analysis in Geographic Information System (GIS). Applying high performance computing to perform geometric intersection on huge amount of spatial data to get real-time results is necessary. Given two input geometries (polygon or polyline) of a candidate pair, we introduce a new two-step geospatial filter that first creates sketches of the geometries and uses it to detect workload and then refines the sketches by the common areas of sketches to decrease the overall computations in the refine phase. We call this filter PolySketch-based CMBR (PSCMBR) filter. We show the application of this filter in speeding-up line segment intersections (LSI) reporting task that is a basic computation in a variety of geospatial applications like polygon overlay and spatial join.

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.

Voronoi diagram construction is a common and fundamental problem in computational geometry and spatial computing. Numerous sequential and parallel algorithms for Voronoi diagram construction exists in literature. This paper presents a multi-threaded approach where we augment an existing sequential implementation of Fortune's planesweep algorithm with compiler directives. The novelty of our fine-grained parallel algorithm lies in exploiting the concurrency available at each event point encountered during the algorithm. On the Intel Xeon E5 CPU, our shared-memory parallelization with OpenMP achieves around 2x speedup compared to the sequential implementation using datasets containing 2k-128k sites.

Sports data analysis and visualization can be a useful tool for gaining insights into the games. In this paper, we present a new technique to analyze and visualize shot patterns in tennis matches. Tennis is a complicated game that involves a rich set of tactics and strategies. The current tennis data analyses are usually conducted at a high level that often fail to show useful patterns and nuances embedded in low level data. Based on a very detailed database of professional tennis matches, we have developed a system to analyze the serve and shot patterns so that a user can explore questions such as "What are the favorite patterns of this player? What are the most effective patterns for this player?" This can help tennis experts, players, and fans gain deeper insight into the sport.

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.

In recent times, geospatial datasets are growing in terms of size, complexity and heterogeneity. High performance systems are needed to analyze such data to produce actionable insights in an efficient manner. For polygonal a.k.a vector datasets, operations such as I/O, data partitioning, communication, and load balancing becomes challenging in a cluster environment. In this work, we present MPI-Vector-IO 1, a parallel I/O library that we have designed using MPI-IO specifically for partitioning and reading irregular vector data formats such as Well Known Text. It makes MPI aware of spatial data, spatial primitives and provides support for spatial data types embedded within collective computation and communication using MPI message-passing library. These abstractions along with parallel I/O support are useful for parallel Geographic Information System (GIS) application development on HPC platforms.

Presents the introductory welcome message from the conference proceedings. May include the conference officers' congratulations to all involved with the conference event and publication of the proceedings record.

Given two layers of large polygonal datasets, detecting those pairs of cross-layer polygons which satisfy a join predicate, such as intersection or contain, is one of the most computationally intensive primitive operations in the spatial domain applications. In this work, we introduce GCMF, an end-to-end software system, that is able to handle spatial join (with ST_Intersect operation) over non-indexed polygonal datasets with over 3 GB file size comprising more than 600, 000 polygons on a single GPU within less than 8 sec by applying innovative filter and refinement techniques. GCMF performs a two-step filtering phase. 1) A sort-based Minimum Bounding Rectangle (MBR) filtering step detects potentially overlapping polygon pairs up to 20 times faster than the optimized GEOS library routine. 2) A linear time Common MBR filtering step (based on the overlapping area of two given MBRs) that not only eliminates two-third of the candidate polygon pairs but also reduces the number of edges to be considered in the refinement phase by 40-fold on an average based on our experimental results with real datasets. Furthermore, for the refinement phase, GCMF implements a load-balanced parallel point-in-polygon and edge-intersection tests over GPU. Our experimental results with three different real datasets show up to 39-fold end-to- end speedup versus optimized sequential routines of GEOS C++ library as well as PostgreSQL spatial database with PostGIS.

Clipping arbitrary polygons is one of the complex operations in computer graphics and computational geometry. It is applied in many fields such as Geographic Information Systems (GIS) and VLSI CAD. We have two significant results to report. Our first result is the effective parallelization of the classic, highly sequential Greiner-Hormann algorithm, which yields the first output-sensitive CREW PRAM algorithm for a pair of simple polygons, and can perform clipping in O(logn) time using O(n+k) processors, where n is the total number of vertices and k is the number of edge intersections. This improves upon our previous clipping algorithm based on the parallelization of Vatti's sweepline algorithm, which requires O(n+k+k') processors to achieve logarithmic time complexity where k' can be O(n2). This also improves upon another O(logn) time algorithm by Karinthi, Srinivas, and Almasi which unlike our algorithm does not handle self-intersecting polygons, is not output-sensitive, and must employ O(n2) processors to achieve O(logn) time. We also study multi-core and many-core implementations of our parallel Greiner-Hormann algorithm. Our second result is a practical, parallel GIS system, namely MPI-GIS, for polygon overlay processing of two GIS layers containing large number of polygons over a cluster of compute nodes. It employs R-tree for efficient indexing and identification of potentially intersecting set of polygons across two input GIS layers. Spatial data files tend to be large in size (in GBs) and the underlying overlay computation is highly irregular and compute intensive. This system achieves 44X speedup on a 32-node NERSC's CARVER cluster while processing about 600K polygons in two GIS layers within 19 seconds which takes over 13 minutes on state-of-art ArcGIS system.

Message Passing Interface (MPI) has been the predominant standardized system for writing parallel and distributed applications. However, while MPI has been the software system of choice for traditional parallel and distributed computing platforms such as large compute clusters and Grid, MPI is not the system of choice for cloud platforms. The primary reasons for this is the lack of low latency high bandwidth network capabilities of the cloud platforms and the inherent architectural differences from traditional compute clusters. Prior studies suggest that the message latency of cloud platforms could be as much as 35x slower than that of an infiniband-connected cluster [1] for popular MPI implementations. MPI-like environment on cloud platforms is desirable for a large class of applications that run for long time spans with varying computing needs, such as the modeling and analysis to predict swath of a hurricane. Such applications could benefit from cloud's resiliency and on-demand access for a robust and green solution. Interestingly, most of the cloud vendors provide APIs to access cloud resources in an efficient manner different than how an MPI implementation would avail of those resources. We have done extensive research to identify the pain-points for designing and implementing an MPI-like framework for cloud platforms. Our research has provided us with vital guidelines that we are sharing in this paper. We present the details of the key components required for such a framework along with our experience while implementing a preliminary MPI-like framework over Azure dubbed cloud MPI and evaluate its pros and cons. A large GIS application has been ported over cloud MPI to study its effectiveness and limitations.

Polygon clipping is one of the complex operations in computational geometry. It is a primitive operation in many fields such as Geographic Information Systems (GIS), Computer Graphics and VLSI CAD. Sequential algorithms for this problem are in abundance in literature but there are very few parallel algorithms solving it in its most general form. We present the first output-sensitive CREW PRAM algorithm, which can perform polygon clipping in O(logn) time using (n + k + k') processors, where n is the number of vertices, k is the number of edge intersections and k' is the additional temporary vertices introduced due to the partitioning of polygons. The current best algorithm by Karinthi, Srinivas, and Almasi [1] does not handle self-intersecting polygons, is not output-sensitive and must employ ⊝(n2) processors to achieve O(logn) time. Our algorithm is developed from the first principles and it is superior to [1] in cost. It yields a practical implementation on multicores and demonstrates 30x speedup for real-world dataset. Our algorithm can perform the typical clipping operations including intersection, union, and difference.