Grant: Discovery Grants Program - Individual
University of Waterloo
$31,000.00
Systems and Foundations For Massive-Scale Data Management
FY 2019-20
Summary
As the volume of data grows, and the speed of new data generation increases, many applications process their data on highly-parallel distributed data management systems. The objective of this proposal is to study distributed data management systems with a focus on two areas: (1) theoretical foundations of massive-scale data management systems; and (2) systems for processing large-scale graph data.***On theoretical foundations, my focus is on understanding the fundamental limitations of distributed algorithms for answering queries over relational data and evaluate how ""good"" they are. Distributed algorithms differ in their parallelism levels, communication and computation costs, and the number of rounds of computation, i.e., machine synchronizations, they require. My goal is to derive lower or upper bounds on the costs of algorithms that perform a task over data. Specifically, I intend to study two questions:*** 1. Power of synchronization: How many rounds of computation are needed to answer a query?*** 2. Limits of parallelism: What is the maximum number of machines that can be utilized to answer a query?***On large-scale graph processing, my focus is on general-purpose distributed graph systems. Large-scale graphs are at the core of many applications, such as web search, social networks, and genetic analysis. Broadly, these applications perform the following tasks on graphs: (1) batch graph algorithms; (2) machine-learning algorithms; (3) finding subgraphs; and (4) real-time analysis if the graph is evolving. Existing systems support one or two of these tasks. My goal is to build a system that supports all of these tasks and is based on the timely dataflow (TD) execution model. TD is an inherently streaming model, which can support real-time analysis, but has mechanisms to support synchronous and asynchronous computations, which can support batch graph algorithms, machine-learning algorithms and subgraph finding. Specifically, I intend to study the following issues:*** 1. TD operators of a general-purpose graph system.*** 2. Query languages and APIs that efficiently compile to these TD operators.*** 3. Storage models that are efficient under limited cluster memory.*** 4. Tools for testing and debugging graph applications running on TD.***This work will establish theoretical foundations for massive-scale data processing, and produce an open-source prototype system advancing the state of the art in large-scale graph processing.**
Program
Discovery Grants Program - Individual
Recipient
Location
Ontario, Canada
Recipient Type
Academia
Type
Grant
Source
NSERC's Awards Data
As published
Application id
RGPIN-2016-03877
Name nom
Salihoglu, Semih
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
2016
Award amount
31000
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
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
2711
Research subject group en
Information technology
Research subject group fr
Technologie de l'information
Research subject en
Database management
Research subject fr
Gestion de bases de données
Installment
NA
Partie
0
Nb partie
NA
Application title
Systems and Foundations For Massive-Scale Data Management
Keyword
NSERC
Application summary
As the volume of data grows, and the speed of new data generation increases, many applications process their data on highly-parallel distributed data management systems. The objective of this proposal is to study distributed data management systems with a focus on two areas: (1) theoretical foundations of massive-scale data management systems; and (2) systems for processing large-scale graph data.***On theoretical foundations, my focus is on understanding the fundamental limitations of distributed algorithms for answering queries over relational data and evaluate how ""good"" they are. Distributed algorithms differ in their parallelism levels, communication and computation costs, and the number of rounds of computation, i.e., machine synchronizations, they require. My goal is to derive lower or upper bounds on the costs of algorithms that perform a task over data. Specifically, I intend to study two questions:*** 1. Power of synchronization: How many rounds of computation are needed to answer a query?*** 2. Limits of parallelism: What is the maximum number of machines that can be utilized to answer a query?***On large-scale graph processing, my focus is on general-purpose distributed graph systems. Large-scale graphs are at the core of many applications, such as web search, social networks, and genetic analysis. Broadly, these applications perform the following tasks on graphs: (1) batch graph algorithms; (2) machine-learning algorithms; (3) finding subgraphs; and (4) real-time analysis if the graph is evolving. Existing systems support one or two of these tasks. My goal is to build a system that supports all of these tasks and is based on the timely dataflow (TD) execution model. TD is an inherently streaming model, which can support real-time analysis, but has mechanisms to support synchronous and asynchronous computations, which can support batch graph algorithms, machine-learning algorithms and subgraph finding. Specifically, I intend to study the following issues:*** 1. TD operators of a general-purpose graph system.*** 2. Query languages and APIs that efficiently compile to these TD operators.*** 3. Storage models that are efficient under limited cluster memory.*** 4. Tools for testing and debugging graph applications running on TD.***This work will establish theoretical foundations for massive-scale data processing, and produce an open-source prototype system advancing the state of the art in large-scale graph processing.**