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 INFLUENCE OF URBAN FORM AT DIFFERENT GEOGRAPHICAL SCALES ON TRAVEL BEHAVIOR; EVIDENCE FROM U.S. CITIES

Suburban lifestyle is popular among American families, although it has been criticized for encouraging automobile use through longer commutes, causing heavy traffic congestion, and destroying open spaces (Handy, 2005). It is a serious concern that people living in low-density suburban areas suffer from high automobile dependency and lower rates of daily physical activity, both of which result in social, environmental and health-related costs. In response to such concerns, researchers have investigated the inter-relationships between urban land-use pattern and travel behavior within the last few decades and suggested that land-use planning can play a significant role in changing travel behavior in the long-term. However, debates regarding the magnitude and efficiency of the effects of land-use on travel patterns have been contentious over the years. Changes in built-environment patterns is potentially considered a long-term panacea for automobile dependency and traffic congestion, despite some researchers arguing that the effects of land-use on travel behavior are minor, if any. It is still not clear why the estimated impact is different in urban areas and how effective a proposed land-use change/policy is in changing certain travel behavior. This knowledge gap has made it difficult for decision-makers to evaluate land-use plans and policies. In addition, little is known about the influence of the large-scale built environment. In the present dissertation, advanced spatial-statistical tools have been employed to better understand and analyze these impacts at different scales, along with analyzing transit-oriented development policy at both small and large scales. The objective of this research is to: (1) develop scalable and consistent measures of the overall physical form of metropolitan areas; (2) re-examine the effects of built-environment factors at different hierarchical scales on travel behavior, and, in particular, on vehicle miles traveled (VMT) and car ownership; and (3) investigate the effects of transit-oriented development on travel behavior. The findings show that changes in built-environment at both local and regional levels could be very influential in changing travel behavior. Specifically, the promotion of compact, mixed-use built environment with well-connected street networks reduces VMT and car ownership, resulting in less traffic congestion, air pollution, and energy consumption.