Real-time analytics on large dynamic graphs

In today's fast-paced and interconnected digital world, the data generated by an increasing number of applications is being modeled as dynamic graphs. The graph structure encodes relationships among data items, while the structural changes to the graphs as well as the continuous stream of information produced by the entities in these graphs make them dynamic in nature. Examples include social networks where users post status updates, images, videos, etc.; phone call networks where nodes may send text messages or place phone calls; road traffic networks where the traffic behavior of the road segments changes constantly, and so on. There is a tremendous value in storing, managing, and analyzing such dynamic graphs and deriving meaningful insights in real-time. However, a majority of the work in graph analytics assumes a static setting, and there is a lack of systematic study of the various dynamic scenarios, the complexity they impose on the analysis tasks, and the challenges in building efficient systems that can support such tasks at a large scale. In this dissertation, I design a unified streaming graph data management framework, and develop prototype systems to support increasingly complex tasks on dynamic graphs. In the first part, I focus on the management and querying of distributed graph data. I develop a hybrid replication policy that monitors the read-write frequencies of the nodes to decide dynamically what data to replicate, and whether to do eager or lazy replication in order to minimize network communication and support low-latency querying. In the second part, I study parallel execution of continuous neighborhood-driven aggregates, where each node aggregates the information generated in its neighborhoods. I build my system around the notion of an aggregation overlay graph, a pre-compiled data structure that enables sharing of partial aggregates across different queries, and also allows partial pre-computation of the aggregates to minimize the query latencies and increase throughput. Finally, I extend the framework to support continuous detection and analysis of activity-based subgraphs, where subgraphs could be specified using both graph structure as well as activity conditions on the nodes. The query specification tasks in my system are expressed using a set of active structural primitives, which allows the query evaluator to use a set of novel optimization techniques, thereby achieving high throughput. Overall, in this dissertation, I define and investigate a set of novel tasks on dynamic graphs, design scalable optimization techniques, build prototype systems, and show the effectiveness of the proposed techniques through extensive evaluation using large-scale real and synthetic datasets.

THE IMPACT OF UPPER-LEVEL PROCESSES ON THE INTENSITY AND STRUCTURAL CHANGES OF HURRICANE SANDY (2012)

The first part of this study examines the relative roles of frontogenesis and tropopause undulation in determining the intensity and structural changes of Hurricane Sandy (2012) using a high-resolution cloud-resolving model. A 138-h simulation reproduces Sandy’s four distinct development stages: (i) rapid intensification, (ii) weakening, (iii) steady maximum surface wind but with large continued sea-level pressure (SLP) falls, and (iv) re-intensification. Results show typical correlations between intensity changes, sea-surface temperature and vertical wind shear during the first two stages. The large SLP falls during the last two stages are mostly caused by Sandy’s moving northward into lower-tropopause regions associated with an eastward-propagating midlatitude trough, where the associated lower-stratospheric warm air wraps into the storm and its surrounding areas. The steady maximum surface wind occurs because of the widespread SLP falls with weak pressure gradients lacking significant inward advection of absolute angular momentum (AAM). Meanwhile, there is a continuous frontogenesis in the outer region during the last three stages. Cyclonic inward advection of AAM along each frontal rainband accounts for the continued expansion of the tropical-storm-force wind and structural changes, while deep convection in the eyewall and merging of the final two survived frontal rainbands generate a spiraling jet in Sandy’s northwestern quadrant, leading to its re-intensification prior to landfall. The physical, kinematic and dynamic aspects of an upper-level outflow layer and its possible impact on the re-intensification of Sandy are examined in the second part of this study. Above the outflow layer isentropes are tilted downward with radius as a result of the development of deep convection and an approaching upper-level trough, causing weak subsidence. Its maximum outward radial velocity is located above the cloud top, so the outflow channel experiences cloud-induced long-wave cooling. Because Sandy has two distinct convective regions (an eyewall and a frontal rainband), it has multiple outflow layers, with the eyewall’s outflow layer located above that of the frontal rainband. During the re-intensification stage, the eyewall’s outflow layer interacts with a jet stream ahead of the upper-level trough axis. Because of the presence of inertial instability on the anticyclonic side of the jet stream and symmetric instability in the inner region of the outflow layer, Sandy’s secondary circulation intensifies. Its re-intensification ceases when these instabilities disappear. The relationship between the intensity of the secondary circulation and dynamic instabilities of the outflow layer suggests that the re-intensification occurs in response to these instabilities. Additionally, it is verified that the long-wave cooling in the outflow layer helps induce symmetric instability by reducing static stability.