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.

Essays on the Effects of Social Insurance for Disability

This dissertation examines how social insurance, family support and work capacity enhance individuals' economic well-being following significant health and income shocks. I first examine the extent to which the liquidity-enhancing effects of Worker's Compensation (WC) benefits outweigh the moral hazard costs. Analyzing administrative data from Oregon, I estimate a hazard model exploiting variation in the timing and size of a retroactive lump-sum WC payment to decompose the elasticity of claim duration with respect to benefits into the elasticity with respect to an increase in cash on hand, and a decrease in the opportunity cost of missing work. I find that the liquidity effect accounts for 60 to 65 percent of the increase in claim duration among lower-wage workers, but less than half of the increase for higher earners. Using the framework from Chetty (2008), I conclude that the insurance value of WC exceeds the distortionary cost, and increasing the benefit level could increase social welfare. Next, I investigate how government-provided disability insurance (DI) interacts with private transfers to disabled individuals from their grown children. Using the Health and Retirement Study, I estimate a fixed effects, difference in differences regression to compare transfers between DI recipients and two control groups: rejected applicants and a reweighted sample of disabled non-applicants. I find that DI reduces the probability of receiving a transfer by no more than 3 percentage points, or 10 percent. Additional analysis reveals that DI could increase the probability of receiving a transfer in cases where children had limited prior information about the disability, suggesting that DI could send a welfare-improving information signal. Finally, Zachary Morris and I examine how a functional assessment could complement medical evaluations in determining eligibility for disability benefits and in targeting return to work interventions. We analyze claimants' self-reported functional capacity in a survey of current DI beneficiaries to estimate the share of disability claimants able to do work-related activity. We estimate that 13 percent of current DI beneficiaries are capable of work-related activity. Furthermore, other characteristics of these higher-functioning beneficiaries are positively correlated with employment, making them an appropriate target for return to work interventions.