CRII: CSR: Partitioning Large Graphs in Deep Storage Architecture

CRII：CSR：深度存储架构中的大图分区

• 批准号: 1756012
• 负责人: Dong Dai
• 金额: $ 16.82万
• 依托单位: Texas Tech University
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2018
• 资助国家: 美国
• 起止时间: 2018-04-01 至 2018-10-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1756012&HistoricalAwards=false
• 关键词: CRII; CSR; Partitioning; Large; Graphs

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.

许多对我们社会很重要的计算应用程序，例如管理社交网络、分析人类基因组或建模人脑连接都严重依赖于大型图结构。在实践中，大型图的表示需要分区并存储在机器集群上，以确保所需的响应时间和吞吐量。这种经典的跨服务器分区问题已被广泛研究，并且已被证明是高度复杂的。此外，现代深度存储架构由于需要“跨层次”分区（即将图放置到存储系统的不同层中）而使问题进一步复杂化。这一变化使得现有的解决方案变得不够充分。本研究旨在寻求一种利用图结构和工作负载特征的整体方法，以在未来深度存储架构中为分布式图表示实现更好的性能。更具体地说，该项目包括两个协同研究任务，共同形成一种新颖的深度图分区解决方案。存储架构。第一个任务侧重于在线图放置算法，该算法可以根据精心设计的启发式分数立即将连续到达的图顶点和边分配到适当的服务器和特定的内部存储层。在第一个任务的基础上，第二个任务侧重于根据工作负载动态调整当前分区。这种调整基于新的提升/降级算法，该算法不仅提升/降级单个顶点，而且根据马太效应改变其邻居的优先级。随着大型图结构的重要性日益增加以及新存储技术的出现，现有的图存储系统在图分区方面面临着巨大的挑战。这项研究工作旨在在未来的存储架构中构建高效的分布式图存储系统。此外，该项目将研究活动与教育和外展工作相结合，以培养具有广泛包容性和全球竞争力的科学人才。该奖项反映了 NSF 的法定使命，并通过使用基金会的智力价值和更广泛的影响审查标准进行评估，被认为值得支持。