Grant: Discovery Grants Program - Individual
University of Waterloo
$41,000.00
Highly Scalable Graph Processing
FY 2019-20
Summary
Graph data are of growing importance in many applications, because graphs naturally model complicated structures with explicit representation of the relationships among entities represented by the vertices. One particular type of graph that has increased in importance and poses particular challenges is transactional graphs where each edge represents a transaction between entities represented by the vertices. A common example is a product graph where the vertices represent customers and catalog items and each edge represents a user action (e.g., buying an item, liking an item, putting an item in the shopping cart). Real-time processing of actions and real-time analytics on these graphs is an important problem, and the subject of this discovery grant proposal.******These graphs can be very large and very dynamic with edges added at high speed. For example, Alibaba has reported that they maintain graphs with several billion vertices (that represent customers and catalog items) and in excess of 100 billion edges (that represent behaviours such as clicks, adding to shopping cart, orders, etc). These are streaming graphs where (typically) edges are streamed from one or more sources to one or more processing nodes. The streaming rate of these graphs are very high Alibaba reports peak rates of 320k transactions (edges)/sec raising significant processing challenges. The workloads on these graphs are of two types: transactional (e.g., acting on an edge that represents a purchase as soon as the edge arrives what is known as On-line Transaction Processing or OLTP) and analytical (e.g., recommendation based on recent user activity what is usually referred to as On-line Analytical Processing or OLAP). The current state-of-the-art is to handle these two workloads using separate systems, but organizations have expressed a great desire to be able to process both workloads within a single system over a single graph. The long-term objective of my research is to study architectures and techniques to process OLTP and OLAP workloads on very large streaming graphs with very high streaming rates.******Within this broad framework, I intend to study the following specific problems:******1. Continuous processing of streaming graphs. The primary objective is to investigate robust system architectures that can process a large number of persistent OLTP queries on large streaming graphs.******2. Windowed graph analytics over streaming graphs. The objective is to investigate mechanism for processing OLAP workloads on streaming graphs, which is difficult because these are iterative requiring multiple passes over data. We will investigate windowed processing techniques to complement continuous processing adopted for OLTP workloads.******3. Hardware assist for graph processing. The objective is to study the use of GPUs and FPGAs in a unified architecture (CPU+GPU+FPGA) to assist high volume OLTP and OLAP processing under high streaming rates.
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-04061
Name nom
Ozsu, MTamer
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
41000
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:1 - 5
Partie
1
Nb partie
5
Application title
Highly Scalable Graph Processing
Keyword
NSERC
Application summary
Graph data are of growing importance in many applications, because graphs naturally model complicated structures with explicit representation of the relationships among entities represented by the vertices. One particular type of graph that has increased in importance and poses particular challenges is transactional graphs where each edge represents a transaction between entities represented by the vertices. A common example is a product graph where the vertices represent customers and catalog items and each edge represents a user action (e.g., buying an item, liking an item, putting an item in the shopping cart). Real-time processing of actions and real-time analytics on these graphs is an important problem, and the subject of this discovery grant proposal.******These graphs can be very large and very dynamic with edges added at high speed. For example, Alibaba has reported that they maintain graphs with several billion vertices (that represent customers and catalog items) and in excess of 100 billion edges (that represent behaviours such as clicks, adding to shopping cart, orders, etc). These are streaming graphs where (typically) edges are streamed from one or more sources to one or more processing nodes. The streaming rate of these graphs are very high Alibaba reports peak rates of 320k transactions (edges)/sec raising significant processing challenges. The workloads on these graphs are of two types: transactional (e.g., acting on an edge that represents a purchase as soon as the edge arrives what is known as On-line Transaction Processing or OLTP) and analytical (e.g., recommendation based on recent user activity what is usually referred to as On-line Analytical Processing or OLAP). The current state-of-the-art is to handle these two workloads using separate systems, but organizations have expressed a great desire to be able to process both workloads within a single system over a single graph. The long-term objective of my research is to study architectures and techniques to process OLTP and OLAP workloads on very large streaming graphs with very high streaming rates.******Within this broad framework, I intend to study the following specific problems:******1. Continuous processing of streaming graphs. The primary objective is to investigate robust system architectures that can process a large number of persistent OLTP queries on large streaming graphs.******2. Windowed graph analytics over streaming graphs. The objective is to investigate mechanism for processing OLAP workloads on streaming graphs, which is difficult because these are iterative requiring multiple passes over data. We will investigate windowed processing techniques to complement continuous processing adopted for OLTP workloads.******3. Hardware assist for graph processing. The objective is to study the use of GPUs and FPGAs in a unified architecture (CPU+GPU+FPGA) to assist high volume OLTP and OLAP processing under high streaming rates.