Given a large graph$G$, a subgraph query$Q$finds the set of all subgraphs of$G$that satisfy certain conditions specified by$Q$. Examples of subgraph queries including finding a community containing designated members to organize an event, and subgraph matching. To overcome the weakness of existing graph-parallel systems that underutilize CPU cores when finding subgraphs, our prior system, G-thinker, was proposed that adopts a novel think-like-a-task (TLAT) parallel programming model. However, G-thinker targets offline analytics and cannot support interactive online querying where users continually submit subgraph queries with different query contents. The challenges here are (i) how to maintain fairness that queries are answered in the order that they are received: a later query is processed only if earlier queries cannot saturate the available computation resources; (ii) how to track the progress of active queries (each with many tasks under computation) so that users can be timely notified as soon as a query completes; and (iii) how to maintain memory boundedness and high task concurrency as in G-thinker. In this article, we propose a novel TLAT programming framework, called G-thinkerQ, for answering online subgraph queries. G-thinkerQ inherits the memory boundedness and high task concurrency of G-thinker by organizing the tasks of each query using a “task capsule” structure, and designs a novel task-capsule list is to ensure fairness among queries. A novel lineage-based mechanism is also designed to keep track of when the last task of a query is completed. Parallel counterparts of the state-of-the-art algorithms for 4 recent advanced subgraph queries are implemented on G-thinkerQ to demonstrate its CPU-scalability.

The k-core of a graph is the largest induced sub-graph with minimum degree k. The problem of k-core decomposition finds the k-cores of a graph for all valid values of k, and it has many applications such as network analysis, computational biology and graph visualization. Currently, there are two types of parallel algorithms for k-core decomposition: (1) degree-based vertex peeling, and (2) iterative h-index refinement. There is, however, few studies on accelerating k-core decomposition using GPU. In this paper, we propose a highly optimized peeling algorithm on a GPU, and compare it with possible implementations on top of think-like-a-vertex graph-parallel GPU systems as well as existing serial and parallel k-core decomposition algorithms on CPUs. Extensive experiments show that our GPU algorithm is the overall winner in both time and space. Our source code is released at https://github.com/akhlaqueak/KCoreGPU.

Quasi-cliques are a type of dense subgraphs that generalize the notion of cliques, important for applications such as community/module detection in various social and biological networks. However, the existing quasi-clique definition and algorithms are only applicable to undirected graphs. In this paper, we generalize the concept of quasi-cliques to directed graphs by proposing (γ1, γ2) -quasi-cliques which have density requirements in both inbound and outbound directions of each vertex in a quasi-clique subgraph. An efficient recursive algorithm is proposed to find maximal (γ1,γ2)-quasi-cliques which integrates many effective pruning rules that are validated by ablation studies. We also study the finding of top-k large quasi-cliques directly by bootstrapping the search from more compact quasi-cliques, to scale the mining to larger networks. The algorithms are parallelized with effective load balancing, and we demonstrate that they can scale up effectively with the number of CPU cores.

Decision trees and tree ensembles are popular supervised learning models on tabular data. Two recent research trends on tree models stand out: (1) bigger and deeper models with many trees, and (2) scalable distributed training frameworks. However, existing implementations on distributed systems are IO-bound leaving CPU cores underutilized. They also only find best node-splitting conditions approximately due to row-based data partitioning scheme. In this paper, we target the exact training of tree models by effectively utilizing the available CPU cores. The resulting system called TreeServer adopts a column-based data partitioning scheme to minimize communication, and a node-centric task-based engine to fully explore the CPU parallelism. Experiments show that TreeServer is up to 10× faster than models in Spark MLlib. We also showcase TreeServer's high training throughput by using it to build big “deep forest” models.

