2005 PhD Scholars

Abigail DurrantAbigail Durrant
University of Surrey, United Kingdom

Supervisor: Prof. David Frohlich
Microsoft Research supervisor: Dr. Abigail Sellen

Research title: Designing photographic experiences to support autobiographical memory

Research summary: Surprisingly little is known about the role of photographs in remembering life events. This project will examine this issue in relation to current theory in photography and memory, and use the findings to design new ways of capturing and consuming photographs.

Alessandro DuminucoAlessandro Duminuco
Institut Eurécom, France

Supervisor: Prof. Ernst Biersack
Microsoft Research supervisor: Pablo Rodriguez Rodriguez

Research title: A peer-to-peer based file backup system

Research summary: Peer-to-Peer systems have the interesting property of self-scaling, which means that the amount of resources grows with the number of participants. While there exist already a large number P2P systems for file sharing, very little work has been done in the area of using P2P systems for file backup. Typically, file back-up is done in a purely centralized manner. Such an organization requires a large amount of resources (disks, tape robot) and also some human intervention. On the other hand there is an increasing number of PCs each equipped with a local disk with a capacity of tens of Giga Bytes. The goal of the thesis is to investigate how the local disks of a large number of PCs can be organized in such a manner as to allow a highly reliable file back-up system. The thesis will first study existing approaches for distributed file backup and then design and implement its own backup system. It is envisioned to distribute each file that is backed up over multiple machines and to use error correcting codes for loss recovery. In order to evaluate the different design choices, a system model (machine availability, etc) needs to be defined and a performance evaluation will be carried out.

Alexander SpenglerAlexander Spengler
Université Pierre et Marie Curie (Paris 6), France

Supervisor: Prof. Patrick Gallinari
Co-supervisor: Prof. Bernhard Schölkopf, Max Planck Institute for Biological Cybernetics

Research title: Machine learning with structured data. Application to XML document transformation

Research summary: Many domains and applications are concerned with complex data composed of elementary components which are linked according to some structural or logical organisation. In the text domain, for instance, the diffusion of structured data formats like XML and HTML has considerably changed the fields of information retrieval and information extraction. Other application domains concerned with structured data include biology, image processing, multimedia (video), natural language processing, social networks and many more. The aim of this thesis is to investigate the potential of different families of statistical learning methods for handling structured data and to derive and analyse new methods for different data mining tasks (including generic tasks like classification and clustering of structured data as well as problems where transformations between structured representations need to be learned). The primary field of application for the experiments will be that of semi-structured documents (XML textual documents for example). Semi-structured documents are defined by both their content and their logical structure. In order to effectively mine these documents either type of information needs to be incorporated. Compared to other domains in which the data is made up of only one of the two types, this is a much more complex task.

Andrew WeeksAndrew Weeks
University of York, United Kingdom

Supervisor: Prof. Susan Stepney

Research title: Artificial chemical reaction networks for meta-heuristic search

Research summary: The research aim is to develop an artificial chemical reaction network framework that can be used as a robust constructive computational search meta-heuristic, and apply it to complicated constructive search problems, such as proof discovery. The strategy is to investigate the relationship between complex chemical reaction pathways and meta-heuristic search, in particular (i) the role of auto-catalytic networks and hyper-cycles in amplifying good solutions, and self organising the search process; (ii) the workings of catalysis, to develop endogenous ‘embodied’ techniques for searching for complex artefact construction pathways; (iii) the role of equilibrium and non-equilibrium chemical processes in the construction approach, in particular, computational analogues of the appropriate free energy and enthalpy concepts; (iv) the ‘back reaction’ concept, as an indirect way of discovering and constructing novel ‘reactants’.

Andy MauleAndy Maule
University College London, United Kingdom

Supervisor: Prof. Wolfgang Emmerich

Research title: Impact analysis of relations database schema changes on dynamically composed queries

