Although originally conceived as an educational intervention for at-risk students, modern career academies have expanded their scope to programs designed to promote critical thinking, problem solving, and analytical skills to be successful in an advanced career path. Through the integration of career and technical education courses and a rigorous, college preparatory academic curriculum, career academies serve as a key piece of a larger strategy for developing a well- prepared STEM workforce. This study focuses on the Virginia Governor's STEM Academies, a state-wide initiative containing programs designed to expand options for the general student population to acquire STEM literacy and other critical skills, knowledge and credentials that will prepare them for high-demand, high-wage, and high-skill careers. Currently, 22 Academies exist serving students across 36 Virginia School Divisions. Using educational administrative data housed within the Virginia Longitudinal Data System, I examined the Virginia Governor's STEM Academies regarding characteristics of student participation and the relationship between Academy participation and high school and postsecondary outcomes. Using multi-level regression modeling, I found that male students, Asian and Hispanic students, and non-economically disadvantage students have a higher rate of Academy participation. After matching students with propensity score matching on demographic and early academic characteristics, I find that Academy participants are more likely to take Algebra II at an earlier grade, enroll in more Career and Technical Education and dual enrollment courses, and declare a STEM major after enrolling at a postsecondary institution. This research provides a valuable new contribution to the study of career academies after such educational programs have undergone a paradigm shift to preparing students for high-demand, high-wage, and high-skill careers. By incorporating propensity score matching and multi-level regression model, I employ a statistically rigorous approach that can serve as important benchmarking of the enrollment and academic outcomes of the Virginia Governor's STEM Academies. / Doctor of Philosophy / Although originally conceived as an educational intervention for at-risk students, modern career academies have expanded their scope to programs designed to promote critical thinking, problem solving, and analytical skills to be successful in an advanced career path. Through the integration of career and technical education courses and a rigorous, college preparatory academic curriculum, career academies serve as a key piece of a larger strategy for developing a well- prepared STEM workforce. This study focuses on the Virginia Governor's STEM Academies, a state-wide initiative containing programs designed to expand options for the general student population to acquire STEM literacy and other critical skills, knowledge and credentials that will prepare them for high-demand, high-wage, and high-skill careers. Currently, 22 Academies exist serving students across 36 Virginia School Divisions. Using educational administrative data housed within the Virginia Longitudinal Data System, I examined the Virginia Governor's STEM Academies regarding characteristics of student participation and the relationship between Academy participation and high school and postsecondary outcomes. Using multi-level regression modeling, I found that male students, Asian and Hispanic students, and non-economically disadvantage students have a higher rate of Academy participation. After matching students with propensity score matching on demographic and early academic characteristics, I find that Academy participants are more likely to take Algebra II at an earlier grade, enroll in more Career and Technical Education and dual enrollment courses, and declare a STEM major after enrolling at a postsecondary institution. This research provides a valuable new contribution to the study of career academies after such educational programs have undergone a paradigm shift to preparing students for high-demand, high-wage, and high-skill careers. By incorporating propensity score matching and multi-level regression model, I employ a statistically rigorous approach that can serve as important benchmarking of the enrollment and academic outcomes of the Virginia Governor's STEM Academies.

