Almost Stable Matchings by Truncating the Gale–Shapley Algorithm

We show that the ratio of matched individuals to blocking pairs grows linearly with the number of propose–accept rounds executed by the Gale–Shapley algorithm for the stable marriage problem. Consequently, the participants can arrive at an almost stable matching even without full information about the problem instance; for each participant, knowing only its local neighbourhood is enough. In distributed-systems parlance, this means that if each person has only a constant number of acceptable partners, an almost stable matching emerges after a constant number of synchronous communication rounds. We apply our results to give a distributed (2 + ε)-approximation algorithm for maximum-weight matching in bicoloured graphs and a centralised randomised constant-time approximation scheme for estimating the size of a stable matching.

Auditory - Visual Matching in Learning Disabilities : Intervention Studies from Finland and Sweden

The present thesis discusses relevant issues in education: 1) learning disabilities including the role of comorbidity in LDs, and 2) the use of research-based interventions. This thesis consists of a series of four studies (three articles), which deepens the knowledge of the field of special education. Intervention studies (N=242) aimed to examine whether training using a nonverbal auditory-visual matching computer program had a remedial effect in different learning disabilities, such as developmental dyslexia, Attention Deficit Disorder (ADD) and Specific Language Impairment (SLI). These studies were conducted in both Finland and Sweden. The intervention’s non-verbal character made an international perspective possible. The results of the intervention studies confirmed, that the auditory-visual matching computer program, called Audilex had positive intervention effects. In Study I of children with developmental dyslexia there were also improvements in reading skills, specifically in reading nonsense words and reading speed. These improvements in tasks, which are thought to rely on phonological processing, suggest that such reading difficulties in dyslexia may stem in part from more basic perceptual difficulties, including those required to manage the visual and auditory components of the decoding task. In Study II the intervention had a positive effect on children with dyslexia; older students with dyslexia and surprisingly, students with ADD also benefited from this intervention. In conclusion, the role of comorbidity was apparent. An intervention effect was evident also in students’ school behavior. Study III showed that children with SLI experience difficulties very similar to those of children with dyslexia in auditory-visual matching. Children with language-based learning disabilities, such as dyslexia and SLI benefited from the auditory-visual matching intervention. Also comorbidity was evident among these children; in addition to formal diagnoses, comorbidity was explored with an assessment inventory, which was developed for this thesis. Interestingly, an overview of the data of this thesis shows positive intervention effects in all studies despite learning disability, language, gender or age. These findings have been described by a concept inter-modal transpose. Self-evidently these issues need further studies. In learning disabilities the aim in the future will also be to identify individuals at risk rather than by deficit; this aim can be achieved by using research-based interventions, intensified support in general education and inclusive special education. Keywords: learning disabilities, developmental dyslexia, attention deficit disorder, specific language impairment, language-based learning disabilities, comorbidity, auditory-visual matching, research-based interventions, inter-modal transpose

Isotopic fingerprints in surficial waters : Stable isotope methods applied in hydrogeological studies

