Top-K Query Processing in Edge-Labeled Graph Data

Edge-labeled graphs have proliferated rapidly over the last decade due to the increased popularity of social networks and the Semantic Web. In social networks, relationships between people are represented by edges and each edge is labeled with a semantic annotation. Hence, a huge single graph can express many different relationships between entities. The Semantic Web represents each single fragment of knowledge as a triple (subject, predicate, object), which is conceptually identical to an edge from subject to object labeled with predicates. A set of triples constitutes an edge-labeled graph on which knowledge inference is performed. Subgraph matching has been extensively used as a query language for patterns in the context of edge-labeled graphs. For example, in social networks, users can specify a subgraph matching query to find all people that have certain neighborhood relationships. Heavily used fragments of the SPARQL query language for the Semantic Web and graph queries of other graph DBMS can also be viewed as subgraph matching over large graphs. Though subgraph matching has been extensively studied as a query paradigm in the Semantic Web and in social networks, a user can get a large number of answers in response to a query. These answers can be shown to the user in accordance with an importance ranking. In this thesis proposal, we present four different scoring models along with scalable algorithms to find the top-k answers via a suite of intelligent pruning techniques. The suggested models consist of a practically important subset of the SPARQL query language augmented with some additional useful features. The first model called Substitution Importance Query (SIQ) identifies the top-k answers whose scores are calculated from matched vertices' properties in each answer in accordance with a user-specified notion of importance. The second model called Vertex Importance Query (VIQ) identifies important vertices in accordance with a user-defined scoring method that builds on top of various subgraphs articulated by the user. Approximate Importance Query (AIQ), our third model, allows partial and inexact matchings and returns top-k of them with a user-specified approximation terms and scoring functions. In the fourth model called Probabilistic Importance Query (PIQ), a query consists of several sub-blocks: one mandatory block that must be mapped and other blocks that can be opportunistically mapped. The probability is calculated from various aspects of answers such as the number of mapped blocks, vertices' properties in each block and so on and the most top-k probable answers are returned. An important distinguishing feature of our work is that we allow the user a huge amount of freedom in specifying: (i) what pattern and approximation he considers important, (ii) how to score answers - irrespective of whether they are vertices or substitution, and (iii) how to combine and aggregate scores generated by multiple patterns and/or multiple substitutions. Because so much power is given to the user, indexing is more challenging than in situations where additional restrictions are imposed on the queries the user can ask. The proposed algorithms for the first model can also be used for answering SPARQL queries with ORDER BY and LIMIT, and the method for the second model also works for SPARQL queries with GROUP BY, ORDER BY and LIMIT. We test our algorithms on multiple real-world graph databases, showing that our algorithms are far more efficient than popular triple stores.

Balancing Belligerents or Feeding the Beast: Transforming Conflict Traps

Since the end of the Cold War, recurring civil conflicts have been the dominant form of violent armed conflict in the world, accounting for 70% of conflicts active between 2000-2013. Duration and intensity of episodes within recurring conflicts in Africa exhibit four behaviors characteristic of archetypal dynamic system structures. The overarching questions asked in this study are whether these patterns are robustly correlated with fundamental concepts of resiliency in dynamic systems that scale from micro-to macro levels; are they consistent with theoretical risk factors and causal mechanisms; and what are the policy implications. Econometric analysis and dynamic systems modeling of 36 conflicts in Africa between 1989 -2014 are combined with process tracing in a case study of Somalia to evaluate correlations between state characteristics, peace operations and foreign aid on the likelihood of observed conflict patterns, test hypothesized causal mechanisms across scales, and develop policy recommendations for increasing human security while decreasing resiliency of belligerents. Findings are that observed conflict patterns scale from micro to macro levels; are strongly correlated with state characteristics that proxy a mix of cooperative (e.g., gender equality) and coercive (e.g., security forces) conflict-balancing mechanisms; and are weakly correlated with UN and regional peace operations and humanitarian aid. Interactions between peace operations and aid interventions that effect conflict persistence at micro levels are not seen in macro level analysis, due to interdependent, micro-level feedback mechanisms, sequencing, and lagged effects. This study finds that the dynamic system structures associated with observed conflict patterns contain tipping points between balancing mechanisms at the interface of micro-macro level interactions that are determined as much by factors related to how intervention policies are designed and implemented, as what they are. Policy implications are that reducing risk of conflict persistence requires that peace operations and aid interventions (1) simultaneously increase transparency, promote inclusivity (with emphasis on gender equality), and empower local civilian involvement in accountability measures at the local levels; (2) build bridges to horizontally and vertically integrate across levels; and (3) pave pathways towards conflict transformation mechanisms and justice that scale from the individual, to community, regional, and national levels.

MOWING TO GROWING: TRANSFORMING A MUNICIPAL GOLF COURSE TO URBAN AGRICULTURE IN BALTIMORE CITY

This thesis demonstrates how landscape architects can transform underused golf course facilities located within cities for urban agriculture (UA). In the last decade more than 1000 golf courses have closed in the United States. Municipal golf courses represent some of the largest pieces of open space in cities and because of their inherent infrastructure they can provide the ideal location to support large-scale UA. In Southwest Baltimore large food deserts are a serious health concern and represent a lack of access to healthy food options for residents. Carroll Urban Agriculture Park is a design response resulting from a detailed analysis of the existing Carroll Park Golf Course and the surrounding community of Southwest Baltimore. The design will create an urban farm in a park-like setting to provide readily accessible healthy food options and various educational opportunities, and to support current and future urban agriculture related businesses in Baltimore.

The Indistinct Edge: Reconnecting Experience in Nature and Architecture

This thesis explores how architectures sense of place is rooted in the natural environment. The built environment has been constructed to protect and sustain human culture from the weathering of nature. Separating experience from the natural environment removes a sense of place and belonging in the natural and reinforces architectural dominance. This separation distinguishes the natural world as an article of spectacle and gives the human experience an unnatural voyeurship to natural changes. By examining the fusion of architectural and natural edges this thesis analyzes how the human experience can reconnect with a naturalistic sense of place through architecture, blending the finite edge where architecture maintains nature, and adapting buildings to the cycles of the environment. Removing dominance of man-made spaces and replacing them with the cohabitation of the edge between built and natural forms.