YGM is a general-purpose asynchronous distributed computing library for C++/MPI, designed to handle the irregular data access patterns and small messages of graph algorithms and data science applications. It uses data serialization to give an easily usable active message interface and message aggregation to maximize application throughput. Our design philosophy makes a tradeoff that increases network bandwidth utilization at the cost of added latency. We provide a suite of benchmarks showcasing YGM's performance. Compared to similar distributed active message benchmark implementations that do not provide message buffering, we are able to achieve over 10x throughput on thousands of cores at a latency cost that can be as small as 2x or as large as 100x, depending on the machine being used. For applications that can be written to be latency-tolerant, this represents a significant potential performance improvement through using YGM.

Given an edge-weighted graph and a set of known seed vertices of interest, a network scientist often desires to understand the graph relationships to explain connections between the seed vertices. If the size of the seed set is 2, shortest path calculations are an attractive computational kernel to explore the connections between the two vertices. When the seed set is 3 or larger (say up to 1,000s) Steiner minimal tree – min-weight acyclic connected subgraph (of the input graph) that contains all the seed vertices – is an attractive generalization of shortest weighted paths. In general, computing a Steiner minimal tree is NP-hard, but decades ago several polynomial-time algorithms were designed and proven to yield Steiner trees whose total weight is bounded within 2 times the minimal Steiner tree. Despite its rich theoretical literature, works related to parallel Steiner minimal tree computation and their scalable implementations are rather scarce. In this paper, we present a parallel 2-approximation Steiner minimal tree algorithm (with theoretical guarantees) and its MPI-based distributed implementation. In place of distance computation between all pairs of seed vertices, an expensive phase in many approximation algorithms, the solution we employ, exploits Voronoi cell computation. Also, this approach has higher parallel efficiency than others that involve minimum spanning tree computation on the entire graph. Furthermore, our distributed design exploits asynchronous processing and a message prioritization scheme to accelerate convergence of distance computation, employs techniques to avoid inefficient distributed spanning tree computation on the entire graph, and harnesses a combination of vertex and edge centric processing to offer fast time-to-solution. We demonstrate scalability and performance of our solution using real-world graphs with up to 128 billion edges and 512 compute nodes (8K processes), show the ability to find Steiner trees with up to 10K seed vertices in under one minute, and present in-depth analyses that highlight the benefits of our design choices. Using four real-world graphs and three seed sets for each, we compare our solution with the state-of-the-art exact Steiner minimal tree solver, SCIP-Jack, and two sequential algorithms with the same approximation bound as our algorithm. Our distributed solution comfortably outperforms these related works on graphs with 10s million edges and offers decent strong scaling – up to 90% efficient. We empirically show that, on average, the total distance (sum of edge weights) of the Steiner tree identified by our solution is 1.0527 times greater than the Steiner minimal tree (i.e., the optimal solution) – well within the theoretical bound of less than equal to 2.

Understanding the higher-order interactions within network data is a key objective of network science. Surveys of metadata triangles (or patterned 3-cycles in metadata-enriched graphs) are often of interest in this pursuit. In this work, we develop TriPoll, a prototype distributed HPC system capable of surveying triangles in massive graphs containing metadata on their edges and vertices. We contrast our approach with much of the prior effort on triangle analysis, which often focuses on simple triangle counting, usually in simple graphs with no metadata. We assess the scalability of TriPoll when surveying triangles involving metadata on real and synthetic graphs with up to hundreds of billions of edges. We utilize communication-reducing optimizations to demonstrate a triangle counting task on a 224 billion edge web graph in approximately half of the time of competing approaches, while additionally supporting metadata-aware capabilities.

Modern shared-memory platforms embrace the Non-uniform Memory Access (NUMA) architecture - they have physically distributed, yet cache-coherent shared-memory. This paper explores the feasibility of a shared-memory graph processing engine for NUMA platforms inspired by designs that target zero-sharing platforms. This work exploits the characteristics of two processing modes, synchronous and asynchronous, in the context of the shared-memory NUMA platform. Depending on the algorithm, phase of execution, and graph topology, synchronous and asynchronous modes hold unique advantages over one another. We then explore a hybrid solution that combines synchronous and asynchronous processing within the same graph computation task and harness optimizations therein. An extensive evaluation using graphs with billions of edges and empirical comparisons with several state-of-the-art solutions demonstrate the performance advantages of our design.

There are multiple situations where supporting approximation in graph pattern matching tasks is highly desirable: (i) the data acquisition process can be noisy; (ii) a user may only have an imprecise idea of the search query; and (iii) approximation can be used for high volume vertex labeling when extracting machine learning features from graph data. We present a new algorithmic pipeline for approximate matching that combines edit-distance based matching with systematic graph pruning. We formalize the problem as identifying all exact matches for up to k edit-distance subgraphs of a user-supplied template. We design a solution which exploits unique optimization opportunities within the design space, not explored previously. Our solution is (i) highly scalable, (ii) supports arbitrary patterns and edit-distance, (iii) offers 100% precision and 100% recall guarantees, and (vi) supports a set of popular data analysis scenarios. We demonstrate its advantages through an implementation that offers good strong and weak scaling on massive real-world (257 billion edges) and synthetic (1.1 trillion edges) labeled graphs, respectively, and when operating on a massive cluster (256 nodes/9,216 cores), orders of magnitude larger than previously used for similar problems. Empirical comparison with the state-of-the-art highlights the advantages of our solution when handling massive graphs and complex patterns.