Research summary: When database schemas require change, it is typical to predict the effects of the change, first to gauge if the change is worth the expense, and second, to determine what must be reconciled once the change has taken place. Current techniques to predict the effects of schema changes upon applications that use the database can be expensive and error-prone, making the change process expensive and difficult. Our thesis is that an automated approach for predicting these effects, known as an impact analysis, can create a more informed schema change process, allowing stakeholders to obtain beneficial information, at lower costs than currently used industrial practice. This is an interesting research problem because modern data-access practices make it difficult to create an automated analysis that can identify the dependencies between applications and the database schema. This project will develop a novel analysis that overcomes these difficulties.

Aziem ChawdharyAziem Chawdhary
Queen Mary University of London, United Kingdom

Supervisor: Prof. Peter O’Hearn
Microsoft Research supervisor: Dr. Byron Cook

Research title: Automatic program analysis and verification with separation logic

Research summary: There have recently been major advances in the mechanical verification of software, perhaps most strikingly exemplified by Microsoft’s SLAM model checker. However, current software model checkers have only rudimentary treatments of heap-intensive properties and of concurrency. Separation logic is a recent theoretical development which provides a fresh approach to reasoning about the heap and about concurrency. The purpose of this project is to investigate uses of separation logic in automatic verification. The current plan is to start, not from a generalist position, but by building a tool oriented to specific code targets.

Brendan SheehanBrendan Sheehan
University College Dublin, Ireland

Supervisor: Dr. Aaron Quigley
Co-supervisor: Prof. Paddy Nixon

Research title: Model driven visualisation of large scale relational networks

Embark InitiativeResearch summary: The visualisation of relational data has thus far been largely concerned with handling small to medium size collections of data. In the case of large scale relational networks the convention of using nodes and edges is no longer practical. The simple reason for this is that the resolution of the screen provides a restriction on how many items of data can be displayed simultaneously. While techniques can be developed to provide visualisations of such networks for the purposes of exposition of some known relationship or where the frame provided by a well defined question simplifies the visualisation problem, the question of visualisation for purely exploratory purposes remains. Using optimisation techniques to specify constraints on how the underlying data is visualised, tools will be developed to allow the user to arbitrarily introduce and retract parameters so as to impose hypothetical models on the visualisation to reveal unanticipated structure in the data. Initial research will look into how various graph abstraction techniques handle multidimensional data. Particular emphasis is given to geometric methods. For example how quadtree or Voronoi partitioning of the underlying data space deals with various clustering schemes such as Principal Component Analysis (PCA), Multidimensional Scaling (MDS) and non-linear clustering methods such as Kohonen networks will be analysed.

Brian AmbergBrian Amberg
Universität Basel, Switzerland

Supervisor: Prof. Thomas Vetter
Microsoft Research supervisor: Prof. Andrew Blake

Research title: Real time editing of face expressions in video streams

Research summary: The aim of this PhD project is the extraction and manipulation of facial expressions in video streams. To achieve this, an expression model of the subject in the video stream will be built. This model is fitted to the stream in order to extract expression, pose and lightning conditions. The model will be able to synthesise new expressions from the parameter set. This allows to render a modified face back into the video stream, enabling applications like expression change, exaggeration, or diminution. To achieve this aim several obstacles from different fields have to be overcome. 1) An expression model is needed that separates identity from expression. 2) Real time fitting of the model to the video stream can only be achieved by combining a multitude of methods on different scales of the problem. Efficient tracking of the ROI can reduce the search space by focusing on parts of each frame. Time and space coherence in a video sequence must be exploited to achieve a speedup against single frame operations. A probabilistic model of facial deformations must be learned to predict the parameter set for future frames. 3) Rendering the modified face seamlessly into a video stream requires the removal of the existing face and in painting of background regions that were occluded in the original image. Additionally techniques for the smoothing of cut-out edges are needed to remove artifacts.

Damian Serrano-GarciaDamian Serrano-Garcia
Universidad Politecnica de Madrid, Spain

Supervisor: Prof. Marta Patiño-Martínez

Research title: High performance database replication for storage area networks

