CAREER: G*: A Parallel System for Efficiently Processing Large Graphs

复杂的网络，如人类社会团体、交通网络和万维网，经常用图形表示。这个项目的目标是构建一个新的系统，既方便又高效地执行对大型图集合的查询。为了实现这一目标，该项目开发了能够有效地使用服务器集群的数据存储和处理技术。该项目的成果包括(1)利用图之间的共性的高效数据存储技术，(2)允许并行图处理解决方案的简单实现的方法，(3)通过跨图共享计算来加速多个图上的查询的框架，(4)以针对查询执行而优化的方式在磁盘上存储数据的技术，(5)通过在服务器上适当地分布数据来优化查询执行的方法，以及(6)在平衡恢复速度和所需成本的同时屏蔽服务器故障的技术。该项目对许多应用领域有重大影响，在这些领域了解各种类型的网络是至关重要的。例子包括国家安全、社会和政治研究、运输和营销。基于这项研究的编程作业和学期项目是为数据管理系统、分布式系统和社会网络分析的本科生/研究生课程开发的。该项目还通过纽约州立大学奥尔巴尼分校的暑期项目为高中生和少数族裔学生提供研究机会。该项目产生的软件、实验数据和研究论文将通过项目网站(http://www.cs.albany.edu/~jhh/research/G_star/).发布

Complex networks such as human social groups, transportation networks and the World Wide Web are frequently represented as graphs. The goal of this project is to construct a new system that both conveniently and efficiently executes queries on collections of large graphs. To achieve this goal, the project develops data storage and processing techniques that can effectively use a server cluster.The project's outcomes include (1) efficient data storage techniques that take advantage of commonalities between graphs, (2) methods that allow simple implementations of parallel graph processing solutions, (3) a framework that accelerates queries on multiple graphs by sharing computations across graphs, (4) techniques that store data on disks in a manner optimized for query execution, (5) methods that optimize query execution by appropriately distributing data over servers, and (6) techniques that mask server failures while balancing recovery speed and required cost.This project has significant impacts on many application areas where it is critical to understand networks of various types. Examples include national security, social and political studies, transportation and marketing. Programming assignments and term projects based on this research are developed for undergraduate/graduate courses on data management systems, distributed systems and social network analysis. This project also offers research opportunities to both high school and minority students through summer programs at the University at Albany, State University of New York. The software, experimental data and research papers that result from this project will be disseminated through the project website (http://www.cs.albany.edu/~jhh/research/G_star/).