Finding the shortest paths in a graph has been studied for a long time, and there are many main memory based algorithms dealing with this problem. Among these, Dijkstra's shortest path algorithm is one of the most commonly used efficient algorithms to the non-negative graphs. Even more efficient algorithms have been developed recently for graphs with particular properties such as the weights of edges fall into a range of integer. All of the mentioned algorithms require the graph totally reside in the main memory. Howevery, for very large graphs, such as the digital maps managed by Geographic Information Systems (GIS), the requirement cannot be satisfied in most cases, so the algorithms mentioned above are not appropriate. My objective in this thesis is to design and evaluate the performance of external memory (disk-based) shortest path algorithms and data structures to solve the shortest path problem in very large digital maps. In particular the following questions are studied:What have other researchers done on the shortest path queries in very large digital maps?What could be improved on the previous works? How efficient are our new shortest paths algorithms on the digital maps, and what factors affect the efficiency? What can be done based on the algorithm? In this thesis, we give a disk-based Dijkstra's-like algorithm to answer shortest path queries based on pre-processing information. Experiments based on our Java implementation are given to show what factors affect the running time of our algorithms.

Internet Telephony defined as real time voice or multimediacommunications over packet switched networks dates back to theearly days of the Internet. ARPA's Network SecureCommunications project had implemented, as early as December1973, an infrastructure for local and transnet real time voicecommunication. Two main sets of standards have emerged: H. 323from the ITU-T and the session initiation protocol (SIP) fromthe Internet Engineering Task Force (IETF). Both includespecifications for value added services. Value added services,or more simply services, are critical to service providers'survival and success. Unfortunately, the service architecturesthat come with the ITU-T and the IETF sets of standards arerather weak. Although they are constantly evolving,alternatives and complements need to be researched. This thesiswhich is made up of a formal dissertation and 6 appendices,proposes a novel mobile agent based service architecture forInternet Telephony. The architecture addresses the issues noneof the existing architectures solves in a satisfactory manner.Furthermore it adds mobile agents to the panoply of servicecreation tools. The appendices are reprints of articlespublished in refereed magazines/journals or under considerationfor publication. The formal dissertation is a summary of thepublications. A consistent and comprehensive set ofrequirements are derived. They are TINA-C flavored, but adaptedto Internet Telephony. They are used to critically reviewrelated work and also used to motivate the use of mobile agentsas the pillars of a novel architecture. The components of thisnovel architecture are identified. The key component is themobile service agent. It acts as a folder and carriesservice(s) to which the end-user has subscribed. Mobile serviceagents need to be upgraded when new versions of service logicare available and when end-users make changes to service data.This thesis proposes a novel upgrading framework. The currentInternet infrastructure comprises a wide range of hosts. Mobileagent platforms are now available for most of thesehosts/clients including memory/processing power constrainedPDAs. Our mobile service agents need to adapt to hostvariability when roaming. A novel adaptivity framework is alsoproposed. These two frameworks are general and can be appliedto any other mobile agent which meets a basic set ofassumptions. A key advantage of a mobile agent based servicearchitecture is that it enables the developement of mobileagent based services. The thesis proposes a novel mobile agentbased multi-party session scheduler. The feasibility and theadvantages of the architecture proposed by this thesis havebeen demonstrated by a prototype on which measurements havebeen made. Future work includes the addition of a securityframework to the architecture, and refinenements to theupgrading and adaptivity frameworks. More mobile agent basedservices, especially mobile multi agent based services willalso be developed. / <p>NR 20140805</p>