Research summary: New developments in database replication protocols and new architectures such as system and storage area networks (SANs) have changed dramatically the limits of the scalability for eager database replication. In this project Damien will build upon these developments to produce a highly scalable replicated database. SANs will be exploited to attain low overhead replica coordination. New correctness criteria such as 1-copy snapshot isolation will be exploited to enhance scalability by removing read-write conflicts. Finally, autonomic reconfiguration and optimisation will be exploited to maximise performance.

Dan DobreDan Dobre
Technische Universität Darmstadt, Germany

Supervisor: Prof. Neeraj Suri

Research title: Group communication protocols & replication for Web services

Research summary: The project focus is on exploiting different properties of message exchange patterns at the communication/application level to derive fault-tolerant atomic broadcast protocols facilitating fast message delivery. Currently, Dan is investigating the combined application of distinct oracles (for example, a leader and a weak atomic broadcast oracle) to achieve a better coverage with respect to liveness and/or to expedite message delivery. An interesting issue is to what extent such ‘hybrid’ protocols meet the lower bound on delivery latency in the normal case. Eventually the protocols will be migrated from the static/crash model to dynamic/byzantine models.

Daniele QuerciaDaniele Quercia
University College London, United Kingdom

Supervisor: Dr. Stephen Hailes
Co-supervisor: Licia Capra

Research title: Distributed trust models for pervasive computing

Research summary: Pervasive computing environments must be able to provide resources and services without relying on a centralised infrastructure. This would not be possible in the absence of appropriate security mechanisms. Fundamental to the creation of security are mechanisms for assigning trust to different devices: without trust, devices cannot collaborate effectively, and without collaboration, the pervasive computing vision cannot be made a reality. Given the importance of this area, researchers have been designing distributed trust models for some time. However, the focus of such work has usually been on the creation of very general trust-based frameworks that are sufficiently imprecise that they are both difficult to apply and almost impossible to falsify in real-life scenarios. In contrast, the proposed research takes a more rigorously scientific approach. It is comprised of the following steps: (i) select a set of concrete real-life scenarios that both make use of pervasive devices and benefit from a computational trust framework; (ii) deduce and formalise the trust challenges posed by each scenario (iii) design computational models that address those trust challenges (iv) evaluate these models both qualitatively and quantitatively against criteria drawn from the initial domain-specific investigation.

David StynesDavid Stynes
University College Cork, Ireland

Supervisor: Dr. Ken Brown
Microsoft Research supervisor: Dr. Youssef Hamadi

Research title: Adversarial constraint solving

Embark InitiativeResearch summary: The aim of the research is the combination of constraint satisfaction techniques with artificial intelligence game playing and/or mathematical game theory techniques to tackle combinatorial problems in which two or more self-motivated agents with different goals must produce a joint solution.

Fabien CorblinFabien Corblin
Université Joseph Fourier, France

Supervisor: Prof. Laurent Trilling
Co-supervisor: Dr. Éric Fanchon, CEA-CNRS
Microsoft Research supervisor: Dr. Youssef Hamadi

Research title: Modelling, inference and simulation of biological networks using constraint logic programming (CLP)

Research summary: Computer tools are needed in systems biology to analyse qualitatively the dynamics of interaction networks, to discover the organisation of the cell’s molecular component. In this context, Fabien’s objective is to develop a general tool based on a unique specification allowing the exploration of the model’s parameters’ and behaviours’ properties, by a mix of inference and simulation. This work is based on the multi-valued asynchronous networks proposed by R. Thomas and E. Snoussi (1989, 1993). This formalism, which can be seen as a discrete abstraction of a special class of piecewise affine differential equations, allows a qualitative analysis of the dynamic behaviour of such systems. This formalism has been recently extended by de Jong et al. (2004) to take into account trajectories which are confined in the neighbourhood of discretisation thresholds (‘sliding modes’). The goal of this research is to investigate how a formal description of such a biological switching network can be exploited through an implementation in CLP (Constraint Logic Programming) in order to obtain the variety of functionalities desired. This tool will be applied to the construction of several biological networks.

Florian SchroffFlorian Schroff
University of Oxford, United Kingdom