Micromobility refers to small, lightweight vehicles such as shared bicycles and electric scooters (e-scooters). Recently, shared micromobility services see increasing deployment in urban areas to solve the "last mile´ problem, where the travel distance is considered long when walking on foot, but not worth driving a car (e.g., to avoid parking). A key question to ask when deciding whether to deploy a shared micromobility service in an area is: how much car traffic can be reduced during peak hours if this service is deployed? This work answers this question by agent-based transportation simulation. The key challenge here is to generate a realistic synthetic population of the target area along with their travel day-plans. We propose to use an area-specific travel survey plus openly available data sources for this purpose, and demonstrate our approach through a case study that studied the traffic impacts of deploying dockless e-scooters in Birmingham, AL. A demo of our simulation is available at https://youtu.be/zh_mHQ6ck4U.

Micromobility refers to small, lightweight vehicles such as shared bicycles and electric scooters (e-scooters). Recently, shared micromobility services see increasing deployment in urban areas, especially for trips where the travel distance is considered long for walking, but not worth driving a car (e.g., to avoid parking). A key question to ask when deciding whether to deploy a shared micromobility service in an area is: how much car traffic can be reduced during peak hours if this service is deployed? This work answers this question by agent-based transportation simulation. The key contribution is to generate a realistic synthetic population of transportation users in the target area along with their travel day-plans, using an area-specific travel survey plus openly available data sources. We demonstrate our approach through a case study on the deployment of dockless e-scooters in Birmingham, AL, with a demo at https://youtu.be/zh_mHQ6ck4U.

Various industries use towers as part of their daily operations, such as transmission towers (aka. electricity pylons), telecommunications towers and water towers. These towers re- quire regular maintenance, and before the maintenance work can be done, a preliminary survey must be conducted to determine where to work. More and more, such surveys are being conducted via drones. This work develops a detection model to help locate tower issues from the video frames of drones. However, it does not provide satisfactory performance to directly train such an object detection model with the annotated problem locations from domain experts. Therefore, we propose to improve the quality of the extracted image features with the help of another separate task which detects the various parts that are involved in the tower issues, such as bolts, nuts, washers and pins, the annotations of which can be done without the need of domain expertise. Through this multi-task learning scheme, we improved the problem detection recall from 59.6% to 71.5%, providing much more effective recommendations of potential issues for inspectors to examine further. Also, the average number of problem detections in each image is merely 5.54 so inspectors are not overwhelmed by the recommended locations.

Mining from a big graph those subgraphs that satisfy certain conditions is useful in many applications such as community detection and subgraph matching. These problems have a high time complexity, but existing systems to scale them are all IO-bound in execution. We propose the first truly CPU-bound distributed framework called G-thinker that adopts a user-friendly subgraph-centric vertex-pulling API for writing distributed subgraph mining algorithms. To utilize all CPU cores of a cluster, G-thinker features (1) a highly-concurrent vertex cache for parallel task access and (2) a lightweight task scheduling approach that ensures high task throughput. These designs well overlap communication with computation to minimize the CPU idle time. Extensive experiments demonstrate that G-thinker achieves orders of magnitude speedup compared even with the fastest existing subgraph-centric system, and it scales well to much larger and denser real network data. G-thinker is open-sourced at http://bit.ly/gthinker with detailed documentation.

Frequent pattern mining (FPM) has been a focused theme in data mining research for decades, but there lacks a general programming framework that can be easily customized to mine different kinds of frequent patterns, and existing solutions to FPM over big transaction databases are IO-bound rendering CPU cores underutilized even though FPM is NP-hard. This paper presents, PrefixFPM, a general-purpose framework for FPM that is able to fully utilize the CPU cores in a multicore machine. PrefixFPM follows the idea of prefix projection to partition the workloads of PFM into independent tasks by divide and conquer. PrefixFPM exposes a unified programming interface to users who can customize it to mine their desired patterns, and the parallel execution engine is transparent to end-users and can be reused for mining all kinds of patterns. We have adapted the state-of-the-art serial algorithms for mining frequent patterns including subsequences, subtrees, and subgraphs on top of PrefixFPM, and extensive experiments demonstrate an excellent speedup ratio of PrefixFPM with the number of cores. A demo is available at https://youtu.be/PfioC0GDpsw; the code is available at https://github.com/yanlab19870714/PrefixFPM.