In many practical scenarios, prediction for high-dimensional observations can be accurately performed using only a fraction of the existing features. However, the set of relevant predictive features, known as the sparsity pattern, varies across data. For instance, features that are informative for a subset of observations might be useless for the rest. In fact, in such cases, the dataset can be seen as an aggregation of samples belonging to several low-dimensional sub-models, potentially due to different generative processes. My thesis introduces several techniques for identifying sparse predictive structures and the areas of the feature space where these structures are effective. This information allows the training of models which perform better than those obtained through traditional feature selection. We formalize Informative Projection Recovery, the problem of extracting a set of low-dimensional projections of data which jointly form an accurate solution to a given learning task. Our solution to this problem is a regression-based algorithm that identifies informative projections by optimizing over a matrix of point-wise loss estimators. It generalizes to a number of machine learning problems, offering solutions to classification, clustering and regression tasks. Experiments show that our method can discover and leverage low-dimensional structure, yielding accurate and compact models. Our method is particularly useful in applications involving multivariate numeric data in which expert assessment of the results is of the essence. Additionally, we developed an active learning framework which works with the obtained compact models in finding unlabeled data deemed to be worth expert evaluation. For this purpose, we enhance standard active selection criteria using the information encapsulated by the trained model. The advantage of our approach is that the labeling effort is expended mainly on samples which benefit models from the hypothesis class we are considering. Additionally, the domain experts benefit from the availability of informative axis aligned projections at the time of labeling. Experiments show that this results in an improved learning rate over standard selection criteria, both for synthetic data and real-world data from the clinical domain, while the comprehensible view of the data supports the labeling process and helps preempt labeling errors.

Package party, implemented in the R system for statistical computing, provides basic classes and methods for recursive partitioning along with reference implementations for three recently-suggested tree-based learners: conditional inference trees and forests, and model-based recursive partitioning. / Series: Research Report Series / Department of Statistics and Mathematics

Graph-partitioning problems can be generically defined as a family of problems in which we are asked to partition a graph into two or more components. We present overview of methods and concepts used to find best graph partitions according to several criteria. We prove duality of multi-commodity flow and sparsest cut problem due to work of Leighton and Rao by describing algorithm using a Linear programming relaxation and a geometric embedding. Then we present the work of Arora, Rao and Vazirani (ARV) and their algorithm based on Semidefinite programming relaxation and a geometric embedding. We also explain the concept of expander flows first introduced in the work of ARV. One section of our work is devoted to the spectral graph theory, introducing the concepts of the spectral gap, random walks, conductance and relations between them. We connect the ideas of expander flows and spectral theory in chapter about so called Cut-Matching game framework. Finally we present the performance results of our implementation of the Leighton-Rao and the Cut-Matching game algorithms. Powered by TCPDF (www.tcpdf.org)

