Canada Spends Logo

Explorez notre analyse du budget 2026

Grant: Discovery Grants Program - Individual

University of Waterloo

$55,000.00

Efficiency of Data Structures

EF 2022-23

Résumé
This research lies at the heart of Data Structures and Algorithms, indeed at the heart of Computer Science itself. Most is motivated by applications on very large data sets; all is motivated by finding the "best possible way" to solve natural problems. The work is primarily mathematical in nature, developing data structures and proving lower bounds, but also includes some implementations. As demand for fast large information systems escalates, the manner in which data is organized and the algorithms used to manipulate information become increasingly critical. More time and space efficient methods must be created to allow large systems to better perform in response to sophisticated queries and updates. Space efficiency is crucial, not because of a shortage of storage in general, but because dramatic reduction in space requirements can allow the information required by a computation to be in a faster (smaller) level of memory when needed, thus drastically reducing the computation time. The principal focus of this research is to address several aspects of this issue. The first is that of succinct representations of data structures: the representation of structural information (search trees etc.) in the information theoretic minimum space while still permitting the required operations (navigation etc.) in constant time. A natural continuation of this is the application of succinct data structures to text indexing and to geometric problems. In tandem with this application-driven work is the fundamental notion of actually proving that the methods developed are indeed the best possible for the tasks at hand. A second line of research involves the computational complexity of comparison-based problems: issues such as sorting (or partially sorting) in the minimum number of comparisons. This latter work is primarily of theoretical interest and gives motivation for the development of various mathematical tools (such as graph entropy), but it also sheds light on the practical aspects of large scale computation. The work focuses on the intellectual development of the field, but also has real potential for immediate application and advancing Canada's software industry.
Programme
Discovery Grants Program - Individual
Emplacement
Ontario, Canada
Type de bénéficiaire
Academia
Type
Grant
Source
NSERC's Awards Data

Tel que publié

Application id
RGPIN-2018-03972
Name nom
Munro, Ian
Department département
Computer Science, David R. Cheriton School of - Computer Science, David R. Cheriton School of
Organization id
33
Institution établissement
University of Waterloo
Province en
Ontario
Province fr
Ontario
Country en
CANADA
Country fr
CANADA
Fiscal year exercice financier
2022
Competition year année de concours
2018
Award amount
55000
Program id
RGPIN
Program name en
Discovery Grants Program - Individual
Program name fr
Programme de subventions à la découverte - individuelles
Group en
DISCOVERY RESEARCH
Group fr
RECHERCHE AXÉE SUR LA DÉCOUVERTE
Committee code
1507
Committee name en
Computer Science
Committee name fr
Sciences informatiques
Area of application code
801
Area of application group en
Information and communication services
Area of application group fr
Services d'information et de télécommunications
Area of application en
Computer software
Area of application fr
Logiciel
Research subject code
2700
Research subject group en
Information technology
Research subject group fr
Technologie de l'information
Research subject en
Information technology
Research subject fr
Technologie de l'information
Installment
inst:5
Partie
1
Nb partie
6
Application title
Efficiency of Data Structures
Application summary
This research lies at the heart of Data Structures and Algorithms, indeed at the heart of Computer Science itself. Most is motivated by applications on very large data sets; all is motivated by finding the "best possible way" to solve natural problems. The work is primarily mathematical in nature, developing data structures and proving lower bounds, but also includes some implementations. As demand for fast large information systems escalates, the manner in which data is organized and the algorithms used to manipulate information become increasingly critical. More time and space efficient methods must be created to allow large systems to better perform in response to sophisticated queries and updates. Space efficiency is crucial, not because of a shortage of storage in general, but because dramatic reduction in space requirements can allow the information required by a computation to be in a faster (smaller) level of memory when needed, thus drastically reducing the computation time. The principal focus of this research is to address several aspects of this issue. The first is that of succinct representations of data structures: the representation of structural information (search trees etc.) in the information theoretic minimum space while still permitting the required operations (navigation etc.) in constant time. A natural continuation of this is the application of succinct data structures to text indexing and to geometric problems. In tandem with this application-driven work is the fundamental notion of actually proving that the methods developed are indeed the best possible for the tasks at hand. A second line of research involves the computational complexity of comparison-based problems: issues such as sorting (or partially sorting) in the minimum number of comparisons. This latter work is primarily of theoretical interest and gives motivation for the development of various mathematical tools (such as graph entropy), but it also sheds light on the practical aspects of large scale computation. The work focuses on the intellectual development of the field, but also has real potential for immediate application and advancing Canada's software industry.