EPSRC logo

Details of Grant 

EPSRC Reference: EP/J019283/1
Title: Next generation pattern matching
Principal Investigator: Clifford, Dr R
Other Investigators:
Researcher Co-Investigators:
Project Partners:
Bar-Ilan University
Department: Computer Science
Organisation: University of Bristol
Scheme: EPSRC Fellowship
Starts: 01 January 2013 Ends: 31 December 2018 Value (£): 941,287
EPSRC Research Topic Classifications:
Fundamentals of Computing
EPSRC Industrial Sector Classifications:
No relevance to Underpinning Sectors
Related Grants:
Panel History:
Panel DatePanel NameOutcome
30 Aug 2012 EPSRC ICT Fellowships Interviews - Aug 2012 Announced
18 Jul 2012 EPSRC ICT Responsive Mode - July 2012 Announced
Summary on Grant Application Form
This fellowship proposal is for a programme of fundamental research to develop the knowledge required for the next generation of pattern matching algorithms. The aim is to make significant

advances in both the theory and practice of searching, manipulating and processing massive datasets of the sorts that are now common in high technology industries and to make state of the art tools available to the wider community.

This proposal will not only develop new algorithms but will also show time and space lower bounds. Where ever faster and more efficient algorithms are developed by the algorithms community, our understanding of the limits of what can be achieved is currently at a much more basic level. Such lower bounds, were they available, would not only be important for the significant theoretical interest and insight they provide, but also for the practical purpose of preventing fruitless search for algorithms which cannot exist. Within computer science in general, lower bounds have historically proven hard to develop (consider for example the famous question of P vs NP) but in the context of streaming and dynamic computation new ideas can now be applied for the first time.

In order to give a truly complete picture, we will also provide state of the art implementations of both new and some old ideas to test assumptions that have been made and to discover new problems which need to be tackled by the whole community. Implementing pattern matching algorithms, especially those proven to be theoretically efficient, can often be a challenging task requiring both considerable algorithmic and engineering expertise. To ensure maximum impact for the ideas developed we will produce freely available, publicly accessible, state of the art implementations of the newly developed pattern matching algorithms as well as others whose practical performance is still unknown.

Key Findings
This information can now be found on Gateway to Research (GtR) http://gtr.rcuk.ac.uk
Potential use in non-academic contexts
This information can now be found on Gateway to Research (GtR) http://gtr.rcuk.ac.uk
Impacts
Description This information can now be found on Gateway to Research (GtR) http://gtr.rcuk.ac.uk
Summary
Date Materialised
Sectors submitted by the Researcher
This information can now be found on Gateway to Research (GtR) http://gtr.rcuk.ac.uk
Project URL:  
Further Information:  
Organisation Website: http://www.bris.ac.uk