| EPSRC Reference: |
GR/L98640/01 |
| Title: |
TREE STRUCTURES FOR ALGORITHMIC PROBLEMS ON STRINGS |
| Principal Investigator: |
Irving, Dr RW |
| Other Investigators: |
|
| Researcher Co-Investigators: |
|
| Project Partners: |
|
| Department: |
School of Computing Science |
| Organisation: |
University of Glasgow |
| Scheme: |
Standard Research (Pre-FEC) |
| Starts: |
01 April 1998 |
Ends: |
31 March 2001 |
Value (£): |
51,993
|
| EPSRC Research Topic Classifications: |
| Fundamentals of Computing |
|
|
| EPSRC Industrial Sector Classifications: |
| No relevance to Underpinning Sectors |
|
|
| Related Grants: |
|
| Panel History: |
|
|
Summary on Grant Application Form |
|
String processing problems are of increasing importance in computer science and in applications domains such as molecular biology. Among the elegant data structures that have been devised in this context is the suffix tree, which is a form of digital tree that gives an efficient representation of all the substrings of a string, and thereby facilitates fast solutions to many string searching and comparison problems.Comparison trees are classical data structures in computer science with many important uses and applications. Surprisingly, there has been little research into the viability of comparison trees in string searching and comparison problems. But preliminary investigation by the proposer has revealed that such trees, suitably adapted for the context, may well be strongly competitive with suffix trees and other established methodologies such as suffix arrays.A comprehensive theoretical and empirical investigation of the use of search trees in this context is proposed, with a view to identifying their relative strengths and weaknesses, and making software solutions, based on such structures, to practical string problems.
|
|
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.gla.ac.uk |