Interferometric Synthetic Aperture Radar (InSAR) is a remote sensing technology used for estimating the displacement of an object on the ground or the earth's surface itself. Persistent Scatterer-InSAR (PS-InSAR) is a category of time series algorithms enabling high resolution monitoring. PS-InSAR relies on successful selection of points that appear stable across a set of satellite images taken overtime. This paper presents PtSel, a new algorithm for selecting these points, a problem known as Persistent Scatterer Selection. The key advantage of PtSel over the key existing techniques is that it does not require model assumptions, yet preserves solution accuracy. Motivated by the abundance of parallelism the algorithm exposes, we have implemented it for GPUs. Our evaluation using real-world data shows that the GPU implementation not only offers superior performance but also scales linearly with GPU count and workload size. We compare the GPU implementation and a parallel CPU implementation: a consumer grade GPU offers 18x speedup over a 16-core Ivy Bridge Xeon System, while four GPUs offer 65x speedup. The GPU solution consumes 28x less energy than the CPU-only solution. Additionally, we present a comparison with the most widely used PS-interferometry software package StaMPS, in terms of point selection coverage and precision.

Subgraph pattern matching is fundamental to graph analytics and has wide applications. Unfortunately, high computational complexity limits the robustness guarantees of existing algorithms: they do not scale for modern large graph datasets and/or they have limitations in terms of accuracy or in terms of the intricacy of the patterns supported. We present algorithms, theory, and empirical evidence that iteratively eliminating vertices that do not meet local constraints dramatically reduces the search space for pattern matching in real-world graphs, and demonstrate a scalable implementation of our algorithms. We additionally identify the characteristics of patterns for which every non-eliminated vertex participates in a match. These techniques are an essential step to enable scalable, practical solutions for robust pattern matching in large-scale labeled graphs.We demonstrate the advantages of the proposed approach through strong and weak scaling experiments on massive-scale real-world (up to 257 billion edges) and synthetic (up to 2.2 trillion edges) graphs and at scales (256 compute nodes with 6,144 processors) orders of magnitude larger than those used in the past for similar problems.

Interferometric Synthetic Aperture Radar (InSAR) is a remote sensing technology used for estimating displacement of the earth's surface. Phase unwrapping is the most important step in InSAR processing and relies on successful selection of points that appear stable across a set of satellite images taken over time. This paper presents a new algorithm for selecting these points, a problem known as persistent scatterer selection. The algorithm computes the temporal coherence on the wrapped phase derivative by subtracting phases of a pixel and one of its nearby neighbours. It does not require model assumptions, yet preserves accuracy. Motivated by the abundance of parallelism the algorithm exposes, we have implemented it for GPUs. Evaluation using real-world data shows that the GPU implementation not only offers widely superior performance but also scales linearly with GPU count and workload size. We compare the GPU implementation against a parallel CPU implementation: A consumer grade GPU offers an 18× speedup over a 16-core Ivy Bridge Xeon System, while four GPUs offer 65× speedup. Roofline analysis shows that, on a single GPU, our implementation achieves 83% of the peak FLOP-rate of the dual-CPU system. Additionally, the GPU-based solution consumes 29× less energy than the CPU-only solution.

The Vehicular Ad Hoc Network (VANET) holds promises for on-road security applications. In this paper, we utilize the VANET for surveillance purpose, tracking a noncooperative mobile target. We explore the possibilities of engaging Onboard Units (OBUs) and Roadside Units (RSUs) in a metropolitan VANET for tracking a vehicle that is on the run. The uncertainty associated with the unplanned locomotion of a vehicle in the metropolitan road network, that exhibits dynamic characteristics, such as different speed limits and time varying traffic congestion, makes vehicle tracking challenging. We present a tracking system composed of three operational modules: localization, tracking data collection and prediction of future locations of a target. Tracking messages are communicated among the OBUs and RSUs and are triggered on in probable areas where the target may be present. Therefore, another imperative element of the addressed problem is to scope the search to limit the number of OBUs and RSUs involved in the tracking operation. Our proposal does not presume any motion model for the target. A novel movement modeling technique utilizes OBU observations to classify the target's movement pattern. We propose a Dirichlet-multinomial model under the Bayesian estimation framework. The movement estimation is then exploited for predicting future locations of the target. The proposed method is analogous to chasing an on the run vehicle using police squad cars. We believe this approach holds potentials as an alternative to high-speed pursuits.