La réaction de serpentinisation résulte de l’interaction de l’eau de mer, ou de fluides hydrothermaux avec les roches mantelliques. Elle engendre des changements des propriétés chimiques de la lithosphère océanique, avec notamment un enrichissement en éléments mobiles (ex. As, Sb, Li, Cs, Pb, et B). Ces éléments sont importants en sciences de la terre car ce sont des traceurs géochimiques des interactions fluides-roches depuis la ride océanique jusqu’aux zones de subduction. Ce travail de thèse a pour but de caractériser le partitionnement de certains éléments mobiles entre un fluide et la serpentine de manière expérimentale. Pour cela, j’ai développé deux protocoles expérimentaux en condition alcaline. Le premier, consiste en la synthèse de chrysotile à partir d’un gel à la stoechiométrie de la serpentine, à 300 °C et Psat. Pour le second protocole, la serpentine est obtenue par altération de grains d’olivine San Carlos (granulométrie : <30 µm, 30-56 µm, >56 µm) à 200 °C (Psat) pour 1M de NaOH et en présence de carbonate (HCO3-). La minéralogie des produits expérimentaux ainsi que leurs abondances ont été déterminées par diffraction des rayons-X, spectroscopie infrarouge et analyse thermogravimétrique. Les propriétés texturales ont été caractérisées par microscopie électronique à balayage et à transmission haute résolution. La composition du produit solide a été mesurée par spectrométrie de masse et analyse par microsonde-électronique et l’état d’oxydo-réduction du fer a été déterminé par analyses Mössbauer. Des analyses d’absorption des rayons-X (XAS) ont été effectuées afin d’analyser la structure locale de l’antimoine et de l’arsenic. La combinaison de ces techniques analytiques a permis de montrer que la synthèse de chrysotile est effective après seulement 8 heures de réaction. A 200°C, l’olivine est remplacée (pseudomorphose) par le chrysotile et la brucite. Le remplacement est total après 1 mois (<30 µm) et 3 mois (30 et 56 µm). En présence de carbonate, l’altération de l’olivine est caractérisée par une cinétique plus lente et est contrôlée par la précipitation de la magnésite et de la lizardite.En reprenant les 2 protocoles expérimentaux de synthèse de chrysotile (1M NaOH), et en dopant le fluide en un élément trace (Li, As, Cs, Sb et B) le partitionnement des éléments mobiles a pu être étudié. Le coefficient de partage solide-fluide (KD) a pu être défini pour chaque élément durant la synthèse du chrysotile à 300 °C en modélisant nos résultats suivant l’équation de Langmuir (concentrations en solution de 5 à 1000 µg g-1). La séquence obtenue pour les coefficients de partage est la suivante : 0.5<B < As < Li < Cs < Sb<9. En présence de lithium, d’arsenic et d’antimoine, la morphologie du chrysotile atteste d’une croissance radiale. En revanche, le bore favorise une croissance en longueur du chrysotile perpendiculaire à l’axe c. Un mécanisme d’adsorption contrôle principalement la séquestration des éléments mobiles par le chrysotile comme l’indiquent les résultats d’absorption des rayons-X sur l’arsenic et l’antimoine. Lors de l’altération des olivines, la séquestration des éléments trace est hétérogène et le changement des conditions d’oxydo-réduction du système durant la réaction de serpentinisation explique les changements dans la séquestration de l’antimoine d’abord adsorbé sous sa forme pentavalente puis incorporé sous sa forme trivalente par des phases secondaires. Même en faible concentration en solution (200 µg g-1), le lithium a un fort pouvoir catalytique sur la réaction de serpentinisation de l’olivine à 200 °C.En perspective plusieurs expériences haute pression et température (450 °C et 1-4 kbar) ont été réalisées afin de mieux comprendre le comportement des éléments traces durant les transitions de phase et la déstabilisation de la serpentine en contexte de subduction. Les résultats préliminaires indiquent que la présence de ces éléments traces a un rôle très important sur la stabilité du chrysotile. / Serpentinization reaction is the result of the interaction of seawater with mantle rocks especially at slow-spreading ridges. The formation of serpentinite during this alteration reaction changes the physico-chemical properties of the oceanic lithosphere and induces an enrichment in Fluid-mobile elements (FME: e.g. As, Sb, Li, Cs, Pb and B) compared to primary minerals. These elements are efficient geochemical tracers reflecting mantle hydration from the oceanic ridge to subduction environments. In this context, there is a lack of data concerning the partitioning and sequestration processes of FME between serpentine and fluids. The aim of this thesis is to determine fluid/serpentine partition coefficients of these elements as well as their effects on serpentine formation (reaction mechanism and kinetics, textural properties etc.). To achieve this goal, serpentine has been synthesized under highly alkaline hydrothermal conditions using two distinct protocols. Experimental-products were characterized using X-ray powder diffraction (XRPD), Fourier Transform Infra-Red spectroscopy (FTIR), N2 sorption isotherms, ThermoGravimetric Analyses (TGA), Field Emission gun Scanning Electron Microscopy (FESEM), High Resolution Transmission Electron Microscopy (HRTEM), X-ray Absorption Spectroscopy (XAS) and Mössbauer Spectroscopy. The first protocol consists in chrysotile synthesis from H2SiO3 and MgCl2 at 300 °C using batch and semi-continuous experiments. With this approach, we were able to chrarcterized chrysotile nanotubes nucleation and growth processes. In the second protocol, we investigated olivine serpentinization reaction under high hydroxyl-alkalinity or high carbonate-alkalinity at 200 °C. We note the efficiency of serpentine formation under high alkaline conditions in the both protocols and the significant effect of the carbonate component on the serpentinization processes and crystal growth rates. The serpentinization of olivine under alkaline conditions induces the oxidation of a large part of iron trapped by brucite.Replacement is total after 1 month (<30 µm) and 3 month (30-56 µm). The presence of a carbonate component induces a lower reaction kinetic and is characterized by the co-precipitation of magnesite and lizardite.Based on these results, we chose favorable conditions in order to study FME (Li, As, Cs, Sb and B) sequestration. Solid-liquid partitioning for each FME was investigated during chrysotile synthesis at 300°C. Experimental results were modeled using the Langmuir equation and the role of each element on chrysotile textural properties was investigated. In addition, we report new results concerning the sequestration and the distribution of the trace elements during olivine replacement by serpentine and brucite. We highlight that Li act as a catalyst during olivine serpentinisation. Moreover, from XAS measurements, we indicate that Sb and As sequestration is dominated by adsorption mechanism. The precipitation of secondary As- and Sb-bearing phases was also revealed by Electron Microprobe X-ray mapping. Finally, Sb-trapping within chrysotile tubes was also suspected by HRTEM measurements. The changes of redox conditions during serpentinisation induce a change of Sb sequestration mechanism and the precipitation of Sb-bearing phases. In addition, we investigate the partitioning of FME at higher pressure (1-4 kbar) and temperature (450 °C). This pilot study brings promising results regarding the behavior of trace elements during serpentine destabilization (deep lithosphere or subduction contexts) and on the non-negligible role of trace elements on the stability of chrysotile.

