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.

Ledroit Park, A Portrait In Black And White: A Study Of Historic Districts, Social Change, And The Process Of Neighborhood Placemaking

This research examines the process of placemaking in LeDroit Park, a residential Washington, DC, neighborhood with a historic district at its core. Unpacking the entwined physical and social evolution of the small community within the context of the Nation’s Capital, this analysis provides insight into the role of urban design and development as well as historic designation on shaping collective identity. Initially planned and designed in 1873 as a gated suburb just beyond the formal L’Enfant-designed city boundary, LeDroit Park was intended as a retreat for middle and upper-class European Americans from the growing density and social diversity of the city. With a mixture of large romantic revival mansions and smaller frame cottages set on grassy plots evocative of an idealized rural village, the physical design was intentionally inwardly-focused. This feeling of refuge was underscored with a physical fence that surrounded the development, intended to prevent African Americans from nearby Howard University and the surrounding neighborhood, from using the community’s private streets to access the City of Washington. Within two decades of its founding, LeDroit Park was incorporated into the District of Columbia, the surrounding fence was demolished, and the neighborhood was racially integrated. Due to increasingly stringent segregation laws and customs in the city, this period of integration lasted less than twenty years, and LeDroit Park developed into an elite African American enclave, using the urban design as a bulwark against the indignities of a segregated city. Throughout the 20th century housing infill and construction increased density, yet the neighborhood never lost the feeling of security derived from the neighborhood plan. Highlighting the architecture and street design, neighbors successfully received historic district designation in 1974 in order to halt campus expansion. After a stalemate that lasted two decades, the neighborhood began another period of transformation, both racial and socio-economic, catalyzed by a multi-pronged investment program led by Howard University. Through interviews with long-term and new community members, this investigation asserts that the 140-year development history, including recent physical interventions, is integral to placemaking, shaping the material character as well as the social identity of residents.