Supervisor: Andrew Zisserman
Microsoft Research Supervisor: Antonio Criminisi

Research title: Multi-Class Image Interrogator

Research summary: The first part of this project focused on object recognition itself, more specifically segmentation in the sense of assigning a class-label to each pixel in the image. The second part of the project focuses on "Harvesting Image Databases from the Web". The goal is to retrieve large numbers of images form the web for a specified object class. The user only has to specify the object-class and no further user interaction is required. This work returns images for a specified object class with higher precision than common image search engines. Further focus lies in multi-class object recognition employing hierarchical models. In order to be scalable to many object classes it seems to be very important to share features between object classes. This idea will be investigated together with the related idea of using hierarchical models. Hierarchical models could provide a generic mean to share more complicated high level features. Which kind of hierarchy is useful in the object recognition domain, e.g. hierarchies of object classes, parts that assemble an object class, or just abstract features, will be analysed.

Georg WeissenbacherGeorg Weissenbacher
University of Oxford

Supervisor: Prof. Daniel Kröning
Microsoft Research supervisor: Prof. Sir Tony Hoare

Research title: Formal verification techniques for code optimisation

Research summary: Recent efforts like Tony Hoare’s Verifying Compiler Grand Challenge suggest that there is a consensus in the formal verification community that compilers and formal verification tools will eventually coalesce. In compilers, code optimisation is often based on relatively imprecise (conservative) results of light-weight analysis algorithms, while formal verification tools typically perform less efficient but significantly more accurate analyses. Georg will investigate how the detailed information that is gained by using formal verification techniques can be used to increase efficiency as well as quality of the code generated by compilers

Giorgio GianformeGiorgio Gianforme
Università Roma Tre, Italy

Supervisor: Prof. Paolo Atzeni

Research title: Schema and data mapping and transformation: foundations and application

Research summary: Many application settings involve the need to exchange information between heterogeneous frameworks. In the database world, different systems are often used to handle data, following different models, and therefore data and their description need to be translated from one to another. Model Management is a high level-approach to solving such meta data problems. A major operator in model management is ModelGen, which translates schemas from a source to a target model. Given a source data model M1 (e.g., the ER model), a target data model M2 (e.g., SQL DDL or XML Schema), and a source schema S1 expressed in M1, ModelGen generates a target schema S2 in M2. The current results in the ModelGen project of the database group of ‘Università Roma Tre’ can be the basis for various research challenges. Giorgio’s research will consider three main directions: First, there is the need for a formal support to the validity of the approach (correctness and completeness); second, the customisation of the translations has to be studied, both at the schema and at the instance level; third, it will be important to study the validity and the adaptation of the approach to specific application domains, in cross-disciplinary settings.

Kai KohlhoffKai Kohlhoff
University of Cambridge, United Kingdom

Supervisor: Dr. Michele Vendruscolo
Co-supervisor: Prof. Martin Zacharias, International University Bremen

Research title: Experimental and computational studies of free energy landscapes for protein aggregation

Research summary: Deposits of misfolded proteins in cells or in intracellular space play a significant role in a number of severe medical disorders, such as Alzheimer’s and Parkinson’s. The underlying phenomena that cause misfolding and the formation of protein aggregates and amyloid fibrils are not yet well understood. Using data from NMR and X-ray crystallography techniques, Kai is interested in combining experimental measurements with computational methods to improve speed and detail of protein folding simulations. Identifying and applying new constraints to the conformational space of a protein will help finding the correct folding pathway on a protein’s free energy surface.

Konrad KielingKonrad Kieling
Imperial College London, United Kingdom

Supervisor: Dr. Jens S. Eisert
Co-supervisor: Dr. Martin Plenio

Research title: Linear optical quantum computing: novel architectures and computational assessment of performance