The increasing availability of richer, high-dimensional, home sales data-sets, as well as spatially geocoded data, allows for the use of new econometric and computational methods to explore novel research questions. This dissertation consists of three separate research papers which aim to leverage this trend to answer empirical inferential questions, propose new computational approaches in environmental valuation, and address future challenges. The first research chapter estimates the effect on home values of 10 large-scale urban stream restoration projects situated near the project sites. The study area is the Johnson Creek Watershed in Portland, Oregon. The research design incorporates four matching model approaches that vary based on the temporal bands' width, a narrow and a wider band, and two spatial zoning buffers, a smaller and larger that account for the affected homes' distances. Estimated effects tend to be positive for six projects when the restoration projects' distance is smaller, and the temporal bands are narrow, while two restoration projects have positive effects on home values across all four modeling approaches. The second research chapter focuses on the underlying statistical and computational properties of matching methods for causal treatment effects. The prevailing notion in the literature is that there is a tradeoff between bias and variance linked to the number of matched control observations for each treatment unit. In addition, in the era of Big Data, there is a paucity of research addressing the tradeoffs between inferential accuracy and computational time across different matching methods. Is it worth employing computationally costly matching methods if the gains in bias reduction and efficiency are negligible? We revisit the notion of bias-variance tradeoff and address the subject of computational time considerations. We conduct a simulation study and evaluate 160 models and 320 estimands. The results suggest that the conventional notion of a bias-variance tradeoff, with bias increasing and variance decreasing with the number of matched controls, does not hold under the bias-corrected matching estimator (BCME), developed by Abadie and Imbens (2011). Specifically, for the BCME, the trend of bias decreases as the number of matches per treated unit increases. Moreover, when the pre-matching balance's quality is already good, choosing only one match results in a significantly larger bias under all methods and estimators. In addition, the genetic search matching algorithm, GenMatch, is superior compared to the baseline Greedy Method by achieving a better balance between the observed covariate distributions of the treated and matched control groups. On the down side, GenMatch is 408 times slower compared to a greedy matching method. However, when we employ the BCME on matched data, there is a negligible difference in bias reduction between the two matching methods. Traditionally, environmental valuation methods using residential property transactions follow two approaches, hedonic price functions and Random Utility sorting models. An alternative approach is the Iterated Bidding Algorithm (IBA), introduced by Kuminoff and Jarrah (2010). This third chapter aims to improve the IBA approach to property and environmental valuation compared to its early applications. We implement this approach in an artificially simulated residential housing market, maintaining full control over the data generating mechanism. We implement the Mesh Adaptive Direct Search Algorithm (MADS) and introduce a convergence criterion that leverages the knowledge of individuals' actual pairing to homes. We proceed to estimate the preference parameters of the distribution of an underlying artificially simulated housing market. We estimate with significantly higher precision than the original baseline Nelder-Mead optimization that relied only on a price discrepancy convergence criterion, as implemented during the IBAs earlier applications. / Doctor of Philosophy / The increasing availability of richer, high-dimensional, home sales data sets enables us to employ new methods to explore novel research questions involving housing markets. This dissertation consists of three separate research papers which leverage this trend. The first research paper estimates the effects on home values of 10 large-scale urban stream restoration projects in Portland, Oregon. These homes are located near the project sites. The results show that the distance of the homes from the project sites and the duration of the construction cause different effects on home values. However, two restorations have positive effects regardless of the distance and the duration period. The second research study is focused on the issue of causality. The study demonstrates that a traditional notion concerning causality known as the ``bias-variance tradeoff" is not always valid. In addition, the research shows that sophisticated but time-consuming algorithms have negligible effects in improving the accuracy of estimating the causal effects when we account for the required computational time. The third research study improves an environmental evaluation method that relies on residential property transactions. The methodology leverages the features of more informative residential data sets in conjunction with a more efficient optimization method, leading to significant improvements. The study concludes that due to these improvements, this alternative method can be employed to elicit the true preferences of homeowners over housing and locational characteristics by avoiding the shortcomings of existing techniques.

