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.

A Search for Muon Neutrinos in Coincidence with Gamma-Ray Bursts in the Southern Hemisphere Sky Using the IceCube Neutrino Observatory

The origin of observed ultra-high energy cosmic rays (UHECRs, energies in excess of $10^{18.5}$ eV) remains unknown, as extragalactic magnetic fields deflect these charged particles from their true origin. Interactions of these UHECRs at their source would invariably produce high energy neutrinos. As these neutrinos are chargeless and nearly massless, their propagation through the universe is unimpeded and their detection can be correlated with the origin of UHECRs. Gamma-ray bursts (GRBs) are one of the few possible origins for UHECRs, observed as short, immensely bright outbursts of gamma-rays at cosmological distances. The energy density of GRBs in the universe is capable of explaining the measured UHECR flux, making them promising UHECR sources. Interactions between UHECRs and the prompt gamma-ray emission of a GRB would produce neutrinos that would be detected in coincidence with the GRB’s gamma-ray emission. The IceCube Neutrino Observatory can be used to search for these neutrinos in coincidence with GRBs, detecting neutrinos through the Cherenkov radiation emitted by secondary charged particles produced in neutrino interactions in the South Pole glacial ice. Restricting these searches to be in coincidence with GRB gamma-ray emis- sion, analyses can be performed with very little atmospheric background. Previous searches have focused on detecting muon tracks from muon neutrino interactions fromthe Northern Hemisphere, where the Earth shields IceCube’s primary background of atmospheric muons, or spherical cascade events from neutrinos of all flavors from the entire sky, with no compelling neutrino signal found. Neutrino searches from GRBs with IceCube have been extended to a search for muon tracks in the Southern Hemisphere in coincidence with 664 GRBs over five years of IceCube data in this dissertation. Though this region of the sky contains IceCube’s primary background of atmospheric muons, it is also where IceCube is most sensitive to neutrinos at the very highest energies as Earth absorption in the Northern Hemisphere becomes relevant. As previous neutrino searches have strongly constrained neutrino production in GRBs, a new per-GRB analysis is introduced for the first time to discover neutrinos in coincidence with possibly rare neutrino-bright GRBs. A stacked analysis is also performed to discover a weak neutrino signal distributed over many GRBs. Results of this search are found to be consistent with atmospheric muon backgrounds. Combining this result with previously published searches for muon neutrino tracks in the Northern Hemisphere, cascade event searches over the entire sky, and an extension of the Northern Hemisphere track search in three additional years of IceCube data that is consistent with atmospheric backgrounds, the most stringent limits yet can be placed on prompt neutrino production in GRBs, which increasingly disfavor GRBs as primary sources of UHECRs in current GRB models.