CluE: Towards Scalable Primitives for Graph Operations

当今的许多数据密集型应用领域，包括社交网络上的搜索和生物路径中的模块搜索，都需要对大型图形数据集进行复杂的查询。它们的高度连接特性意味着图形操作往往会在许多链接上“爬行”，导致非常大的内存占用，从而使当今的商用服务器上的资源变得紧张。此外，目前的应用平台缺乏对图形操作的抽象，使得开发人员只能实现各种复杂的独立图形查询组件。UCSB海量图形集群(MAGIC)项目的PI正在开发一个可扩展的基础设施，以提供图形基元的高级抽象，简化复杂查询的设计，同时解决最大化数据并行性和跨集群自适应图形分区的难题。该项目的进展将包括数据分区技术、用于图形操作的新原语以及软件基础设施，这些基础设施共同扩展了可扩展的集群基础设施的适用性，如MapReduce和Dryad，以在社交网络和生物图表中进行面向图表的查询。

Many of today's data-intensive application domains, including searches on social networks and module searches in biological pathways, require complex queries on large graph datasets. Their highly connected nature means graph operations tend to "crawl" across many links, resulting in very large memory footprints that strain resources on today's commodity servers. In addition, current application platforms lack abstractions for graph operations, leaving developers to implement a variety of complex standalone graph query components. The PIs of the UCSB Massive Graphs In Clusters (MAGIC) project are developing a scalable infrastructure to provide high level abstractions for graph primitives, simplifying design of complex queries while addressing difficult challenges of maximizing data parallelism and adaptive graph partitioning across clusters. Advances from this project will include data partitioning techniques, novel primitives for graph operations, and a software infrastructure that together expand the applicability of scalable cluster infrastructures such as MapReduce and Dryad to graph-oriented queries in social networks and biological graphs.