Canada Spends Logo

Explorez notre analyse du budget 2026

Grant: Discovery Grants Program - Individual

McMaster University

$17,000.00

""Regularities in Strings: New Combinatorial Properties, More Efficient Algorithms, Applications""

EF 2015-16

Résumé
One of the prominent features of the last quarter-century, especially the last ten years, has been the ""information explosion"", the vast increase in data that is stored, transmitted, processed by computers and communications devices. With such huge data sets, efficiency of processing matters very much. The operations that must be performed are often very simple, usually describable as computing ""patterns"" in strings, but collectively they must be performed quickly. What mathematicians call a ""string"" (or ""word"") is a sequence of letters drawn from some alphabet; for example, a day's e-mail traffic (trillions of binary digits), the Internet (tens of billions of web pages, averaging thousands of characters each), the human genome (three billion letters A, C, G, or T) and other genomes (up to a trillion letters). At present much of the processing of strings depends on the computation of global data structures called ""suffix arrays"", while at the same time the pattern being sought is local and small. In a sense, then, current methods, sophisticated and powerful as they are, are nevertheless still ""brute force"" -- they do not use the local combinatorial properties of the string that determine whether the pattern is there or not. The basic idea of this proposal is to provide local combinatorial analysis that will determine the existence (or not) of the desired patterns as the string is traversed from left to right. This analysis depends on a simple, partially-proved conjecture (12 out of 14 subcases have been established within one of several cases): three independent squares cannot occur in a confined neighbourhood within a string. In recent papers the applicant's results go far beyond what was known before; this project's purpose is to take the combinatorial analysis to its conclusion, then make use of the results to design algorithms that are sensitive to local conditions in the string, and that therefore can execute much more quickly by means of a simple left-to-right scan.
Programme
Discovery Grants Program - Individual
Bénéficiaire
Emplacement
Ontario, Canada
Type de bénéficiaire
Academia
Type
Grant
Source
NSERC's Awards Data

Tel que publié

Application id
8180-2012
Name nom
Smyth, William
Department département
Computing and Software
Organization id
27
Institution établissement
McMaster University
Province en
Ontario
Province fr
Ontario
Country en
CANADA
Country fr
CANADA
Fiscal year exercice financier
2015
Competition year année de concours
2012
Award amount
17000
Program id
RGPIN
Program name en
Discovery Grants Program - Individual
Program name fr
Programme de subventions à la découverte - individuelles
Group en
Discovery grants programs
Group fr
Programmes de subventions à la découverte
Committee code
1507
Committee name en
Computer Science
Committee name fr
Sciences informatiques
Area of application code
1207
Area of application group en
Advancement of knowledge
Area of application group fr
Avancement des connaissances
Area of application en
Information, computer and communication technologies
Area of application fr
Technologie de l'information, des ordinateurs et des réseaux de communications
Research subject code
2713
Research subject group en
Information technology
Research subject group fr
Technologie de l'information
Research subject en
Algorithms
Research subject fr
Algorithmes
Partie
4
Nb partie
5
Application title
""Regularities in Strings: New Combinatorial Properties, More Efficient Algorithms, Applications""
Keyword
NSERC
Application summary
One of the prominent features of the last quarter-century, especially the last ten years, has been the ""information explosion"", the vast increase in data that is stored, transmitted, processed by computers and communications devices. With such huge data sets, efficiency of processing matters very much. The operations that must be performed are often very simple, usually describable as computing ""patterns"" in strings, but collectively they must be performed quickly. What mathematicians call a ""string"" (or ""word"") is a sequence of letters drawn from some alphabet; for example, a day's e-mail traffic (trillions of binary digits), the Internet (tens of billions of web pages, averaging thousands of characters each), the human genome (three billion letters A, C, G, or T) and other genomes (up to a trillion letters). At present much of the processing of strings depends on the computation of global data structures called ""suffix arrays"", while at the same time the pattern being sought is local and small. In a sense, then, current methods, sophisticated and powerful as they are, are nevertheless still ""brute force"" -- they do not use the local combinatorial properties of the string that determine whether the pattern is there or not. The basic idea of this proposal is to provide local combinatorial analysis that will determine the existence (or not) of the desired patterns as the string is traversed from left to right. This analysis depends on a simple, partially-proved conjecture (12 out of 14 subcases have been established within one of several cases): three independent squares cannot occur in a confined neighbourhood within a string. In recent papers the applicant's results go far beyond what was known before; this project's purpose is to take the combinatorial analysis to its conclusion, then make use of the results to design algorithms that are sensitive to local conditions in the string, and that therefore can execute much more quickly by means of a simple left-to-right scan.