Computer Science at the University of Bristol (UoB) is an international centre of excellence in the theory and application of computing. The subject of Computer Science (CS) is currently revolutionising a wide range of human activities, including the life sciences. It is also itself undergoing revolutionary change, with the introduction of new algorithmic techniques in areas as diverse as graphics, cryptography and quantum computation. Our mission is to anticipate and drive these developments in the areas in which we have world-class expertise.
Since RAE 2001, UoB Computer Science has truly flourished. The number of category A staff has grown with nearly 30%, from 29 to 37. We have expanded in areas where we already had strong expertise, such as machine learning, image processing and quantum computation. We have ventured into new, promising areas such as personal systems and biologically-inspired computing. In nurturing our growth, we have struck a balance between retaining experienced staff returned in the previous RAE (18) and appointing new staff of exceptional promise (19, including 16 early-career researchers).
Here we summarise the main developments since the last RAE.
v A doubling of our research capacity in intelligent systems, with focus on data mining, biological and biologically-inspired computing, and Exabyte Informatics (a University-wide research theme on curating and mining large amounts of data). This includes setting up a new Pattern Analysis group led by Nello Cristianini and the creation of the IRC in Large-Scale Complex IT Systems (LSCITS, www.lscits.org), supported by £5.6m from EPSRC and run from Bristol by David Cliff.
v Sustained collaboration with world-class digital media industry through the 3CR partnership (www.3cresearch.co.uk). This University Innovation Centre initially funded by the DTI has led to a range of cutting-edge research. The Intelligent Content-Based Retrieval project has made available a large volume of searchable, semantically marked wildlife film footage. The Motion Ripper project has produced sophisticated animation tools and has led to two major animations. One of these, a computer-generated piece of “wildlife footage”, was screened by the BBC.
v A significant strengthening of the Maths/CS interface. This includes expansion in classical and quantum algorithms, a strengthening of the links between the data mining group and Bristol’s statistics group, and further investment in cryptography and information security. New collaborations are being fostered by the recently funded Bristol Centre for Complexity Science (bccs.bris.ac.uk), a Doctoral Training Centre funded by a £4m EPSRC grant, and by an EPSRC-funded Bridging the Gaps project (bridgingthegaps.bristol.ac.uk).
v Considerable investment in the area of robotics, resulting in the formation of the Bristol Robotics Laboratory (BRL, www.brl.ac.uk), a joint research facility between UoB and the University of the West of England (UWE). It is led by Chris Melhuish, who holds a joint appointment between UoB (20%) and UWE.
Bristol’s research within Computer Science can be grouped in five core research activities, each consisting of smaller, more focused research groups. There are many cross-linkages between research interests of staff, hence it is common for staff members to be included in more than one group. This allows our research to be more dynamic, thus enabling us to respond to a changing research landscape with greater agility.
These five core activities are as follows:
v Intelligent Systems is concerned with general principles underlying learning and intelligence in computational and biological systems. Research areas include machine learning and data mining, biologically-inspired computing, bioinformatics and applications to large-scale systems and data. This research benefits from strong links between the CS and Engineering Mathematics departments.
v Digital Media is concerned with the creation, capture, processing, compression and communication of video, images and sound. The main research areas are computer vision and image processing, graphics and animation. We particularly focus on applications in medicine, biology and film production.
v Foundations investigates theoretical and practical issues in algorithms, complexity, cryptography and quantum computation. This ranges from theoretical work in the understanding of the nature of quantum information processing to applied work in cryptography which has had an impact on deployed systems and industrial standards.
v Personal Systems involves the application of CS to activities around people and their interactions with computers and robots. Its research activities are concentrated in the following areas: personal robotics, wearable computing, pervasive computing and ubiquitous computing.
v Architecture and Design pursues research in computer architecture, design, verification and languages. It is particularly concerned with low power hardware design, design for verification and multiprocessors. In addition the group conducts research into hardware designs which are secure for use in security tokens.
2. Research Highlights
In this section we outline some of the main research achievements over the RAE period in each of the five core research activities.
[Notational conventions: Individual researchers are referred to by their last name in bold (with added initials in brackets in case of name clashes, so Campbell (ICG) refers to Colin Campbell and Campbell (N) refers to Neill Campbell). Early-career researchers are indicated with an asterisk*. At the start of each activity we list the contributing researchers with their position (P – Professor, R – Reader, SL – Senior Lecturer, L – Lecturer, RF – Research Fellow). New appointments since the last RAE are underlined in this list. References to papers in RA2 are denoted by [Flach-2] for the second paper by Flach.]
Rafal Bogacz* (SL), Colin Campbell (R), David Cliff (P), Nello Cristianini (P), Tijl De Bie* (L), Peter Flach (P), Julian Gough* (R), Steve Gregory (SL), Tim Kovacs (SL), Jonathan Lawry (R), James Marshall* (L), Trevor Martin (P), Oliver Ray* (RF), Jonathan Rossiter (SL)
Research in this area is concerned with general principles underlying learning and intelligence in computational and biological systems. Research activities cover the following areas: artificial intelligence, machine learning and data mining, large-scale systems, biological models and biologically-inspired computing. There are strong links with other departments, such as biological sciences, psychology and neuroscience, and with a large number of companies and other universities, especially via the recently set up LSCITS IRC.
Flach’s research has concentrated on extending traditional machine learning methods to deal with highly structured data. His contributions include the Tertius rule discovery algorithm, which has been included in the widely-used Weka machine learning toolbox and used by a major microprocessor manufacturer for “proof-of-principle” work. He has developed transformation methods that make machine learning problems involving structured data amenable to analysis using attribute-value representations [Flach-1]. He has upgraded Bayesian classifiers, Bayesian networks and kernel methods to model probability distributions over and geometric embeddings of complex objects represented as terms in higher-order logic. In addition he has generalised rule learning to subgroup discovery [Flach-3]. Finally, Flach has pioneered the use of ROC analysis to improve machine learning methods and algorithms [Flach-2,4].
Kovacs has developed a theory for Michigan-style genetics-based machine learning systems which includes classes of problems and algorithms and a mapping between them [Kovacs-2,3]. He has identified a variety of pathological credit assignment conditions in reinforcement learning systems with adaptive state aggregation and analysed the conditions under which they can occur. Kovacs has compiled the world’s largest bibliography of learning classifier systems literature, a much-used online resource.
Lawry has developed the label semantics framework as a formal random set approach to modelling the uncertainty associated with the use of vague/fuzzy description labels in rule-based systems [Lawry-2,3]. Within this framework he has developed rule induction methods, such as the LID3 algorithm, which learn probability estimation trees in which attributes are constrained by fuzzy labels. These methods have been applied across a range of applications, including classification of weather radar images, flood prediction and real-time path planning and obstacle avoidance.
In collaboration with British Telecom Research Labs, where he holds a senior research fellowship, Martin has developed soft computing methods for fusion, integration and mining of semi-structured information. This has led to 5 patents in the area of processing XML-enhanced symbolic and text-based data, and to the iPHI and SOFT software packages, which have been used in a number of prototypes within British Telecom [Martin-2,3]. It has been applied to the problem of personal content filtering and customisation and to user modelling, data mining and knowledge discovery in a home sensor network [Martin-1].
Cliff’s research has addressed the automated design and implementation of market-based systems, with particular emphasis on low-latency automated execution and on the adaptive self-equilibrating nature of auction market mechanisms [Cliff-1]. He developed new automated trading strategies and new mechanisms for automated design and fine-tuning of auction-market mechanisms, which are now widely used in the financial markets. Before re-entering academia in October 2005, he worked on these and related topics for major commercial organisations where the primary outputs were patents, or frequently trade secrets.
A considerable amount of work in the Intelligent Systems area is devoted to solving biological problems and exploring connections with biological systems. Here we outline some of our main achievements with a biological dimension.
Gough* has designed and developed the SUPERFAMILY web server for assigning protein domains of known structure to genome sequences using hidden Markov models [Gough-1,2]. This on-line system is widely used (over 100,000 hits in January 2007) and has had considerable impact on bioinformatics, structural and molecular biology. The project has enabled Gough to work on computational models of evolution, with novel results about the protein repertoire and domain combinations published in Science [Gough-3,4].
Bogacz* has developed mathematical theories describing two cognitive processes in the brain: decision making [Bogacz-3,4] and familiarity discrimination [Bogacz-1,2]. He proposed that during decision making between multiple alternatives the brain performs an optimal statistical test. He demonstrated that the computations required for this test map onto the anatomy of the key brain decision area, via a neural network, and thus provided the rationale for its organisation. He has established that neural networks can achieve much higher capacity for familiarity discrimination than other networks can achieve for recall.
Kovacs and Marshall* have established a Regional Network on Mathematics, Computation and Biology in 2004, involving the universities and research-active industries of Bristol and Bath in the area of Information Processing in Biological Systems. Marshall’s work with the Bristol Ant Lab has included game-theoretic and computational analysis of natural selection, and has resulted in the re-evaluation of long-standing theories. Modelling novel social insect behaviour, namely house-hunting in the ant Temnothorax albipennis, has led to the derivation of a new decentralised control algorithm, which exhibits the speed-accuracy trade-off demonstrated by the ants during collective decision making [Marshall-3].
Cristianini has focused on the statistical and algorithmic aspects of Pattern Analysis methods and their applications to computational genomics and computational linguistics. He is internationally very well-known for work on kernel-based algorithms which was summarised in two books co-authored with John Shawe-Taylor; the most recent of these, Kernel Methods for Pattern Analysis (2004), has sold over 3000 copies to date. He has generalized kernel-based algorithms to cover other classes of learning algorithms, all sharing the same focus on exact optimisation and strong statistical foundations [Cristianini-2]. Theoretical contributions include stability results for empirical moments of distributions, convex methods for kernel combinations [Cristianini-3] and algorithms for transduction. The applications involve models of gene family evolution, in particular for yeast and mammalian genomes [Cristianini-4], methods for genomic data fusion and models of language evolution.
De Bie* works on the exploitation of advanced (convex) optimisation techniques. His results include methods for data fusion mostly developed and applied in a bioinformatics context [De Bie-3,4], methods for modelling the evolution of gene family sizes [De Bie-1], and techniques to solve combinatorial optimisation problems such as graph cut problems and transduction [De Bie-2].
Campbell (ICG) has worked in algorithm design for kernel-based methods and probabilistic graphical models, especially in relation to cancer informatics [Campbell(ICG)-1,2,3]. In collaboration with the Institute of Cancer Research, London, his algorithms have successfully identified targets of therapeutic significance. Gene targets have been identified for knockdown using small interfering RNAs and these knockdowns have resulted in substantial loss of tumour cell viability for one subtype and inhibition of tumour cell proliferation for another cancer subtype.
Andrew Calway (SL), Neill Campbell (R), Kirsten Cater* (L), Colin Dalton (L), Mike Fraser (SL), David Gibson (RF), Walterio Mayol-Cuevas* (L), Majid Mirmehdi (R), Erik Reinhard (SL)
This resarch concerns the creation, capture, processing, compression and communication of video, images and sound. The activities are concentrated in computer vision, image processing, graphics and animation. Close links have developed with the extensive network of media production companies in the Bristol area and beyond (e.g., Turner Broadcasting) to conduct inter-disciplinary research in digital media technology and creative media content production. The group also works in areas related to our Personal Systems research.
Reinhard has developed dynamic range reduction algorithms in the field of high dynamic range imaging, which have helped the general acceptance of this emerging technology, following the work of Chalmers [Reinhard-2,4]. The algorithms developed by Reinhard are currently widely used in the film, games and photography industries. He developed the first computational model to glean the colour mood of one image and apply this to a different image. Cater, in the area of selective rendering, has investigated directing resources to ensure the highest quality image for the minimum computational cost [Cater-1, Dalton-1].
The Intelligent Content-Based Retrieval project, led by Campbell (N), has, in conjunction with Matrix Media Ltd and Granada Productions, made available hundreds of hours’ worth of high-resolution wildlife film footage alongside its semantic metadata [Gibson-1,2,3]. Coupled with technical meta-data extraction and a 75,000 term taxonomy it is one of the most important resources of its type in the world, allowing research into bridging the semantic gap for data retrieval and search applications. This work was initiated by Thomas, who sadly passed away during the period of the RAE, but has been continued by Campbell (N) and Gibson.
The Motion Ripper project, led by Campbell (N) and Dalton, has produced highly innovative tools for animators that increased productivity in “blocking-out” animations and synthesising crowd scenes. In addition to tools and research publications, this project led to two major animations. The first of these, “No Easy Way”, is a 2½ minute computer graphics short, nominated for a prize at Imagina 2005 – the industry’s leading trade awards event [Campbell(N)-1, Dalton-3]. The second was aired as part of the BBC Natural History Unit’s “Natural World” production “Ant Attack” in January 2006 and included several scenes of artificially created ants and their associated motions [Campbell(N)-2, Dalton-4].
Mirmehdi has helped create a diabetic retinopathy system facilitating the detection of exudate pathologies as well as precise measurement of the optic disc for monitoring disease over time. He has developed and validated an image-based speckle tracking methodology for determining temporal 2D axial and lateral displacement and strain fields from ultrasound video streams [Mirmehdi-3]. Algorithms for object segmentation via active contours were developed by Mirmehdi for random texture analysis and defect analysis on various surfaces [Mirmehdi-2,4]. The methods are applicable to a variety of images, particularly those from medical imaging and in the manufacturing industries.
Raphael Clifford* (L), Aram Harrow* (L), Richard Jozsa (P), Elisabeth Oswald* (L), Daniel Page* (L), Nigel Smart (P), Bogdan Warinschi* (L)
This research investigates, for both classical and quantum computing, theoretical and practical issues in algorithms, complexity and cryptography. The cryptography group specialises in implementation techniques, the underlying hard problems on which cryptography is based and the provable security of protocols. The group is a major partner in the eCrypt European Network of Excellence in cryptography. The quantum computing group is part of a large and internationally renowned University effort straddling the departments of Electronic Engineering, Mathematics, Computer Science and Physics. The work in CS is concerned with the theoretical underpinnings of this large research programme.
Smart’s work on asymmetric cryptanalysis has continued with the development of the technique of Weil descent as a means to attack elliptic curve cryptosystems [Smart-2]. He helped develop the first L(1/3) algorithm for finding discrete logarithms in medium characteristic fields, thus filling a long-standing gap in our understanding of the discrete logarithm problem [Smart-3]. With Page*, he has led work in the new area of pairing-based cryptography, developed new protocols and investigated a number of implementation issues [Page-4]. Smart is a co-inventor of the Ate-pairing algorithm, the most efficient pairing algorithm known [Smart-4]. This has resulted in an effort to standardize, via the IEEE, some of the protocols and techniques and the formation of a spin-out company called Identum.
Oswald*, Page* and Smart are well-known for their work in side-channel analysis, for both traditional [Oswald-2,3,4] and pairing-based systems [Page-3]. They have contributed a number of new attacks, such as cache-attacks, and developed a number of novel defences. Investigation has been carried out into non-traditional side-channel and fault attacks using features of memory sub-systems, virtual machines and processor pipelines. This work has led to a new direction of interest in this area, opening the way for a more diverse range of attack techniques.
Warinschi* developed the first security model for group signature schemes [Warinschi-1] and has contributed to the increasing body of work which aims to bridge the divide between the cryptographic model and the symbolic model for analysing security protocols [Warinschi-2,3]. The increasing importance of this work derives from the fact that protocols are now becoming hard to prove secure in the cryptographic model due to their increased complexity. The symbolic model, on the other hand, manages smoothly increasing complex systems, but it is not known whether it can model adversarial goals and powers accurately.
Clifford* has developed a series of algorithms which make advances in lowering the computational complexity of various problems. He has developed sub-quadratic time algorithms for string matching in numerical data under the L1 and L∞ norms [Clifford-3]. This is the first time this bound has been broken and the complexity achieved is conjectured to be tight. He has created distributed suffix trees with optimal parallel performance, allowing massive datasets to be handled on a distributed memory machine [Clifford-1].
Jozsa has produced a series of milestone results in the study of quantum information and its relation to classical information. He has provided a complete solution to the question of the trade-off between quantum and classical resources in the task of describing quantum sources, both in the case of the source being given as quantum states and in the case that the state identities are given classically [Jozsa-1]. He has established new monotonicity properties of the entropy function leading to a new geometrical understanding of quantum information compression [Jozsa-2] and has proved a connection between quantum computational speedup and the phenomenon of multipartite quantum entanglement [Jozsa-3]. He has proved a strengthened form of the no-cloning theorem, one of the fundamental cornerstones of quantum information theory, asserting that cloning, even with assistance, is impossible unless the assistance by itself contains the full information of the copy.
Harrow* has performed pioneering work in both quantum information theory and quantum algorithms. He introduced the idea of coherent classical communication to quantum information theory, which has led to the development of many new channel coding protocols [Harrow-1]. In quantum algorithms, he introduced the first efficient circuits for the quantum Schur transform, an important algorithmic building block analogous to the quantum Fourier transform. He has demonstrated the first super-polynomial quantum speedup that is based on a nonabelian Fourier transform [Harrow-3].
Andrew Calway (SL), Neill Campbell (R), Kirsten Cater* (L), Peter Flach (P), Mike Fraser (SL), David May (P), Walterio Mayol-Cuevas* (L), Chris Melhuish (P, 20%), Majid Mirmehdi (R), Henk Muller (R), Sriram Subramanian (L), Cliff Randell (RF)
This research involves the application of computer science to activities around people and their interactions with computers and robots. Its research activities are concentrated in personal robotics, wearable computing, pervasive computing and ubiquitous computing. A major highlight over the past years has been our work in the Equator IRC, in which the Computer Science Department was one of eight participating institutions.
The international final review of Equator concluded that “The IRC turned a high risk starting point into something not only excellent but fundamental and which has now become mainstream. The US are trying to catch up in this area where the UK is a leader and this is all credit to EQUATOR”. Our main contribution comprised wearable positioning technology based on ultrasonics and real-time visual simultaneous localisation and mapping (SLAM). This work was led by Muller and Randell.
Calway and Mayol-Cuevas* have made contributions to SLAM for single cameras [Calway-3, Calway-4]. This includes being the first to demonstrate successful real-time localisation using particle filtering, the development of robust visual matching algorithms with high levels of resilience to erratic camera movement and a coherent framework for high-level scene structure.
May and Muller have developed a range of wearables that have been used “in the wild” in experience projects involving children and museum visitors. These wearables include the CyberJacket, E-Sleeve and Magic jacket. We have carried out research into wearable context sensor configurations sensing position, activity and personal well-being. Muller has developed positioning systems based on ultrasonics, which opens the way for combining ultrasonic location sensing applications with the SLAM work mentioned previously [Muller-1,3,4].
May and Cater* have been leading the DTI-sponsored “Mobile Bristol” project, which was one of three projects short-listed for the “Computing Awards for Excellence 2004” organised by Computing Magazine in the “Innovative Project of the Year” category. The project developed a new framework which extends the field of Human-Computer Interaction (HCI) to encompass aspects of user experience, mobility and the outside environment and creates a new model for immersion [Cater-2,3,4]. We have run numerous studies with the general public to increase our understanding of what new technologies are needed. The work on pervasive computing has now been turned into a company, Mista Ltd. Fraser and Subramanian have been working in related fields, by looking at aspects of HCI in relation to interaction in public spaces or using non-traditional input devices [Fraser-2,3,4, Subramanian-2,3]. This has wide-ranging application, for example in displays in museums.
Mayol-Cuevas* has pioneered the use of wearable vision and personal robotics by integrating three research areas: robotics, computer vision and wearable computing [Mayol-Cuevas-1,2,3]. This work advanced wearable sensing by incorporating real-time active vision into wearable systems to produce some of the first examples of concurrent activity recognition and positioning algorithms. He furthermore proposed the first objective methodologies to select sensor placement around the human figure.
The Bristol Robotics Lab (BRL) is a large research laboratory set up between ourselves and the University of the West of England. The BRL enables us to conduct large-scale robotics experiments on robotics. The laboratory is led by Melhuish, whose work has ranged from haptics, to creating robotics which power themselves from their environment [Melhuish-2,3], to the development of controllers and autonomous robots. The research at the BRL now involves Calway, Campbell (N),Fraser and Mayol-Cuevas*.
Architecture and Design
Kerstin Eder (SL), Steve Gregory (SL), Simon Hollis* (L), David May (P), Henk Muller (R), Daniel Page* (L), Dhiraj Pradhan (P)
This research addresses a wide range of topics including programming language design, implementation, analysis, transformation and parallelisation. In addition the group looks at the specification, design, analysis and verification of both software and hardware systems.
Pradhan’s research has focused on verification, low-power design and VLSI testing. He has used Galois switching theory to provide a new mathematical framework for multi-level verification. He has shown that an efficient word-level representation of logic is possible using Galois switching theory and how logic simulation can be sped up using this representation [Pradhan-4]. Pradhan has developed a new SAT algorithm, NIVER, which has been shown to be faster for certain SAT problems in the VLSI CAD area [Pradhan-2]. A new approach has been developed for low-power memory and a new BIST methodology for VLSI testing.
Eder has developed a completely new approach, using techniques from machine learning, to the design and verification of microprocessor pipelines. The approach is based on a formal model of the pipeline flow control logic which for the first time allowed reasoning about timing and performance as well as functional correctness [Eder-1]. In collaboration with Flach she has developed a coverage-directed test generation method based on advanced coverage analysis techniques and inductive learning from examples to automate simulation-based verification of semiconductor designs [Eder-2,3]. This method is covered by a recent UK patent application.
May’s work on a range of programmable components based on a tileable multithreaded event-driven processor has resulted in a spin-out company called Xmos Ltd. It promises to bring programmability to a wide range of application areas, especially in consumer electronics [May-3,4]. May, Muller, Page* and Smart have developed and evaluated a series of non-deterministic processor designs which act to provide a defence against current side-channel attacks, a current concern for smart-card designers [May-1, Muller-2].
Page* has created CAO, an open-source language and compiler specifically designed to address issues of cryptographic implementation from a performance and side-channel perspective. Hollis* has performed research on various interconnect technologies suitable for multi-core processors [Hollis-2,3] and investigated the application of asynchronous interconnects for use in preventing side-channel attacks on smart-cards [Hollis-1].
3. Research Environment
Bristol CS offers a vibrant research environment with a strong emphasis on exchanging ideas and exploiting synergy arising from collaboration between research areas. Regular meetings are organised by most of the research groups or broader activities. These meetings between staff, RAs and PhD students review progress, discuss research priorities, coordinate research, discuss potential future projects and funding applications. Each group organizes a series of seminars and study groups, in addition to a regular departmental seminar series. We regularly host UK and international visitors and invite them to give seminars.
Since 2001, CS at Bristol has appointed a large number of new staff of exceptional promise, namely Bogacz*, Cater*, Clifford*, De Bie*, Fraser, Gough*,Harrow*, Hollis*, Marshall*, Mayol-Cuevas*, Oswald*, Page*, Ray*, Reinhard, Subramanian* and Warinschi*. In addition we have appointed two new professors: Cristianini and Cliff, and have made the joint appointment of Melhuish. As a result, we now have a very powerful mix of promising junior staff and highly experienced senior staff (2 research fellows, 12 lecturers, 8 senior lecturers, 6 readers and 9 professors).
Our recruitment policy is to strengthen our existing groups whilst looking for opportunities to expand our research programmes into significant new areas: for example biologically-inspired computing and robotics. In 2006 we were awarded 3 RCUK Research Fellowships, of which the two remaining ones are about to be appointed.
Early career researchers are fully supported: each is assigned a mentor who is close to their research interests and who guides them through all aspects of their new role, from teaching to research. Initially, they are given reduced teaching and administrative loads to enable them to build up a significant research standing via publications, grants and industrial links. Senior staff aim to help and guide both early career researchers and others by sharing best practice and disseminating information from the various sources which are not available to more junior staff.
PhD students are monitored via a six-monthly review, by means of a short seminar to which all staff and students are invited. Academic staff convene after the presentation to discuss the student’s progress, and written and oral feedback is provided by a designated member of staff, different from the student’s advisor. Students are required to produce a research plan by the end of the first year, and from the middle of the second year they are required to produce a thesis plan and draft chapters.
Computing, file storage and internet support is provided for all academic and research staff, visitors and research students on an on-demand basis. This includes filestores with multiple copy back-up, multi-terabyte filestores (raided and mirrored) and terabyte real-memory machines. Management of the technical infrastructure is carried out by a small team of highly experienced staff. New investments include high-dynamic-range displays, interactive walls, haptic devices, networking with 10Gbit backbone and 1Gbit to desktop and wireless throughout.
The University has made a major £6.3m investment to install an extensive high-performance computing (HPC) infrastructure. The currently running interim system consists of 96 nodes each with two dual-core opteron processors, 8 GB of RAM and 11 TB of storage. By 2008-Q1, this will be upgraded to 512 nodes (around 4000 cores), with a capacity of over 13 trillion Flops. Another £2m has been committed by the University to install an additional 600 TB of storage by 2010, with an accessibility layer particularly suited to data curation and mining. May is a member of the university’s HPC board and executive committee.
We are closely involved in a number of University-wide Research Themes. These are a UoB strategy to help focus strategic investments into areas in which Bristol is, or has the potential to be, world-leading. In particular, we have significant involvement in the following themes and drive the agendas of several of these:
v Exabyte Informatics brings together all the researchers in the University involved in curation and mining of large amounts of data.
v Nanoscience and Quantum Information unites the University’s work in small-scale phenomena, as exemplified by the processing of quantum information. The University has invested £10m in a new, extremely ‘quiet’ building to support this research.
v Neuroscience involves researchers looking into form and function of the brain.
v Predictive Life Sciences brings together the University’s work in genomics, biologically-inspired computing and other areas in which biologists can inspire and be inspired by the processing of information.
v Robotics and Autonomous Systems focuses on systems which act under their own control or under close supervision from people.
Funding for our research comes from a variety of sources including EPSRC, ESRC, AHRC, SSRC, MRC, EU, DTI and Industry. We are committed to inter-disciplinary academic research and applied research with industrial partners, and have hence pursued a strategy of employing energetic new staff with interests in areas such as neuroscience, quantum information, robotics and biologically-inspired computing. In Bristol, we are fortunate in that our nearby industry includes world-leaders in computing (HP, Toshiba), Microelectronics (ST, Infineon, Broadcom, Icera, Picochip) and media (BBC, Granada, 422, Aardman). Two staff members, May and Martin have a significant portion of their time bought out by Xmos and British Telecom respectively. The activities of each of our research groups involve visiting industrial staff. At present there are 20 of these from various companies drawn from the list above and others.
Together with colleagues in Electronic Engineering, we carry out a number of projects through 3CR, a University Innovation Centre initially funded by the DTI but now self-supporting. 3CR (www.3cresearch.co.uk) is a non-profit company, whose board is chaired by May. The company has many industrial partners including HP, Granada, QinetiQ, GCHQ, Thales and Toshiba.
We are heavily involved in enterprise. Over the last five years, staff and student projects have led to several new-starts including Baby Interact (Muller), Identum (Smart, Page*), Mista (May), Syritta Algorithmics (Cliff) and Xmos (May). In addition four companies, Iktrix, Imetrum, Pyxis Design and SensaGest, have been created by former research assistants and a number of companies have been formed by our undergraduates with support from the University.
Bristol CS has a considerable and fruitful international dimension. Over one half of our category A staff are non-UK or have held academic positions abroad. A large proportion of our recent appointments were recruited from overseas: Bogacz* (Princeton), Cristianini (UCDavies), De Bie* (KU Leuven), Gough* (Pasteur Institute, Paris), Harrow* (MIT), Oswald* (TU Graz), Reinhard (UCF), Subramanian* (Philips Research, Netherlands) and Warinschi* (UCSD). Many staff members retain collaborations with their previous institutions and other overseas partners, and develop new ones. This is evident from the publications returned in RA2, of which more than a quarter have one or more international co-authors.
Our Worldwide Universities Network (WUN, www.wun.ac.uk) partnership links us with a number of leading international Universities such as Bergen, Urbana-Champaign, Nanjing, Washington State and Wisconsin at Madison (where Flach visited for five weeks in Summer 2004). Other recent collaborations include our UK partnership with Bath, Southampton and Surrey and the associated international partnership with San Diego and Irvine via Set-Squared. In addition we are involved in the Great Western Research initiative between the local RDA and companies and universities in the region, including Bath, Exeter and Plymouth.
4. Esteem Indicators
1. Programme Committee member International Workshop on Modelling Natural Action Selection, 2005.
2. Guest Editor, Machine Learning journal, 2002; Bioinformatics journal, 2003; Neurocomputing journal, 2003.
3. Director EPSRC National Institute for Large-Scale Complex IT Systems Research & Training (£14.6m projected expenditure over 5 years), 2005–present.
4. Member of EPSRC Strategy Advisory Team for ICT, 2004–present..
5. Member of Lord Sainsbury’s Stakeholder Committee for Foresight Cognitive Systems Project, 2002–4.
6. Organiser of “The Legacy of W Grey Walter” three-day symposium on bio-inspired robotics, 2002
7. Royal Society Wolfson Merit Award, 2007–present.
8. Associate Editor of Journal of Artificial Intelligence Research, 2005–present.
9. Associate Editor of Journal of Machine Learning Research, 2001–present.
10. Invited speaker at the European Conference on Machine Learning, 2007.
11. Programme Co-Chair of the European Conference on Machine Learning, 2001.
12. Associate Editor of Machine Learning journal, 2001–5.
13. Programme Co-Chair of the 2009 ACM Conference on Data Mining (appointed in 2007).
14. Editor of Journal of Proteins, 2007–present.
15. Programme Chair for FANTOM 3, 2004.
16. Fellowship from Burroughs-Welcome fund, 2002–3.
17. Invited speaker at Keystone Symposium on Structural Genomics, 2002.
18. Best paper award at GECCO 2005.
19. Associate Editor of the IEEE Transactions on Evolutionary Computation, 2004–present.
20. General Chair of AISB 2006 (with Marshall).
21. Programme Chair and Organiser of SMPS 2006.
22. Invited Speaker for the 28th Linz Seminar on Fuzzy Set Theory, 2007.
23. General Chair of AISB 2006 (with Kovacs).
24. Programme Committee member for European Conference on Artificial Life 2005.
25. Programme Chair IEEE International Conference on Fuzzy Systems 2007.
26. Invited keynote speaker, French National Fuzzy Logic Conference 2004.
27. British Telecom Senior Research Fellowship, 2001–present.
28. Short-term Fellowship of the Japan Society for the Promotion of Science, 2007.
29. Programme Co-Chair of 2005–7 workshops on Integration of Abduction and Induction in AI.
30. Royal Society Research Fellowship, 2005–present.
31. Programme Committee member British Machine Vision Conference, 2000–present (excl. 2005).
32. Programme Committee member IEEE Conference on Image Processing, 1996–present.
33. Associate Editor of Pattern Recognition, 2006–present.
34. Member of ACM SIGGRAPH short papers/sketches jury and session chair, 2003–4.
35. ACM SIGGRAPH International Relations Director, 2006–present.
36. International Resources Programme Chair for SIGGRAPH 2006.
37. Associate Editor of the journal Pattern Analysis and Applications, 2006–present.
38. Chair of the British Machine Vision Association, 2005–present.
39. Member of steering committee of Medical Image Understanding and Analysis Organisation, 2005–present.
40. Guest Editor for Journal of Document Analysis and Recognition, 2005.
41. Editor-in-Chief of ACM Transactions on Applied Perception, 2003–present.
42. Program chair of ACM Symposium on Applied Perception in Graphics and Visualization, 2006.
43. Invited speaker at Society for Information Display International Symposium, Seminar and Exhibition, 2007.
44. Member of Commission Internationale de l’Eclairage technical committee TC8-08, 2004–present.
45. Member of the Organising Committee of the UK-Korea Bioinformatics Workshop 2005.
46. Member of the Organising Committee of the London Stringology Day, LSD 2005.
47. Marie Curie Incoming International Fellowship, 2006–8.
48. LMS Naylor Prize and Lectureship, 2004.
49. EPSRC Senior Research Fellowship, 1999–2003.
50. Simons Visiting Research Professor at MSRI Berkeley, 2002.
51. Invited keynote address at EQIS 2004.
52. Best paper award at CHES 2005.
53. General Chair CHES 2007, Programme Chair CHES 2008.
54. Invited talk at ECC conference 2006 and IPAM workshop 2006.
55. Invited speaker at ECC conference 2004, 2005 and 2006.
56. Technical advisory board member: Certicom (2000–1), Karthika (2001–3) and Identum (2002–present).
57. Programme Chair of EUROCRYPT 2008.
58. Best newcomer paper award at PODS 2005.
59. Invited keynote speaker, Models for Cryptography Workshop, 2006.
60. ACM SIGCHI best paper award, 2005.
61. Member of National Centre for e-Social Science Research Board, 2003–present.
62. Invited member of the e-science programme Usability Task Force, 2004–present.
63. Plenary Talk at Modelling and 3D Reconstruction workshop, University of Cantabria, 2005.
64. Invited talk at ECCV 2006.
65. Invited talk at IST EU ‘Beyond Robotics’ Conference, 2002.
66. Best paper award at TAROS 2006.
67. Member of FP7 IST Advisory Group, 2007–present.
68. Bristol Principal Investigator for Equator IRC (£10m, £1.2m to Bristol), 2000–7.
69. Invited external EU reviewer of FP6 IP WEAR-IT@Work, 2005–7.
70. Workshops Chair of UbiComp 2007.
71. Programme Committee member of Ubicomp 2006.
72. Programme Committee member of ISWC 2004, 2006–7.
73. Programme Committee member Computer Vision Theory and Applications, 2006.
Architecture and Design
74. Invited speaker at the IEE Symposium on System-on-Chip Challenges, 2003.
75. Leading academic advisor on the UK design verification roadmapping exercise by the National Microelectronics Institute, 2006–present.
76. Fellow of Royal Society, 1991–present.
77. Technical advisory board member: Picochip (2001–present), Icera (2003–present), Arithmatica (2003–present) and Clearspeed (2005–present).
78. Expert witness: Intel Corp vs Via technologies (2001–3), LG vs Clevo (2004–5).
79. IEEE Fellow, 1988–present.
80. ACM Fellow, 1999–present.
81. Humboldt Prize winner, 2005.
82. Editor IEEE Transactions on Computers, 2002–present.
5. Future Strategy
We broadly expect our research in the immediate future to be organised in the same five core activities, with shifting emphasis in response to new research challenges and opportunities. In this section we outline our main research plans and strategy in each of these activities.
The ubiquity and on-line availability of digital data is giving rise to a new paradigm of data-centric computing. In our Intelligent Systems research, we will address a range of research challenges arising from this paradigm shift, exploiting our expertise in data mining, the study of complexity arising in natural and engineered systems and the CS/biology interface.
v In the context of the Exabyte Informatics UoB research theme, we will target a number of research challenges including modelling media, web and scientific content through pattern analysis and machine learning. We will then embed the data in a semantic shell containing rich annotation and relevant background knowledge. In addition we will employ network analysis techniques to exploit the wealth of information encoded in interaction networks of various kinds.
v We will create self-describing data, able to answer simple questions and aware of other data sources and the resources needed to find answers to a specified degree of accuracy. The ultimate aim is to create a universal interface to text and semi-structured data, whether in documents, databases or hidden behind a query/retrieval system, making use of XML and richer markup such as the semantic web, coupled with the use of soft computing to handle the inherent difficulty of expressing and processing imprecise natural language terms.
v Bristol is well-placed to become a leading centre in Predictive Life Sciences (another UoB research theme) given the concentration and diversity of high-quality researchers in this area. We will apply machine learning techniques to understand the decision processes in the brain. We will investigate whether our computational models can help in treating a variety of human disorders connected with the malfunction of the relevant parts of the brain, such as Parkinson’s disease.
v We will investigate distributed learning within label semantics frameworks, in order to improve understanding of the potential usefulness of fuzziness in communications between robotic systems, with application to autonomous vehicles. In collaboration with the Bristol Robotics Laboratory, we will develop theories and practical implementations for intelligent and aware bio-mimetic robotics.
Our work in digital media focuses on the pipeline of capture of graphical data, via computer vision techniques, through to its display via animation and production on new HDR devices. It also encompasses a number of application domains such as medicine, biology and film and game production. We envisage the application of such technologies to expand considerably in the near future.
v In high dynamic range (HDR) imaging we will expand our efforts to include the full high dynamic range imaging pipeline, in particular the capture of HDR images and video. We will develop novel applications in this area by integration of high dynamic range imaging, computer graphics, computer vision and colour science.
v We will extend our portfolio of medical image analysis work by new links to medical physics units in Bristol and beyond, including work with the soon to be built Bristol Brain Imaging Centre. We will particularly target very high accuracy object segmentation, statistical texture defect detection and texture segmentation.
v In collaboration with the departments of Physics and Biological Sciences we have successfully completed the field trials of a novel system capable of identifying individuals amongst a colony of penguins off the coast of South Africa. We will apply data mining techniques to huge amounts of observations and hence answer questions such as “Does a particular animal always feed at the same time?” and “Do animals always hunt with the same group?”
Research in foundations will continue to investigate theoretical and practical issues in algorithms, complexity and cryptography. In many of these areas new tools will need to be developed, to cope with increased mathematical and system complexity. In the field of quantum computation, the interplay between classical and quantum complexity is expected to dominate.
v Our work in cryptography will be extended by investigating in more detail the issues arising from the interaction of implementation and provable security, especially in the area of pairing-based cryptography.
v We aim to create automatic analysis tools for cryptographic protocols which allow the merging of the cryptographic and the formal methods traditions, focusing particularly on specific application domains such as e-voting. This is particularly challenging since current formal models cannot cope with commitments.
v In quantum computation we will address questions such as: Can quantum algorithms provide better poly-time algorithms for tasks where classical poly time algorithms are already known? Can quantum algorithms provide better parallelisability features than classical algorithms for a given task? We furthermore aim to answer the question as to whether quantum computation can offer better approximation algorithms for NP problems.
The proliferation of mobile devices and other forms of non-traditional computing devices is expected to continue at or exceed the current pace. This will lead to a great deal of future challenges at the human/computer, or human/robot, interface. The future strategy of our Personal Systems research is to apply our knowledge of human experience and interaction to small devices, robotics and haptics, thus cementing our strengths in these new areas, whilst continuing our very successful research in pervasive computing.
v A key challenge for wearable computing and robotics is the development of low-cost, low-power computer vision systems. By bringing together our recent work on real-time algorithms, single chip multiprocessors and digital imagers, we aim to make vision a robust, low-cost and widely available technology.
v We will investigate the use of cameras to recover, concurrently, high-level descriptions of visual scenes and to use real-time vision in highly portable robotic devices to assist people such as those who are partially sighted.
v We will expand our Real-Time Camera Localisation project, aiming towards robust wide area monocular SLAM, with emphasis on incorporating robustness to realistic human activity and integration into wearable computing applications, including additional sensor information such as ultrasound and GPS.
Architecture and Design
Research challenges involve the whole design pipeline of a modern microprocessor, from circuit-level verification to higher-level architectural issues and how these relate to the software which runs on the microprocessor. Our collaboration with the local semiconductor community will intensify via various initiatives, supported by industry, the RDA and the University.
v Commercial hardware synthesis tools rely on mapping a predetermined, fixed data flow graph onto hardware, without modifying the graph prior to architectural synthesis, which seriously limits the scope of any architectural optimisation. Using the word-level representation previously developed, we will develop new synthesis tools alleviating this limitation.
v Our work in simulation-based design verification will be extended in collaboration with the world-leading IBM Research Labs in Haifa. In collaboration with Airbus we will develop a portable Microprocessor Instruction and Data Abstraction System suitable for use in hard-realtime, safety-critical control system applications.
v Our work in computer architecture for security applications will be extended with the development of CRISP, a processor architecture and ISA designed for lightweight, high performance cryptography. The key differentiating feature of this work is a re-evaluation of the RISC processor design philosophy in the context of non-media, performance-critical codes.
v We will investigate languages and architectures which make million-processor machines useful and useable. A key issue for an easily programmable highly parallel computer is the interconnect, especially its ability to diffuse computations rapidly. Our pioneering work on practical low-cost multicore architectures will be the starting point for this research.
6. Sustainability and Vitality
The future of Computer Science research in Bristol looks extremely exciting. With a broad portfolio of expertise, high grant income streams and ever-increasing collaborations with other disciplines, we are confident of a steady and sustained growth. The University remains deeply committed to Computer Science, as evidenced by the expansion of Computer Science since the last RAE.
In particular, in the immediate future we are requesting £10m from the University to invest in a Centre of Excellence in Microelectronics, jointly with the Electronic Engineering department. This is part of an initiative with local industry, which also aims to bring in a significant level of industrial income to support this area.
We aim to capitalise on the recent university investment in HPC and data storage, by increasing our interactions with data-rich but computing-poor areas. For example, many disciplines in arts and social science routinely collect large amounts of data, yet lack the facilities to analyse the data fully. We see a great opportunity for data mining applications which make use of the new HPC facility.
A key principle in guiding the direction of Computer Science at Bristol is the interplay between theory and practice. Without a deep theoretical understanding one is unable to make advances in applications, and without practical experience one is unable to guide the development of new theory. We expect a continued strong interaction between all areas of expertise both within the department, within the university and externally. Our strong commitment to inter-disciplinary research means we will continue reaching out to other disciplines.