Recursive partitioning algorithms separate a feature space into a set of disjoint rectangles. Then, usually, a constant in every partition is fitted. While this is a simple and intuitive approach, it may still lack interpretability as to how a specific relationship between dependent and independent variables may look. Or it may be that a certain model is assumed or of interest and there is a number of candidate variables that may non-linearily give rise to different model parameter values. We present an approach that combines generalized linear models with recursive partitioning that offers enhanced interpretability of classical trees as well as providing an explorative way to assess a candidate variable's influence on a parametric model. This method conducts recursive partitioning of a the generalized linear model by (1) fitting the model to the data set, (2) testing for parameter instability over a set of partitioning variables, (3) splitting the data set with respect to the variable associated with the highest instability. The outcome is a tree where each terminal node is associated with a generalized linear model. We will show the methods versatility and suitability to gain additional insight into the relationship of dependent and independent variables by two examples, modelling voting behaviour and a failure model for debt amortization. / Series: Research Report Series / Department of Statistics and Mathematics

The need for a robust system architecture to support software development is well known. In enterprise software development, this must be realized in a multi-tier environment for deployment to a software framework. Many popular integrated development environment (IDE) tools for component-based frameworks push multi-tier partitioning by assisting developers with convenient code generation tools and software deployment tools which package the code. However, if components are not packaged wisely, modifying and adding components becomes difficult and expensive. To help manage change, vertical partitioning can be applied to compartmentalize components according to function and role, resulting in a grid partitioning. This thesis is to advocate a design methodology that enforces vertical partitioning on top of the horizontal multitier partitioning, and to provide guidelines that document the grid partitioning realization in enterprise software development processes as applied in the J2EE framework.