Given a user-specified minimum degree threshold γ , a γ -quasiclique is a subgraph g = (V g , E g ) where each vertex ν ∈ V g connects to at least γ fraction of the other vertices (i.e., ⌈ γ · (| V g |- 1)⌉ vertices) in g. Quasi-clique is one of the most natural definitions for dense structures useful in finding communities in social networks and discovering significant biomolecule structures and pathways. However, mining maximal quasi-cliques is notoriously expensive. In this paper, we design parallel algorithms for mining maximal quasi-cliques on G-thinker, a distributed graph mining framework that decomposes mining into compute-intensive tasks to fully utilize CPU cores. We found that directly using G-thinker results in the straggler problem due to (i) the drastic load imbalance among different tasks and (ii) the difficulty of predicting the task running time. We address these challenges by redesigning G-thinker's execution engine to prioritize long-running tasks for execution, and by utilizing a novel timeout strategy to effectively decompose long-running tasks to improve load balancing. While this system redesign applies to many other expensive dense subgraph mining problems, this paper verifies the idea by adapting the state-of-the-art quasi-clique algorithm, Quick, to our redesigned G-thinker. Extensive experiments verify that our new solution scales well with the number of CPU cores, achieving 201× runtime speedup when mining a graph with 3.77M vertices and 16.5M edges in a 16-node cluster.

Precipitation nowcasting, which predicts rainfall intensity in the near future, has been studied by meteorologists for decades. Currently, computer vision techniques, especially optical flow based methods, are widely adopted by observatories since they deliver reasonable performance without the need of model training. However, their performance is highly sensitive to model parameters which require a lot of empirical knowledge to optimize. With the recent success of deep learning (DL), machine learning researchers have started to explore the use of spatiotemporal DL models for precipitation nowcasting, which have demonstrated a better performance than optical flow based methods. However, DL models are not easy to conFigure for nonDL experts such as meteorologists. In this poster, we introduce EasyRain, a platform with a user-friendly web interface to help users without domain knowledge (in DL and/or meteorology) to efficiently build DL and optical flow based models. We will demonstrate the efficiency and usability of EasyRain for training, tuning, and comparing precipitation nowcasting models.

MATSim is the state-of-the-art open source software for agent-based transport simulation, intended for use to evaluate transportation planning models. A standard approach to use MATSim is to conduct a user survey about their day-plans of travel, from which a synthetic dataset of agents' day-plans for an entire region is generated for transport simulation. The simulation output can be used for various evaluations, such as congestion conditions of road segments and their peak hours.This paper aims to conduct a transportation simulation on MATSim for the region of Birmingham, AL. A traditional approach based on Iterative Proportional Fitting (IPF) is not sufficient for generating a realistic synthetic population due to the small data problem: Birmingham is a small city with limited transport data statistics, and we only have a survey of 451 people for their day-plans. To tackle the small data problem, we seek the assistance of abundant open data such as US Census data, OpenStreetMap, OpenAddresses and Birmingham Business}{Alliance to complete the fine details realistically. We also utilize various data science and machine learning techniques to build models that utilize these open data to generate a realistic population. Preliminary tests demonstrate reasonable accuracy of the simulation results.

This poster aims to conduct a transportation simulation on MATSim, the state-of-the-art open source software for agent-based transportation simulation, for the region of Birmingham, AL, where a synthetic population is generated from a survey of 451 people with their day-plans of traveling. To tackle the small data problem, we seek the assistance of abundant open data such as US Census data, OpenStreetMap, OpenAddresses and Birmingham Business Alliance to complete the fine details realistically. We also utilize data science and machine learning techniques as well as iterative proportional fitting to build models that utilize these open data to generate a realistic population. Good accuracy of the simulation is achieved; see https://youtu.be/ZIm0WsmKB4E for a demo.