Canada Spends Logo

Explorez notre analyse du budget 2026

Grant: Discovery Grants Program - Individual

Dalhousie University

$22,000.00

Succinct Data Structures with Applications to Large Data Sets

EF 2012-13

Résumé
The problem of efficiently storing and retrieving information is an essential topic in computer science. During the past decades, various techniques have been developed to index data so that the useful information can be retrieved almost instantaneously by performing queries for keywords or phrases. In recent years, as the size of the data has grown rapidly, many techniques that were useful for small, older systems have become infeasible for large, modern applications because they occupy too much storage. Most of this space is not the raw data, but structural information added to improve search efficiency. Succinct data structures were proposed to address this problem, so that the information in large systems can be retrieved quickly, but the space requirement is little more than that of the raw data. In order to provide theoretical and practical solutions to modern systems that process large data sets such as web search engines, geographic information systems and bioinformatics applications, this program will extend the research on succinct data structures, and start new research directions on this subject. The proposed research will use succinct data structures to develop new solutions to fundamental problems in algorithms and computational geometry, such as text search and range search. It will start a new research direction that uses cache-oblivious model to improve the I/O efficiency of succinct data structures for applications that deal with large data sets stored in external memory. It will also start a new line of research by designing succinct data structures for bioinformatics applications and text databases by addressing useful types of searches performed in these systems, such as approximate search. In addition, algorithm engineering will be performed to study the efficiency of our solutions in practice, and code will be contributed to software libraries that deal with succinct data structures, to make them more complete and hence more useful for software development.
Programme
Discovery Grants Program - Individual
Bénéficiaire
Emplacement
Nova Scotia, Canada
Type de bénéficiaire
Academia
Type
Grant
Source
NSERC's Awards Data

Tel que publié

Application id
418613-2012
Name nom
He, Meng
Department département
Computer Science, Faculty of
Organization id
79
Institution établissement
Dalhousie University
Province en
Nova Scotia
Province fr
Nouvelle-Écosse
Country en
CANADA
Country fr
CANADA
Fiscal year exercice financier
2012
Competition year année de concours
2012
Award amount
22000
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
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
2713
Research subject group en
Information technology
Research subject group fr
Technologie de l'information
Research subject en
Algorithms
Research subject fr
Algorithmes
Partie
1
Nb partie
5
Application title
Succinct Data Structures with Applications to Large Data Sets
Keyword
NSERC
Application summary
The problem of efficiently storing and retrieving information is an essential topic in computer science. During the past decades, various techniques have been developed to index data so that the useful information can be retrieved almost instantaneously by performing queries for keywords or phrases. In recent years, as the size of the data has grown rapidly, many techniques that were useful for small, older systems have become infeasible for large, modern applications because they occupy too much storage. Most of this space is not the raw data, but structural information added to improve search efficiency. Succinct data structures were proposed to address this problem, so that the information in large systems can be retrieved quickly, but the space requirement is little more than that of the raw data. In order to provide theoretical and practical solutions to modern systems that process large data sets such as web search engines, geographic information systems and bioinformatics applications, this program will extend the research on succinct data structures, and start new research directions on this subject. The proposed research will use succinct data structures to develop new solutions to fundamental problems in algorithms and computational geometry, such as text search and range search. It will start a new research direction that uses cache-oblivious model to improve the I/O efficiency of succinct data structures for applications that deal with large data sets stored in external memory. It will also start a new line of research by designing succinct data structures for bioinformatics applications and text databases by addressing useful types of searches performed in these systems, such as approximate search. In addition, algorithm engineering will be performed to study the efficiency of our solutions in practice, and code will be contributed to software libraries that deal with succinct data structures, to make them more complete and hence more useful for software development.