The driving force behind this study has been the need to develop and apply methods for investigating the hydrogeochemical processes of significance to water management and artificial groundwater recharge. Isotope partitioning of elements in the course of physicochemical processes produces isotopic variations to their natural reservoirs. Tracer property of the stable isotope abundances of oxygen, hydrogen and carbon has been applied to investigate hydrogeological processes in Finland. The work described here has initiated the use of stable isotope methods to achieve a better understanding of these processes in the shallow glacigenic formations of Finland. In addition, the regional precipitation and groundwater records will supplement the data of global precipitation, but as importantly, provide primary background data for hydrological studies. The isotopic composition of oxygen and hydrogen in Finnish groundwaters and atmospheric precipitation was determined in water samples collected during 1995 2005. Prior to this study, no detailed records existed on the spatial or annual variability of the isotopic composition of precipitation or groundwaters in Finland. Groundwaters and precipitation in Finland display a distinct spatial distribution of the isotopic ratios of oxygen and hydrogen. The depletion of the heavier isotopes as a function of increasing latitude is closely related to the local mean surface temperature. No significant differences were observed between the mean annual isotope ratios of oxygen and hydrogen in precipitation and those in local groundwaters. These results suggest that the link between the spatial variability in the isotopic composition of precipitation and local temperature is preserved in groundwaters. Artificial groundwater recharge to glaciogenic sedimentary formations offers many possibilities to apply the isotopic ratios of oxygen, hydrogen and carbon as natural isotopic tracers. In this study the systematics of dissolved carbon have been investigated in two geochemically different glacigenic groundwater formations: a typical esker aquifer at Tuusula, in southern Finland and a carbonate-bearing aquifer with a complex internal structure at Virttaankangas, in southwest Finland. Reducing the concentration of dissolved organic carbon (DOC) in water is a primary challenge in the process of artificial groundwater recharge. The carbon isotope method was used to as a tool to trace the role of redox processes in the decomposition of DOC. At the Tuusula site, artificial recharge leads to a significant decrease in the organic matter content of the infiltrated water. In total, 81% of the initial DOC present in the infiltrated water was removed in three successive stages of subsurface processes. Three distinct processes in the reduction of the DOC content were traced: The decomposition of dissolved organic carbon in the first stage of subsurface flow appeared to be the most significant part in DOC removal, whereas further decrease in DOC has been attributed to adsorption and finally to dilution with local groundwater. Here, isotope methods were used for the first time to quantify the processes of DOC removal in an artificial groundwater recharge. Groundwaters in the Virttaankangas aquifer are characterized by high pH values exceeding 9, which are exceptional for shallow aquifers on glaciated crystalline bedrock. The Virttaankangas sediments were discovered to contain trace amounts of fine grained, dispersed calcite, which has a high tendency to increase the pH of local groundwaters. Understanding the origin of the unusual geochemistry of the Virttaankangas groundwaters is an important issue for constraining the operation of the future artificial groundwater plant. The isotope ratios of oxygen and carbon in sedimentary carbonate minerals have been successfully applied to constrain the origin of the dispersed calcite in the Virttaankangas sediments. The isotopic and chemical characteristics of the groundwater in the distinct units of aquifer were observed to vary depending on the aquifer mineralogy, groundwater residence time and the openness of the system to soil CO2. The high pH values of > 9 have been related to dissolution of calcite into groundwater under closed or nearly closed system conditions relative to soil CO2, at a low partial pressure of CO2.

Efficient Content-based Routing, Mobility-aware Topologies, and Temporal Subspace Matching

Event-based systems are seen as good candidates for supporting distributed applications in dynamic and ubiquitous environments because they support decoupled and asynchronous many-to-many information dissemination. Event systems are widely used, because asynchronous messaging provides a flexible alternative to RPC (Remote Procedure Call). They are typically implemented using an overlay network of routers. A content-based router forwards event messages based on filters that are installed by subscribers and other routers. The filters are organized into a routing table in order to forward incoming events to proper subscribers and neighbouring routers. This thesis addresses the optimization of content-based routing tables organized using the covering relation and presents novel data structures and configurations for improving local and distributed operation. Data structures are needed for organizing filters into a routing table that supports efficient matching and runtime operation. We present novel results on dynamic filter merging and the integration of filter merging with content-based routing tables. In addition, the thesis examines the cost of client mobility using different protocols and routing topologies. We also present a new matching technique called temporal subspace matching. The technique combines two new features. The first feature, temporal operation, supports notifications, or content profiles, that persist in time. The second feature, subspace matching, allows more expressive semantics, because notifications may contain intervals and be defined as subspaces of the content space. We also present an application of temporal subspace matching pertaining to metadata-based continuous collection and object tracking.

Data fusion and matching by maximizing statistical dependencies

The core aim of machine learning is to make a computer program learn from the experience. Learning from data is usually defined as a task of learning regularities or patterns in data in order to extract useful information, or to learn the underlying concept. An important sub-field of machine learning is called multi-view learning where the task is to learn from multiple data sets or views describing the same underlying concept. A typical example of such scenario would be to study a biological concept using several biological measurements like gene expression, protein expression and metabolic profiles, or to classify web pages based on their content and the contents of their hyperlinks. In this thesis, novel problem formulations and methods for multi-view learning are presented. The contributions include a linear data fusion approach during exploratory data analysis, a new measure to evaluate different kinds of representations for textual data, and an extension of multi-view learning for novel scenarios where the correspondence of samples in the different views or data sets is not known in advance. In order to infer the one-to-one correspondence of samples between two views, a novel concept of multi-view matching is proposed. The matching algorithm is completely data-driven and is demonstrated in several applications such as matching of metabolites between humans and mice, and matching of sentences between documents in two languages.