<p dir="ltr">In today's big data environment, development of robust knowledge discovery solutions depends on integration of data from various sources. For example, intelligence agencies fuse data from multiple sources to identify criminal activities; e-commerce platforms consolidate user activities on various platforms and devices to build better user profile; scientists connect data from various modality to develop new drugs, and treatments. In all such activities, entities from different data sources need to be aligned---first, to ensure accurate analysis and more importantly, to discover novel knowledge regarding these entities. If the data sources are networks, aligning entities from different sources leads to the task of network alignment, which is the focus of this thesis. The main objective of this task is to find an optimal one-to-one correspondence among nodes in two or more networks utilizing graph topology and nodes/edges attributes. </p><p dir="ltr">In existing works, diverse computational schemes have been adopted for solving the network alignment task; these schemes include finding eigen-decomposition of similarity matrices, solving quadratic assignment problems via sub-gradient optimization, and designing iterative greedy matching techniques. Contemporary works approach this problem using a deep learning framework by learning node representations to identify matches. Node matching's key challenges include computational complexity and scalability. However, privacy concerns or unavailability often prevent the utilization of node attributes in real-world scenarios. In light of this, we aim to solve this problem by relying solely on the graph structure, without the need for prior knowledge, external attributes, or guidance from landmark nodes. Clearly, topology-based matching emerges as a hard problem when compared to other network matching tasks.</p><p dir="ltr">In this thesis, I propose two original works to solve network topology-based alignment task. The first work, Graphlet-based Alignment (Graphlet-Align), employs a topological approach to network alignment. Graphlet-Align represents each node with a local graphlet count based signature and use that as feature for deriving node to node similarity across a pair of networks. By using these similarity values in a bipartite matching algorithm Graphlet-Align obtains a preliminary alignment. It then uses high-order information extending to k-hop neighborhood of a node to further refine the alignment, achieving better accuracy. We validated Graphlet-Align's efficacy by applying it to various large real-world networks, achieving accuracy improvements ranging from $20\%$ to $72\%$ over state-of-the-art methods on both duplicated and noisy graphs.</p><p dir="ltr">Expanding on this paradigm that focuses solely on topology for solving graph alignment, in my second work, I develop a self-supervised learning framework known as Self-Supervised Topological Alignment (SST-Align). SST-Align uses graphlet-based signature for creating self-supervised node alignment labels, and then use those labels to generate node embedding vectors of both the networks in a joint space from which node alignment task can be effectively and accurately solved. It starts with an optimization process that applies average pooling on top of the extracted graphlet signature to construct an initial node assignment. Next, a self-supervised Siamese network architecture utilizes both the initial node assignment and graph convolutional networks to generate node embeddings through a contrastive loss. By applying kd-tree similarity to the two networks' embeddings, we achieve the final node mapping. Extensive testing on real-world graph alignment datasets shows that our developed methodology has competitive results compared to seven existing competing models in terms of node mapping accuracy. Additionally, we establish the Ablation Study to evaluate the two-stage accuracy, excluding the learning representation part and comparing the mapping accuracy accordingly.</p><p dir="ltr">This thesis enhances the theoretical understanding of topological features in the analysis of graph data for network alignment task, hence facilitating future advancements toward the field.</p>

In various business and military settings, there is an expectation of on-demand delivery of supplies and services. Typically, several delivery vehicles (also called servers) carry these supplies. Requests arrive one at a time and when a request arrives, a server is assigned to this request at a cost that is proportional to the distance between the server and the request. Bad assignments will not only lead to larger costs but will also create bottlenecks by increasing delivery time. There is, therefore, a need to design decision-making algorithms that produce cost-effective assignments of servers to requests in real-time. In this thesis, we consider the online bipartite matching problem where each server can serve exactly one request. In the online minimum metric bipartite matching problem, we are provided with a set of server locations in a metric space. Requests arrive one at a time that have to be immediately and irrevocably matched to a free server. The total cost of matching all the requests to servers, also known as the online matching is the sum of the cost of all the edges in the matching. There are many well-studied models for request generation. We study the problem in the adversarial model where an adversary who knows the decisions made by the algorithm generates a request sequence to maximize ratio of the cost of the online matching and the minimum-cost matching (also called the competitive ratio). An algorithm is a-competitive if the cost of online matching is at most 'a' times the minimum cost. A recently discovered robust and deterministic online algorithm (we refer to this as the robust matching or the RM-Algorithm) was shown to have optimal competitive ratios in the adversarial model and a relatively weaker random arrival model. We extend the analysis of the RM-Algorithm in the adversarial model and show that the competitive ratio of the algorithm is sensitive to the input, i.e., for "nice" input metric spaces or "nice" server placements, the performance guarantees of the RM-Algorithm is significantly better. In fact, we show that the performance is almost optimal for any fixed metric space and server locations. / Master of Science / In various business and military settings, there is an expectation of on-demand delivery of supplies and services. Typically, several delivery vehicles (also called servers) carry these supplies. Requests arrive one at a time and when a request arrives, a server is assigned to this request at a cost that is proportional to the distance between the server and the request. Bad assignments will not only lead to larger costs but will also create bottlenecks by increasing delivery time. There is, therefore, a need to design decision-making algorithms that produce cost-effective assignments of servers to requests in real-time. In this thesis, we consider the online bipartite matching problem where each server can serve exactly one request. In the online minimum metric bipartite matching problem, we are provided with a set of server locations in a metric space. Requests arrive one at a time that have to be immediately and irrevocably matched to a free server. The total cost of matching all the requests to servers, also known as the online matching is the sum of the cost of all the edges in the matching. There are many well-studied models for request generation. We study the problem in the adversarial model where an adversary who knows the decisions made by the algorithm generates a request sequence to maximize ratio of the cost of the online matching and the minimum-cost matching (also called the competitive ratio). An algorithm is α-competitive if the cost of online matching is at most α times the minimum cost. A recently discovered robust and deterministic online algorithm (we refer to this as the robust matching or the RM-Algorithm) was shown to have optimal competitive ratios in the adversarial model and a relatively weaker random arrival model. We extend the analysis of the RM-Algorithm in the adversarial model and show that the competitive ratio of the algorithm is sensitive to the input, i.e., for “nice” input metric spaces or “nice” server placements, the performance guarantees of the RM-Algorithm is significantly better. In fact, we show that the performance is almost optimal for any fixed metric space and server locations.