A research report submitted to the Faculty of Science, University of Witwatersrand, in partial fulfilment of the requirements for the degree of Master of Science (Resource Conservation Biology). Johannesburg, 2015 / The vegetation of the Kgaswane Mountain Reserve, in North West Province, South Africa, was mapped according to seven vegetation structure types, based on tree density and height, and grass height. Free-living ticks were collected by drag-sampling the vegetation from each structure type in November 2014, prior to the onset of the summer rains, and February 2015, once most of the seasonal rains had fallen. Eland (Taurotragus oryx) location information was recorded from four GPS collared cows over the two sample periods. Tick abundance was consistently lower in shorter, open, more exposed vegetation structure types, and higher in more sheltered types. Position higher up in the landscape nullified the positive impacts of trees on beneath-canopy microclimate in tall open woodlands, as indicated by comparatively lower tick numbers than in more sheltered woodland types. Tick abundance is influenced by vegetation structure and the availability of hosts. The majority of ticks trapped during both periods were larvae, with nymphs mostly present in November and adults mostly present later in the season, indicating the seasonal nature of tick cohort recruitment. Eland calving behaviour centred on areas with low adult tick abundance. Eland did not respond to total tick abundance during either sampling period. They did select areas with low adult tick abundance, and avoided areas with high adult tick abundance. This corresponded with an improvement in upland forage quality, which allowed them to avoid foraging in areas with high adult tick abundance. It is plausible that the potential for infestation by adult ticks may be a supplementary influence driving the use of space by eland.

How so many species coexist while utilizing the same resources is both of ecological interest and important for the management of wildlife communities and parks. This thesis endeavours to understand how grazing herbivores co-exist, with special emphasis on understanding the mechanisms of competition and facilitation over temporal and spatial scales. I compared the dry season use of grasslands, grass species, grass height and grass greenness by white rhino and three other ungulate species, zebra, wildebeest, and impala. I was specifically interested in the extent to which white rhinos, with their capacity to graze both short and tall grass, either competed with or facilitated other grazers. In Chapter Two, I clarify the mechanisms of facilitation and competition in terms of temporal and spatial scales, and discuss why there is little evidence in the literature to support these mechanisms. I conclude that evidence for facilitation through stimulation of grass re-growth during the growing season appears stronger than that for increased resource access through removal of obstructing grass structures during the dormant season. Facilitation may benefit the nutritional gains obtained by certain species in the short term, but these benefits do not appear to be translated into the expected population consequences. In collaboration with co-author Norman Owen-Smith, we suggested this could be due to seasonal tradeoffs between facilitation and competition, as well as to restrictions on the spatial extent of trophic overlap. In Chapter 3 Norman Owen-Smith and I compared the grass height use in relation to body size. We expected that the grass height favoured would increase with the body size of the herbivore species, as suggested from past studies of resource partitioning among large mammalian herbivores. Instead we found that the largest of these species, white rhino, concentrated on the shortest grass, while the smallest species, impala, favoured grass heights intermediate between those grazed by wildebeest and zebra. Results suggest that the scaling of mouth width relative to body size, and hence metabolic demands, is the primary factor governing grass height selection, rather than body size alone. Hence grazing successions governed by body size differences may not be a typical feature of their ecology, contrary to past suggestions. Furthermore, there was considerable overlap in grass height grazed among these four species, indicating that niche separation by grass height is inadequate alone to explain their coexistence. More attention needs to be paid to other aspects such as the grass species selected and habitat structure favoured. Chapter Four compared the overlap in grassland use and grass species use, as well as grass height and grass greenness of swards utilized by the herbivores as the dry season advances. I show that all species prefer grazing lawns during times of abundance, and that zebra leave grazing lawns before other species, and wildebeest leave grazing lawns before white rhino and impala. This suggests zebra and wildebeest may be competitively excluded from grazing lawns through a reduction in grass height, by white rhino and impala, during the dry season. However, white rhino are also potentially the ‘supreme’ facilitator increasing the availability of nutritious grazing lawns, as well as increasing the quality of those lawns through grazing in the wet season. A better understanding of the trade-off between “habitat facilitation” and competitive exclusion by white rhino, allows us to better understand how grazing herbivores co-exist.