Empirical Studies on Labor Market Matching (summary section only)

This thesis analyzes how matching takes place at the Finnish labor market from three different angles. The Finnish labor market has undergone severe structural changes following the economic crisis in the early 1990s. The labor market has had problems adjusting from these changes and hence a high and persistent unemployment has followed. In this thesis I analyze if matching problems, and in particular if changes in matching, can explain some of this persistence. The thesis consists of three essays. In the first essay Finnish Evidence of Changes in the Labor Market Matching Process the matching process at the Finnish labor market is analyzed. The key finding is that the matching process has changed thoroughly between the booming 1980s and the post-crisis period. The importance of the number of unemployed, and in particular long-term unemployed, for the matching process has vanished. More unemployed do not increase matching as theory predicts but rather the opposite. In the second essay, The Aggregate Matching Function and Directed Search -Finnish Evidence, stock-flow matching as a potential micro foundation of the aggregate matching function is studied. In the essay I show that newly unemployed match mainly with the stock of vacancies while longer term unemployed match with the inflow of vacancies. When aggregating I still find evidence of the traditional aggregate matching function. This could explain the huge support the aggregate matching function has received despite its odd randomness assumption. The third essay, How do Registered Job Seekers really match? -Finnish occupational level Evidence, studies matching for nine occupational groups and finds that very different matching problems exist for different occupations. In this essay also misspecification stemming from non-corresponding variables is dealt with through the introduction of a completely new set of variables. The new outflow measure used is vacancies filled with registered job seekers and it is matched by the supply side measure registered job seekers.

Environmental and climatic dependences of stable isotope ratios in tree rings on different temporal scales

This work examines stable isotope ratios of carbon, oxygen and hydrogen in annual growth rings of trees. Isotopic composition in wood cellulose is used as a tool to study past climate. The method benefits from the accurate and precise dating provided by dendrochronology. In this study the origin, nature and the strength of climatic correlations are studied on different temporal scales and at different sites in Finland. The origin of carbon isotopic signal is in photosynthetic fractionation. The basic physical and chemical fractionations involved are reasonably well understood. This was confirmed by measuring instantaneous photosynthetic discrimination on Scots pine (Pinus sylvestris L.). The internal conductance of CO2 was recognized to have a significant impact on the observed fractionation, and further investigations are suggested to quantify its role in controlling the isotopic signal of photosynthates. Isotopic composition of the produced biomass can potentially be affected by variety of external factors that induce physiological changes in trees. Response of carbon isotopic signal in tree ring cellulose to changes in resource availability was assessed in a manipulation experiment. It showed that the signal was relatively stable despite of changes in water and nitrogen availability to the tree. Palaeoclimatic reconstructions are typically based on functions describing empirical relationship between isotopic and climatic parameters. These empirical relationships may change depending on the site conditions, species and timeframe studied. Annual variation in Scots pine tree ring carbon and oxygen isotopic composition was studied in northern and in central eastern Finland and annual variation in tree ring latewood carbon, oxygen and hydrogen isotopic ratio in Oak (Quercus robur L.) was studied in southern Finland. In all of the studied sites at least one of the studied isotope ratios was shown to record climate strongly enough to be used in climatic reconstructions. Using the observed relationships, four-century-long climate reconstructions from living Scots pine were created for northern and central eastern Finland. Also temporal stability of the relationships between three proxy indicators, tree ring growth and carbon and oxygen isotopic composition was studied during the four-hundred-year period. Isotope ratios measured from tree rings in Finland were shown to be sensitive indicators of climate. Increasing understanding of environmental controls and physiological mechanisms affecting tree ring isotopic composition will make possible more accurate interpretation of isotope data. This study also demonstrated that by measuring multiple isotopes and physical proxies from the same tree rings, additional information on tree physiology can be obtained. Thus isotopic ratios measured from tree ring cellulose provide means to improve the reliability of climate reconstructions.