Research summary: Among the different proposals for realization of quantum computation hardware, linear optical schemes are attractive due to simplicity of the required resources and only little decoherence. Unfortunately, non-unit success probabilities of the elementary gates are inherent in this scheme. In this project the potentials and limits of the linear optics toolbox will be investigated in the context of resource preparation for one-way computation. Further, general properties of the gates that can be built with these ingredients will be studied. With less restrictive rules the problems of the scheme being probabilistic may be overcome. Therefore, possible extensions will be discussed, e.g. atoms that are coupled to the light field by means of cavities.

Loïc FejozLoïc Fejoz
INRIA Lorraine (LORIA), France

Supervisor: Dr. Stephan Merz
Microsoft Research supervisor: Dr. Tim Harris

Research title: Provably correct lock-free data structures

Research summary: The aim of this thesis is to design a method for the development and verification of algorithms working on lock-free data structures. The idea will be to start with a formal behavioural specification of the data structure in a sequential setting and derive an implementation that can be used in concurrent applications via a series of refinement steps. These implementations are intended to be more efficient for modern hardware and software than traditional algorithms relying on central locks to protect concurrent modifications.

Michael KaisserMichael Kaisser
University of Edinburgh, United Kingdom

Supervisor: Prof. Bonnie Webber

Research title: Enlisting syntactic and semantic resources for web-based question answering and fact extraction

Research summary: Michael Kaisser’s research challenge is the possibility of more direct Natural Language access to the vast sea of information expressed in Natural Language on the Web. Specifically, he is investigating how to search the Web for facts. He wants to develop a coherent linguistic approach to this task by exploiting (wherever possible) freely available linguistic tools and resources. His research area overlaps with what is usually called ‘Question Answering’. While common search engines are keyword-based, a Web search that starts with a question is much more specific and provides more information that can be used when searching for relevant answers or Web sites that contain these answers: Understanding a question syntactically and semantically can help to understand which results are relevant to a user’s search and which are not.

Philippe-Alexandre PouillePhilippe-Alexandre Pouille
Institut Curie, France

Supervisor: Dr. Emmanuel Farge

Research title: In silico model for self-organised embryogenesis mechano-genetics interplay

Research summary: The genetic control of embryonic morphogenetic movements at gastrulation is better and better described in developmental biology, especially in the early drosophila embryo. However, the relationship between genetically controlled active single cells shape changes and migration, and the consecutive generation of the multi-cellular ‘macroscopic’ embryonic phenotype remains to be quantitatively investigated. As well as the precise biomechanics leading to feedback mechanical induction of developmental gene expression modulation in response to these morphogenetic movements. The research project consists in generating a biomechanical in silico viscoelastic multi-cellular model of the embryonic active and reactive tissues, to study such self-organised embryogenesis mechano-genetic interplay participating to embryonic mechanical morphing and development.

Stewart HickeyStewart Hickey
University of Limerick, Ireland

Supervisor: Dr. Colin Fitzpatrick

Research title: Technologies for sustainable ICT

Embark InitiativeResearch summary: When evaluating the environmental performance of electronic products it is very important to consider all aspects of their life cycle. This ensures that any action to improve the performance contributes to the overall reduction in environmental impact and avoids the transfer of burdens from one life cycle phase to another. Most often with electronic products it is the Use Phase of the life cycle that is most environmentally damaging. This project will examine the life cycle of PC’s with an emphasis on the use phase. More specifically it will focus on the use of networks and software in reducing environmental impacts in a market friendly fashion.

Tony O'DonovanTony O'Donovan
University College Cork, Ireland

Supervisor: Prof. Cormac Sreenan
Research title: Research in wireless sensor networks

Embark InitiativeResearch summary: Wireless sensor networks are collections of autonomous devices (nodes) with computational, sensing and wireless communication capabilities. Tony's research will focus on the use of wireless sensor networks in the area of medical informatics. Most wireless sensor network research involves networks of hundreds or thousands of nodes and the difficulties entailed with networks of this scale. This project on the other hand, will be concerned with the issue of coordinating a small number of sensors to detect medical emergencies in a low latency manner, possibly coupled with actuators to mitigate the effects of the emergency condition. The main challenge will be achieving close to 100 percent reliable communication and ensuring the system is robust enough for use as a medical device.