Matching is one of the most fundamental algorithmic graph problems. Many variants of matching problems have been studied on different classes of graphs, the one of special interest to us being the Maximum Cardinality Bipartite Matching in Planar Graphs. In this work, we present a novel sparsification based approach for computing maximum/perfect bipartite matching in planar graphs. The overall complexity of our algorithm is O(n^6/5 log² n) where n is the number of vertices in the graph, bettering the O(n^3/2) time achieved independently by Hopcroft-Karp algorithm and by Lipton and Tarjan divide and conquer approach using planar separators. Our algorithm combines the best of both these standard algorithms along with our sparsification technique and rich planar graph properties to achieve the speed up. Our algorithm is not the fastest, with the existence of O(n log³ n) algorithm based on max-flow reduction. / MS / A matching in a graph can be defined as a subset of edges without common vertices. A matching algorithm finds a maximum set of such vertex-disjoint edges. Many real life resource allocation problems can be solved efficiently by modelling them as a matching problem. While many variants of matching problems have been studied on different classes of graphs, the simplest and the most popular among them is the Maximum Cardinality Bipartite Matching problem. Bipartite matching arises in varied applications like matching applicants to job openings, matching ads to user queries, matching threads to tasks in OS scheduler, matching protein sequences based on their structures and so on. In this work, we present an efficient algorithm for computing maximum cardinality bipartite matching in planar graphs. Planar graphs are sparse graphs and have interesting structural properties which allow us to design faster algorithms in planar setting for problems that are otherwise considered hard in arbitrary graphs. We use a new sparsification based approach where we maintain a compact and accurate representation of the original graph with a lesser number of vertices. Our algorithm combines the features of the best known bipartite matching algorithm for an arbitrary graph with the novel sparsification approach to achieve the speedup.

Distributed adaptive computing systems (ACS) allow developers to design applications using multiple programmable devices. The ACS API, an API created for distributed adaptive com-puting, gives developers the ability to design scalable ACS systems in a cluster networking environment for large applications. One such application, found in the field of bioinformatics, is the DNA sequence alignment problem. This thesis presents a runtime reconfigurable FPGA implementation of the Smith-Waterman similarity comparison algorithm. Additionally, this thesis presents tools designed for the ACS API that assist developers creating applications in a heterogeneous distributed adaptive computing environment. / Master of Science

Microwave processing of ceramics has seen a growth in research and development efforts throughout the past decade. One area of interest is the exploration of improved heating control through experiments and numerical modeling. Controlled heating may be used to counteract non-uniform heating and avoid destructive phenomena such as cracking and thermal runaway. Thermal runaway is a potential problem in materials with temperature dependent dielectric properties. As the material absorbs electromagnetic energy, the temperature increases as does its ability to absorb more energy. Controlled processing of the material may be achieved by manipulating the applied field. The purpose of this research is to model the interaction of the EM-field with a thin ceramic fiber to investigate possible mechanisms that may affect the heating process. The fiber undergoes microwave heating in a single-mode resonant applicator. Maxwell's equations for the fields within the cavity are solved using mode-matching techniques taking into account the field interaction of the fiber and an arbitrarily shaped coupling aperture. Effects of varying the aperture shape on the field distribution are explored. The coupled nature of the electromagnetic solution with the material's temperature-dependent properties, including an analysis of non-uniform heating, is also discussed. / Master of Science

