CRII: CSR: Partitioning Large Graphs in Deep Storage Architecture

Texas Tech University, Lubbock TX

Investigators

Abstract

Many computing applications that are important for our society, e.g. managing social networks, analyzing human genomes, or modeling human brain connectivity, rely heavily on large graph structures. In practice, representations of large graphs need to be partitioned and stored on a cluster of machines to ensure the desired response time and throughput. Such a classic cross-server partitioning problem has been extensively studied and has been shown to be highly complex. Furthermore, modern deep storage architecture further complicates the problem with the need of "cross-hierarchy" partitioning, i.e., placing graphs into different layers of the storage systems. This change makes existing solutions inadequate. This research aims to pursue a holistic approach that exploits both graph structure and workload characteristics to achieve better performance for distributed graph representations in future deep storage architecture. More specifically, this project includes two synergistic research tasks, together forming a novel graph partitioning solution for deep storage architecture. The first task focuses on an online graph placement algorithm, which could instantly distribute the continuously arriving graph vertices and edges to proper server and specific internal storage layer based on an elaborate heuristic score. Building upon the first task, the second task focuses on adjusting current partitions dynamically according to the workloads. This adjustment is based on a new promotion/demotion algorithm that not only promotes/demotes a single vertex but also changes the priorities of its neighbors according to the Matthew Effect. With the increasing importance of large graph structures and the emergence of new storage technologies, existing graph storage systems experience significant challenges towards graph partitioning. This research effort aims towards building highly efficient distributed graph storage systems in future storage architecture. In addition, this project integrates the research activities with education and outreach efforts to train broadly inclusive and globally competitive science workforce. This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.