Canada Spends Logo

Explore our Budget 2026 analysis

Grant: Discovery Grants Program - Individual

Simon Fraser University

$29,000.00

Streaming Algorithms for Structural Trends

FY 2015-16

Summary
Over the past years, computer science has been responding to the ever-increasing data size by exploring new ways and models of computation.  This proposal focuses on the theoretical aspects of this effort by exploring streaming algorithms. A streaming algorithm reads its input left to right over one or more passes. This model corresponds to reading data from sequential storage, as well as processing as it is generated on the fly. The main limitation is that the space use must stay well below the input size. To comply, the algorithm  typically condenses its data into a small summary, losing many details and obtaining an output that is only approximately correct. Most of the streaming research is in discovering statistical information, such as element frequencies, which is independent of the order of the elements in the stream.  In this proposal, we propose to focus on and develop tools for the less well-studied problems of discovering ""structural"" trends such as monotonicity, periodicity, etc, which rely on the order of the elements in the input. Previous work as well as our preliminary results indicate strong relationships linking structural trends in streams to one another.  For instance, one can discover periodicity by using pattern matching, and discover palindromes by using periodic properties.  Our main goal is to understand these relationships and help build a common ""vocabulary"" of tools, similar to the sketching algorithms discovered over the past 15 years for statistical problems, that will apply to the general problem of discovering structural trends.  Example problems include various versions of monotonicity and common sequences, frequent substrings, smoothness of the input, local periodicity, squares (and cubes) in streams, etc. Problems on the ordering of the input occur in fields such as bioinformatics and networks.  However, most existing models are too simple to be of use in an applied setting.  Complications that simple models cannot handle include noisy data, slow changes in the input over time, the involvement of difficult subproblems (such as dealing with edit distance in a stream environment), etc., which makes the algorithms design messy.  It is the goal of the PI to understand (feasible) applications and build their needs into the model in a realistic, clean way.  For instance, while finding perfect palindromes in a stream is reasonably easy, finding those that might have a few incorrect characters is open.  In order to solve such problems, we propose to consider and build tools that are custom-designed for handling real world complications. We also propose to work on recent models that use streaming implicitly in an ad hoc manner (such as the MapReduce application) that would benefit from more theoretical rigour.  The ultimate goal of this research is to better our understanding of big data processing in the theoretical sense, as well as make it more amenable for real applications.
Program
Discovery Grants Program - Individual
Location
British Columbia, Canada
Recipient Type
Academia
Type
Grant
Source
NSERC's Awards Data

As published

Application id
RGPIN-2015-04465
Name nom
Ergun, AyseFunda
Department département
Computing Science, School of - Computing Science, School of
Organization id
5
Institution établissement
Simon Fraser University
Province en
British Columbia
Province fr
Colombie-Britannique
Country en
CANADA
Country fr
CANADA
Fiscal year exercice financier
2015
Competition year année de concours
2015
Award amount
29000
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
1
Nb partie
5
Application title
Streaming Algorithms for Structural Trends
Keyword
NSERC
Application summary
<p>Over the past years, computer science has been responding to the ever-increasing data size by exploring new ways and models of computation.  This proposal focuses on the theoretical aspects of this effort by exploring streaming algorithms. </p> <p>A streaming algorithm reads its input left to right over one or more passes. This model corresponds to reading data from sequential storage, as well as processing as it is generated on the fly. The main limitation is that the space use must stay well below the input size. To comply, the algorithm  typically condenses its data into a small summary, losing many details and obtaining an output that is only approximately correct.</p> <p>Most of the streaming research is in discovering statistical information, such as element frequencies, which is independent of the order of the elements in the stream.  In this proposal, we propose to focus on and develop tools for the less well-studied problems of discovering ""structural"" trends such as monotonicity, periodicity, etc, which rely on the order of the elements in the input.</p> <p>Previous work as well as our preliminary results indicate strong relationships linking structural trends in streams to one another.  For instance, one can discover periodicity by using pattern matching, and discover palindromes by using periodic properties.  Our main goal is to understand these relationships and help build a common ""vocabulary"" of tools, similar to the sketching algorithms discovered over the past 15 years for statistical problems, that will apply to the general problem of discovering structural trends.  Example problems include various versions of monotonicity and common sequences, frequent substrings, smoothness of the input, local periodicity, squares (and cubes) in streams, etc.</p> <p>Problems on the ordering of the input occur in fields such as bioinformatics and networks.  However, most existing models are too simple to be of use in an applied setting.  Complications that simple models cannot handle include noisy data, slow changes in the input over time, the involvement of difficult subproblems (such as dealing with edit distance in a stream environment), etc., which makes the algorithms design messy.  It is the goal of the PI to understand (feasible) applications and build their needs into the model in a realistic, clean way.  For instance, while finding perfect palindromes in a stream is reasonably easy, finding those that might have a few incorrect characters is open.  In order to solve such problems, we propose to consider and build tools that are custom-designed for handling real world complications.</p> <p>We also propose to work on recent models that use streaming implicitly in an ad hoc manner (such as the MapReduce application) that would benefit from more theoretical rigour.  </p> <p>The ultimate goal of this research is to better our understanding of big data processing in the theoretical sense, as well as make it more amenable for real applications.</p>   <p> </p> <p> </p> <p> </p> <p> </p> <p> </p> <p> </p> <p> </p> <p> </p>