Data analysis is the process of inspecting, cleaning, extract, and modeling data with the intention of extracting useful information in order to support users in their decisions. With the advent of Big Data, data analysis was becoming more complicated due to the volume and variety of data. This process begins with the acquisition of the data and the selection of the data that is useful for the desiderata analysis. With such amount of data, also expert users are not able to inspect the data and understand if a dataset is suitable or not for their purposes. In this dissertation, we focus on five problems in the broad data analysis process to help users find insights from the data when they do not have enough knowledge about its data. First, we analyze the data description problem, where the user is looking for a description of the input dataset. We introduce data descriptions: a compact, readable and insightful formula of boolean predicates that represents a set of data records. Finding the best description for a dataset is computationally expensive and task-specific; we, therefore, introduce a set of metrics and heuristics for generating meaningful descriptions at an interactive performance. Secondly, we look at the problem of order dependency discovery, which discovers another kind of metadata that may help the user in the understanding of characteristics of a dataset. Our approach leverages the observation that discovering order dependencies can be guided by the discovery of a more specific form of dependencies called order compatibility dependencies. Thirdly, textual data encodes much hidden information. To allow this data to reach its full potential, there has been an increasing interest in extracting structural information from it. In this regard, we propose a novel approach for extracting events that are based on temporal co-reference among entities. We consider an event to be a set of entities that collectively experience relationships between them in a specific period of time. We developed a distributed strategy that is able to scale with the largest on-line encyclopedia available, Wikipedia. Then, we deal with the evolving nature of the data by focusing on the problem of finding synonymous attributes in evolving Wikipedia Infoboxes. Over time, several attributes have been used to indicate the same characteristic of an entity. This provides several issues when we are trying to analyze the content of different time periods. To solve it, we propose a clustering strategy that combines two contrasting distance metrics. We developed an approximate solution that we assess over 13 years of Wikipedia history by proving its flexibility and accuracy. Finally, we tackle the problem of identifying movements of attributes in evolving datasets. In an evolving environment, entities not only change their characteristics, but they sometimes exchange them over time. We proposed a strategy where we are able to discover those cases, and we also test our strategy on real datasets. We formally present the five problems that we validate both in terms of theoretical results and experimental evaluation, and we demonstrate that the proposed approaches efficiently scale with a large amount of data.

Le début des années 2000 a vu la cartographie du génome humain se réaliser après 13 ans de recherche. Le défi du prochain siècle réside dans la construction du connectome humain, qui consiste à cartographier les connexions du cerveau en utilisant l’imagerie par résonance magnétique (IRM) de diffusion. Cette technique permet en effet d’étudier la matière blanche du cerveau de façon complètement non invasive. Bien que le défi soit monumental, la résolution d’une image d’IRM se situe à l’échelle macroscopique et est environ 1000 fois inférieure à la taille des axones qu’il faut cartographier. Pour aider à pallier à ce problème, ce mémoire propose une nouvelle technique de débruitage spécialement conçue pour l’imagerie de diffusion. L’algorithme Non Local Spatial and Angular Matching (NLSAM) se base sur les principes du block matching et du dictionary learning pour exploiter la redondance des données d’IRM de diffusion. Un seuillage sur les voisins angulaire est aussi réalisé à l’aide du sparse coding, où l’erreur de reconstruction en norme l2 est bornée par la variance locale du bruit. L’algorithme est aussi conçu pour gérer le biais du bruit Ricien et Chi non centré puisque les images d’IRM contiennent du bruit non Gaussien. Ceci permet ainsi d’acquérir des données d’IRM de diffusion à une plus grande résolution spatiale que présentement disponible en milieu clinique. Ce travail ouvre donc la voie à un meilleur type d’acquisition, ce qui pourrait contribuer à révéler de nouveaux détails anatomiques non discernables à la résolution spatiale présentement utilisée par la communauté d’IRM de diffusion. Ceci pourrait aussi éventuellement contribuer à identifier de nouveaux biomarqueurs permettant de comprendre les maladies dégénératives telles que la sclérose en plaques, la maladie d’Alzheimer et la maladie de Parkinson.

Thèse numérisée par la Division de la gestion de documents et des archives de l'Université de Montréal.