Grant: Discovery Grants Program - Individual
University of Waterloo
$25,361.00
Compressed Indexes for Sequence Data: Fast Construction and Dynamism
FY 2019-20
Summary
Situations when we need to store and analyze very large data volumes frequently arise in different areas of Computer Science. Although computers are becoming faster and memory size is getting larger, the design of efficient algorithms and data structures is not losing its importance. This is a consequence of the growing size of the data that we must store and computational intensity of problems that we must solve. In many applications working with massive data, such as bioinformatics and information retrieval, the data can be represented as a sequence of symbols (string) or as a collection of such sequences. This proposal focuses on efficient data structures for storage and processing of very large volumes of sequential data. ******Space usage plays a key role in the design of efficient algorithms. If we are able to find a space-efficient representation of the data, we can fit a larger fraction of data into the main memory or cache and reduce the number of access operations to the secondary memory. This raises the question about algorithms and data structures that work with data that is stored in compressed form. Although operations on compressed data can be more costly, the algorithms are frequently more efficient: The number of data transfers between different levels of the memory hierarchy is reduced. This results in a performance gain that outweighs the computational overhead. The study of algorithms for processing structured compressed data (strings, trees, graphs) is a thriving research area. ******The topic of this proposal is compressed representation of string indexes. A string index is a data structure that stores a sequence of symbols and answers pattern matching queries on this sequence. The string index and its variants are ubiquitous in algorithms working on string data. Although there is already a large body of work on this subject, many important questions with practical relevance are still open. In this project I will concentrate on two aspects of compressed indexes that are relevant in scenarios when the data must be changed frequently: (1) space-efficient and fast construction algorithms for string indexes and (2) support of dynamism in string indexes. ******I and my students will study efficient algorithm for constructing space-efficient and compact index structures. Special attention will be given to the space usage of these algorithms and to their relation with other models of computation. My students and I will also study the performance of dynamic data structures supporting pattern matching queries and some more involved queries on string data that is stored in compressed form. Rigorous study of structured data is the central topic of this proposal. But my group and I will also pay attention to practical aspects of data storage methods. Practical efficiency will be tested by implementing some of our results. Thus my research program has potential for immediate application and for advancing software industry in Canada.*
Program
Discovery Grants Program - Individual
Recipient
Location
Ontario, Canada
Recipient Type
Academia
Type
Grant
Source
NSERC's Awards Data
As published
Application id
RGPIN-2019-04225
Name nom
Nekrich, Yakov
Department département
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
2019
Competition year année de concours
2019
Award amount
25361
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
9999
Area of application group en
Not available
Area of application group fr
Non disponible
Area of application en
Not available
Area of application fr
Non disponible
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
Installment
NA
Partie
0
Nb partie
NA
Application title
Compressed Indexes for Sequence Data: Fast Construction and Dynamism
Keyword
NSERC
Application summary
Situations when we need to store and analyze very large data volumes frequently arise in different areas of Computer Science. Although computers are becoming faster and memory size is getting larger, the design of efficient algorithms and data structures is not losing its importance. This is a consequence of the growing size of the data that we must store and computational intensity of problems that we must solve. In many applications working with massive data, such as bioinformatics and information retrieval, the data can be represented as a sequence of symbols (string) or as a collection of such sequences. This proposal focuses on efficient data structures for storage and processing of very large volumes of sequential data. ******Space usage plays a key role in the design of efficient algorithms. If we are able to find a space-efficient representation of the data, we can fit a larger fraction of data into the main memory or cache and reduce the number of access operations to the secondary memory. This raises the question about algorithms and data structures that work with data that is stored in compressed form. Although operations on compressed data can be more costly, the algorithms are frequently more efficient: The number of data transfers between different levels of the memory hierarchy is reduced. This results in a performance gain that outweighs the computational overhead. The study of algorithms for processing structured compressed data (strings, trees, graphs) is a thriving research area. ******The topic of this proposal is compressed representation of string indexes. A string index is a data structure that stores a sequence of symbols and answers pattern matching queries on this sequence. The string index and its variants are ubiquitous in algorithms working on string data. Although there is already a large body of work on this subject, many important questions with practical relevance are still open. In this project I will concentrate on two aspects of compressed indexes that are relevant in scenarios when the data must be changed frequently: (1) space-efficient and fast construction algorithms for string indexes and (2) support of dynamism in string indexes. ******I and my students will study efficient algorithm for constructing space-efficient and compact index structures. Special attention will be given to the space usage of these algorithms and to their relation with other models of computation. My students and I will also study the performance of dynamic data structures supporting pattern matching queries and some more involved queries on string data that is stored in compressed form. Rigorous study of structured data is the central topic of this proposal. But my group and I will also pay attention to practical aspects of data storage methods. Practical efficiency will be tested by implementing some of our results. Thus my research program has potential for immediate application and for advancing software industry in Canada.*